UC San Diego

The discovery of polar codes has been widely acknowledged as one of the most original and profound breakthroughs in coding theory in the recent two decades. Polar codes form the first explicit family of codes that provably achieves Shannon's capacities with efficient encoding and decoding for a wide range of channels. This solves one of the most fundamental problems in coding theory. At the beginning of its invention, polar code is more recognized as an intriguing theoretical topic due its mediocre performance at moderate block lengths. Later, with the invention of the list decoding algorithm and various other techniques, polar codes now show competitive, and in some cases, better performance as compared with turbo and LDPC codes. Due to this and other considerations, the 3rd Generation Partnership Project (3GPP) has selected polar codes for control and physical broadcast channels in the enhanced mobile broadband (eMBB) mode and the ultra-reliable low latency communications (URLLC) mode of the fifth generation (5G) wireless communications standard.

In this dissertation, we propose new theories on a wide range of topics in polar coding, including structural properties, construction methods, and decoding algorithms.

We begin by looking into the weight distribution of polar codes. As an important characteristic for an error correction code, weight distribution directly gives us estimations on the maximum-likelihood decoding performance of the code. In this dissertation, we present a deterministic algorithm for computing the entire weight distribution of polar codes. We first derive an efficient procedure to compute the weight distribution of polar cosets, and then show that any polar code can be represented as a disjoint union of such polar cosets. We further study the algebraic properties of polar codes as decreasing monomial codes to bound the complexity of our approach. Moreover, we show that this complexity can be drastically reduced using the automorphism group of decreasing monomial codes.

Next, we dive into the topic of large kernel polar codes. It has been shown that polar codes achieve capacity at a rather slow speed, where this speed can be measured by a parameter called scaling exponent. One way to improve the scaling exponent of polar codes, is by replacing their conventional 2x2 kernel with a larger polarization kernel. In this dissertation, we propose theories and a construction approach for a special type of large polarization kernels to construct polar codes with better scaling exponents. Our construction method gives us the first explicit family of codes with scaling exponent provably under 3. However, large kernel polar codes are known for their high decoding complexity. In that respect, we also propose a new decoding algorithm that can efficiently perform successive cancellation decoding for large kernel polar codes.

Moving on to the decoding algorithms, we focus ourselves on a new family of codes called PAC codes, recently introduced by Arikan, that combines polar codes with convolutional precoding. At short block lengths such as 128, PAC codes show better performance under sequential decoding compared with conventional polar codes with CRC precoding. In this dissertation, we first show that we can achieve the same superior performance of PAC codes using list decoding with relatively large list sizes. Then we carry out a qualitative complexity comparison between sequential decoding and list decoding for PAC codes.

Lastly, we look into the subject of polar coded modulation. Bit-interleaved coded modulation (BICM) and multilevel coded modulation (MLC) are two ways commonly used to combine polar codes with high order modulation. In this dissertation, we propose a new hybrid polar coded modulation scheme that lies between BICM and MLC. For high order modulation, our hybrid scheme has a latency advantage compared with MLC. And by simulation we show that our hybrid scheme also achieves a considerable performance gain compared with BICM.