On successive cancellation decoding of polar codes and related codes

Polar codes with a successive cancellation decoder were historically the first practical coding scheme that was able to reliably transmit digital data at the highest possible data rate. This thesis gives new insights on successive cancellation decoding of polar codes and related codes. It consists of three parts. The first part presents a partial order for the synthesized channels of a polar code that is independent of the transmitting channel. This partial order is combined with a partial order from the literature. A minimal representation of this combined partial order is derived that enables us to practically use the combined partial order for simplifying the construction of polar codes. The second part investigates successive cancellation decoding of codes based on the Discrete Fourier Transform over finite fields. Successive cancellation decoding in the natural symbol order is impractical for reasonable blocklength. However, based on the Cooley-Tukey Fast Fourier Transform, we found that successive cancellation decoding in the digitreversed symbol order has significantly lower complexity but comes along with slower polarization. However, for most codes, even this reduced complexity is still impractical. We found that for the reasonably high blocklength of 256, successive cancellation decoding in the digit-reversed order is feasible. Simulations showed that the synthesized channels polarize. Moreover, for that blocklength, we found a way to choose the frozen symbols of the Discrete Fourier Transform code such that its performance under successive cancellation list decoding is very well. However, the decoding complexity is still much higher than for other coding schemes with comparable performance. The third part introduces the fat-tree decoder, which is applicable to polar codes and related codes and which is a generalization to the successive cancellation decoder. The fat-tree decoder does message passing on a cycle-free factor graph for the polar code and thus computes exact posterior probabilities. The fat-tree decoder is able to decode the information symbols of a polar code in any desired order. Moreover, it has the ability to take into account any frozen symbols even from the future symbols. However, to keep the complexity manageable, only a limited number of frozen symbols can be considered and the symbol decoding order is not completely arbitrary. We present two specific fat-tree decoder strategies that perform substantially better than the successive cancellation decoder and have manageable complexity. Moreover, these strategies approach block maximum a posteriori performance for polar codes of many parameters. The high flexibility of the fat-tree decoder suggests that even better tradeoffs between performance and decoding complexity exist.