EPFL doctorate Award 2018 – Marco Mondelli
From Polar to Reed-Muller Codes: Unified Scaling, Nonstandard Channels, and a Proven Conjecture
EPFL thesis n°7164 (2016)
Thesis director: Prof. M. R. Urbanke
"For fundamental contributions to coding theory. In particular, for proving that Reed-Muller codes achieve capacity on the binary erasure channel, coding for non-standard channels, and insight into the scaling behavior of codes in the finite-length regime."
One century after Shannon’s birth, his idea of developing mathematically principled solutions to complex engineering problems is as relevant as ever. In particular, the problem of transmitting information from point to point efficiently and with low complexity is being studied extensively, and the results of this research effort can be found in any of your communication or storage devices today. Next-generation communication systems call for the design of channel codes with small length that achieve high rates, high reliability, and low latency in a variety of transmission settings. In this thesis, we address the two grand challenges of modern communications which consist in (i) designing codes that are optimal in the non-asymptotic regime and in (ii) performing this task over non-standard channels that are much more complex than symmetric point-to-point communication links. More specifically, we consider the finite-length performance of polar codes, which were recently included in the 5G standard, and develop a unified framework to rigorously analyze the scaling of the relevant parameters. We propose provably optimal low-complexity solutions for the broadcast channel, such as the downlink of a cellular system, and the asymmetric channel, such as the channel for fiber links. Last but not least, we present a completely new paradigm of what makes a code optimal: we prove that Reed-Muller codes achieve capacity thus solving a long-standing conjecture.