Generator matrix selection for finite-length polar codes

Abstract

Polar coding is a recently proposed coding technique, which has been proven to achieve the channel capacity. The original 2 x 2 generator matrix polarizes the channels and a portion of channels' capacity approach 1, while the remaining channel capacities approach 0. In the literature, it was shown that, as the codelength goes to in nity, polarization performance of Ar kan's 2 x 2 matrix is better than any matrix of size less than 16 x 16. In this thesis, we show that this observation does not necessarily hold for the nite-length case and the channel polarization is attainable by using di erent generator matrices. The main contribution of this thesis consists of lling the gap on the analysis of the nite-length polar code generation. A normalized polarization distance measure was de ned and polar codes from di erent generator matrices showing di erent amount of polarization e ects were obtained using this measure. Also, the coding structure for these generalized polar codes were obtained. Polarization performances in both asymptotical and nite-length cases were investigated especially for generator matrices of size 3 x 3 and 4 x 4 using Bhattacharyya parameter histograms, polarization rate exponents and normalized polarization distance measures; also upper bound on block error probabilities for these matrices were analyzed. Moreover, the recursive likelihood ratio equations for a speci c 4 x 4 matrix showing the best polarization performance among all 4 x 4 generator matrices were de ned. A decoding algorithm was implemented for a generator matrix from the best group of 4 x 4 generator matrices and its erasure rate was compared with the Ar kan's original generator matrix' decoding performance.