Computation Alignment: Capacity Approximation without Noise Accumulation
arXiv:1108.6312
Abstract
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 et al. 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.
36 pages, to appear in IEEE Transactions on Information Theory
References in corpus (6)
- Interference Alignment and the Degrees of Freedom for the K User Interference Channel
- An Algebraic Approach to Physical-Layer Network Coding
- Aligned Interference Neutralization and the Degrees of Freedom of the 2x2x2 Interference Channel
- A Layered Lattice Coding Scheme for a Class of Three User Gaussian Interference Channels
- Multiple Unicast Capacity of 2-Source 2-Sink Networks
- The Degrees of Freedom of Compute-and-Forward