(October 7) A Joint Typicality Approach to Algebraic Network Information Theory

In network information theory, many of the successful coding theorems and analytical tools have been developed based on random i.i.d. code ensembles. In another branch of network information theory, several coding theorems have been developed based on random structured codes. As well demonstrated by Korner and Marton in the problem of distributed computing of binary sources and the compute—forward framework by Nazer and Gastpar, structured codes can outperform i.i.d. codes when applied to computation problems. In particular, the lattice based compute—forward strategy can be employed as an end-to-end communication strategy for relaying, interference alignment, and many other applications over Gaussian networks.

However, the coding theorems based on structured codes are developed and tailored for their specific network problems which makes it difficult to extend and improve. Motivated by the rich information theoretic coding theorems for random i.i.d. codes and the performance benefits of structured lattice codes for computation applications, our primary interest is in the development of a joint typicality approach to algebraic network information theory.

In this talk, I will discuss how the key lemmas in network information theory such as packing, covering, and joint typicality lemmas can be applied to linear code ensembles. Using this approach, we extend and improve the compute—forward framework with a unified treatment over both discrete memoryless and Gaussian networks. The key component for the improvement is at the decoder in which it recovers multiple linear combinations jointly instead of the successive cancellation decoder used for compute—forward with lattices. The proposed framework provides a new perspective to physical layer network coding and interference cancellation/alignment applications.