CMU-CS-22-102Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-22-102
Andrii Riazanov Ph.D. Thesis May 2022
Keywords:
Coding Theory, Capacity-achieving Codes, Polar Codes, Scaling Exponent
Reliable transmission of data is a central topic in coding theory and information theory. Both of these fields were founded by Claude E. Shannon in his seminal work, where he formalized the problems of communicating information and established their limits. It has been a major problem since then to find explicit coding schemes that achieve these limits. For channel coding this corresponds to finding codes that achieve channel (Shannon) capacity. Channel polarization is a novel approach to code construction introduced by Arikan, which he used to construct polar codes that provably achieve capacity for any memoryless symmetric channel and have low encoding and decoding complexities.
The focus of this thesis is on constructing a variant of polar codes with
an almost optimal speed of convergence to capacity. Let N on the gap δ to capacity is known to be the best possible.
We construct, for any sufficiently small δ > 0, a variant of polar codes with rate W with quasi-linear time encoding and decoding. This result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length, which resolves a central theoretical challenge associated with the attainment of Shannon capacity.The codes constructed in this dissertation are a variant of ArÄ±kan's polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity. 124 pages
Srinivasan Seshan, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |