UC San Diego

Polar codes are the first family of error-correcting codes that was proved to achieve the capacity of binary memoryless symmetric (BMS) channels with efficient encoding and decoding algorithms. They have been drawing increasing interests in both industrial and academic research, especially after being adopted by the 3rd generation partnership project (3GPP) group as the channel codes for the control channel of the 5th generation (5G) wireless systems. The main goal of this dissertation is to explore polar coding techniques, as well as improve the current state-of-the-art, thereby broadening the applications of polar codes.

We begin by studying partial orders (POs) for the synthesized bit-channels of polar codes. We give an alternative proof of an existing PO for bit-channels with the same Hamming weight and use the underlying idea to extend the bit-channel ordering to some additional cases. The bit-channels with universal ordering positions for binary erasure channel (BEC), which are independent of the channel erasure probability, are verified for all of the code blocklengths. We also show the threshold behavior of the Bhattacharyya parameters of some bit-channels by approximating the threshold values.

Then, we move on to the decoding algorithms and improved polar codes. Despite the impressive asymptotic behavior by channel polarization, empirical results indicate less impressive performance of the successive cancellation (SC) decoder for polar codes of short blocklengths, e.g., compared to low-density parity-check (LDPC) codes. We consider belief propagation list (BPL) decoding with a special family of factor-graph layer permutations called stable permutations (SPs) that preserve a specified information set when the corresponding bit permutations are applied to message bit indices. Then, we propose a new code construction methodology to interpolate between Reed-Muller (RM) and polar codes. The new family of hybrid RM-polar codes has superior performance under several decoding algorithms, including SC list (SCL), belief propagation (BP), BPL, and soft-cancellation list (SCANL). By taking advantage of an existing PO on bit-channels whose corresponding indices share the same Hamming weight, we analyze the complexity of the new construction method. Furthermore, we propose an algorithm of BP decoding for polar codes with a special family of large kernels called permuted kernels, in which the leftmost messages over the factor graph need to be permuted accordingly.