Structural Results for Coding Over Communication Networks

Shannon's theory of communications has its fingerprints on every electronic device we own, every computer screen we gaze into. Vitalized by the promise of enabling reliable data compression and communication, it has inspired hundreds of researchers over the past decades. In Point-to-Point (PtP) communications, the optimal performance was characterized by Shannon. However, it was only recently, with the introduction of LDPC codes and polar codes, that this was made a practical possibility. While the promise of achieving optimal performance has come to fruition in PtP communication, the problem has remained open in network communications.

In this talk, we investigate the short-comings of the existing network coding strategies. We prove the necessity of structure in optimality achieving codes. We argue that the lack of such structure in the current coding schemes contributes to their sub-optimality. First, we consider linear codes, and their continuous duals lattice codes. Next, we propose a new class of codes called quasi-linear codes. Lastly, we consider codes constructed over finite block-lengths. The assumption that the performance of coding schemes improves with increasing block-length has been a hallmark of multi-terminal communication strategies. We prove that in many cases this assumption is incorrect.