Explicit Polar Codes with Small Scaling Exponent. (arXiv:1901.08186v2 [cs.IT] UPDATED)

Herein, we focus on explicit constructions of $\ell\times\ell$ binary kernels with small scaling exponent for $\ell \le 64$. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent $\mu < 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 $\ell\times\ell$ kernel $K_\ell$ transforms an underlying BEC into $\ell$ bit-channels $W_1,W_2,\ldots,W_\ell$. The erasure probabilities of $W_1,W_2,\ldots,W_\ell$, known as the polarization behavior of $K_\ell$, determine the resulting scaling exponent $\mu(K_\ell)$. 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_\ 查看全文>>