Explicit Polar Codes with Small Scaling Exponent
share
Herein, we focus on explicit constructions of ℓ×ℓ binary kernels with small scaling exponent for ℓ< 64. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent μ < 3. To the best of our knowledge, such a sequence of codes was not previously known to exist. The principal challenges in establishing our results are twofold: how to construct such kernels and how to evaluate their scaling exponent. In a single polarization step, an ℓ×ℓ kernel K_ℓ transforms an underlying BEC into ℓ bit-channels W_1,W_2,...,W_ℓ. The erasure probabilities of W_1,W_2,...,W_ℓ, known as the polarization behavior of K_ℓ, determine the resulting scaling exponent μ(K_ℓ). We first introduce a class of self-dual binary kernels and prove that their polarization behavior satisfies a strong symmetry property. This reduces the problem of constructing K_ℓ to that of producing a certain nested chain of only ℓ/2 self-orthogonal codes. We use nested cyclic codes, whose distance is as high as possible subject to the orthogonality constraint, to construct the kernels K_32 and K_64. In order to evaluate the polarization behavior of K_32 and K_64, two alternative trellis representations (which may be of independent interest) are proposed. Using the resulting trellises, we show that μ(K_32)=3.122 and explicitly compute over half of the polarization behavior coefficients for K_64, at which point the complexity becomes prohibitive. To complete the computation, we introduce a Monte-Carlo interpolation method, which produces the estimate μ(K_64)≃ 2.87. We augment this estimate with a rigorous proof that, with high probability, we have μ(K_64)< 2.99.
READ FULL TEXT