Polarization and Spatial Coupling: Two Techniques to Boost Performance
S. Hamed Hassani · 2013
Abstract During the last two decades we have witnessed considerable activity in build-ing bridgesbetween the fields of informationtheory/communications, computerscience, and statistical physics. This is due to the realization that many fun-damental concepts and notions in these fields are in fact related and that eachfield can benefit from the insight and techniques developed in the others.For instance, the notion of channel capacity in information theory, thresholdphenomena in computer science, and phase transitions in statistical physics areall expressions of the same concept. Therefore, it would be beneficial to developa common framework that unifies these notions and that could help to leverageknowledge in one field to make progress in the others. A particularly strikingexample is the celebrated belief propagation algorithm. It was independentlyinvented in each of these fields but for verydifferentpurposes.Therealizationof the commonality has benefited each of the areas.We investigate polarization and spatial coupling:twotechniquesthatwereoriginally invented in the context of channel coding (communications) thus re-sulting for the first time in efficient capacity-achieving codes for a wide rangeof channels. As we will discuss, both techniques play a fundamental role alsoin computer science and statistical physics and so these two techniques canbe seen as further fundamental building blocks that unite all three areas. Wedemonstrate applications of these techniques, as well as the fundamental phe-nomena they provide.In more detail, this thesis consists of two parts. In the first part, we considerthe technique of polarization and its resultant class of channel codes, called po-lar codes. Our main focus is the analysis and improvement of the behaviorof polarization towards the most significant aspects of modern channel-codingtheory: scaling laws, universality, and complexity (quantization). For eachof these aspects, we derive fundamental laws that govern the behavior of po-larization and polar codes. Even though we concentrate on applications incommunications, the analysis that we provide is general and can be carriedover to applications of polarization in computer science and statistical physics.As we will show, our investigations confirm some of the inherent strengthsof polar codes such as their robustness with respect to quantization. But theyalso make clear in which aspects further improvement of polar codes is needed.i