Cyclic polar codes
Arikan introduced polar codes in 2009 and proved that they achieve the symmetric capacity, under low-complexity successive cancellation decoding, of any binary-input discrete memoryless channel. Arikan's construction is based on the Kronecker product of 2-by-2 matrices and it was extended to larger matrices by Şaşoǧlu et al. in 2010. In this paper, we construct cyclic polar codes based on a mixed-radix Cooley-Tukey decomposition of the Galois field Fourier transform. Ignoring the twiddle factors between stages, the derived fast Fourier transform is essentially a Kronecker product of small Fourier transform matrices. Thus, one can define a successive cancellation decoder and observe that the coordinate channels polarize. Choosing the locations of the frozen symbols in the resulting polar code is identical to choosing the locations of zeros in the Fourier transform of the codewords and, thus, the code is cyclic.
