Computation alignment: Capacity approximation without noise accumulation

Urs Niesen, Bobak Nazer, Phil Whiting

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


Consider several source nodes communicating across a wireless network to a destination node with the help of several layers of relay nodes. Recent work by Avestimehr has approximated the capacity of this network up to an additive gap. The communication scheme achieving this capacity approximation is based on compress-and-forward, resulting in noise accumulation as the messages traverse the network. As a consequence, the approximation gap increases linearly with the network depth. This paper develops a computation alignment strategy that can approach the capacity of a class of layered, time-varying wireless relay networks up to an approximation gap that is independent of the network depth. This strategy is based on the compute-and-forward framework, which enables relays to decode deterministic functions of the transmitted messages. Alone, compute-and-forward is insufficient to approach the capacity as it incurs a penalty for approximating the wireless channel with complex-valued coefficients by a channel with integer coefficients. Here, this penalty is circumvented by carefully matching channel realizations across time slots to create integer-valued effective channels that are well suited to compute-and-forward. Unlike prior constant gap results, the approximation gap obtained in this paper also depends closely on the fading statistics, which are assumed to be i.i.d. Rayleigh.

Original languageEnglish
Article number6457453
Pages (from-to)3811-3832
Number of pages22
JournalIEEE Transactions on Information Theory
Issue number6
Publication statusPublished - 2013
Externally publishedYes


Dive into the research topics of 'Computation alignment: Capacity approximation without noise accumulation'. Together they form a unique fingerprint.

Cite this