UC Berkeley

In a network, interference between transmitters is usually viewed as highly undesirable and clever algorithms and protocols have been devised to avoid it. Collectively, these strategies transform the physical layer into a set of reliable bit pipes which can then be used seamlessly by higher layers in the protocol stack. Unfortunately, interference avoidance results in sharply decreasing rates as the number of users increases. In this thesis, we develop a new tool, computation coding, that allows receivers to reliably decode equations of transmitted messages by harnessing the interference structure of the channel. Applied to a wireless network, this enables relays to decode linear functions of the transmitted messages with coefficients dictated by the fading realization. Relays can then forward these equations towards the destinations which simply collect enough equations to solve for their desired messages. Structured codes (such as lattices) ensure that these linear combinations can be decoded reliably at the relays, often at far higher rates than the messages individually. Through examples drawn from cooperative communication including cellular uplink, distributed MIMO and wireless network coding, we demonstrate that this compute-and-forward strategy can improve end-to-end throughput in a network. As a consequence, we will see that structured codes can play an important role in approaching the capacity of networks. We also show that our techniques can result in both energy and delay savings for distributed signal processing over a sensor network. Finally, by viewing interference as implicit computation, we provide a new perspective on the interference channel with time-varying fading. We describe a simple interference alignment scheme that enables each user to achieve at least half its interference-free capacity at any signal-to-noise ratio.