UC San Diego

The discovery of channel polarization and polar codes is universally recognized as an historic breakthrough in coding theory. Polar codes provably achieve the capacity of any memoryless symmetric channel, with low encoding and decoding complexity. Moreover, for short block lengths, polar codes under specific decoding algorithms are currently the best known coding scheme for binary-input Gaussian channels. Due to this and other considerations, 3GPP has recently decided to incorporate polar codes in the 5G wireless communications standard. Soon enough, a remarkably short time after their invention, we will be all using polar codes whenever we make a phone call or access the Internet on a mobile device.

Our goal in this dissertation is to explore new frontiers in polar coding, thereby fundamentally advancing the current state-of-the-art in the field. Parts of the results are immediately relevant for successful deployment of polar codes in wireless systems, whereas other parts will focus on key theoretical problems in polar coding that have a longer time-horizon.

We begin by studying the effect of the polarization kernels in the asymptotic behavior of polar codes. We show that replacing the conventional 2×2 kernel in the construction of polar codes with that of a larger size can reduce the gap to the capacity if the larger kernel is carefully selected. A heuristic algorithm is proposed that helps to find such kernels. Furthermore, we prove that a near-optimal scaling behavior is achievable if one is allowed to increase the kernel size as needed. We also study the computational complexity of decoding algorithms for polar codes with large kernels, which are viewed as their main implementation obstacle.

Moving on to the decoding algorithms, we carefully analyze the performance of the successive cancellation decoder with access to the abstract concept of Arikan’s genie. The CRC-aided successive-cancellation list decoding, the primary decoding method of polar codes, is commonly viewed as an implementation of the Arikan’s genie. However, it comes short at completely simulating the genie since the auxiliary information (CRC) comes to the help only at the end of the decoding process. We overcome this problem by introducing the convolutional decoding algorithm of polar codes that is based on a high-rate convolutional pre-coder and utilizes Viterbi Algorithm to mimic the genie all the way through the SC decoding process.

Lastly, we look into channels with deletions. A key assumption in the traditional polar coding is to transmit coded symbols over independent instances of the communication channel. Channels with memory and in particular, deletion channels, do not follow this rule. We introduce a modified polar coding scheme for these channels that depend on much less computational power for decoding than the existing solutions. We also extend the polarization theorems to provide theoretical guarantee and to prove the correctness of our algorithms.