Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Exploiting Interference through Algebraic Structure

Bobak Anthony Nazer

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-186
December 18, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-186.pdf

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 find 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.

Advisor: Michael Gastpar


BibTeX citation:

@phdthesis{Nazer:EECS-2009-186,
    Author = {Nazer, Bobak Anthony},
    Title = {Exploiting Interference through Algebraic Structure},
    School = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-186.html},
    Number = {UCB/EECS-2009-186},
    Abstract = {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 find 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.}
}

EndNote citation:

%0 Thesis
%A Nazer, Bobak Anthony
%T Exploiting Interference through Algebraic Structure
%I EECS Department, University of California, Berkeley
%D 2009
%8 December 18
%@ UCB/EECS-2009-186
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-186.html
%F Nazer:EECS-2009-186