Compute-and-Forward: Harnessing Interference with Structured Codes

For a centralized encoder and decoder, a channel matrix is simply a set of linear equations that can be transformed into parallel channels. We develop a similar approach to multiuser networks: we view interference as creating linear equations of codewords and that a receiver's goal is to collect a full rank set of such equations. Our new relaying technique, compute-and-forward, uses structured codes to reliably compute functions over channels. This allows the relays to efficiently recover a linear functions of codewords without recovering the individual codewords. Thus, our scheme can work with the structure of the interference while removing the effects of the noise at the relay. We apply our scheme to a Gaussian relay network with interference and achieve better rates than either compress-and-forward or decode-and-forward for certain regimes.