Technical Program

Paper Detail

Paper Title Explicit Polar Codes with Small Scaling Exponent
Paper IdentifierTH1.R1.1
Authors Hanwen Yao, Arman Fazeli, Alexander Vardy, University of California, San Diego, United States
Session Polar Codes II
Location Le Théatre (Parterre), Level -1
Session Time Thursday, 11 July, 09:50 - 11:10
Presentation Time Thursday, 11 July, 09:50 - 10:10
Manuscript  Click here to download the manuscript
Abstract Polar coding gives rise to the first explicit family of codes that provably achieve capacity for a wide range of channels with efficient encoding and decoding. But how fast can polar coding approach capacity as a function of the code length? In finite-length analysis, the scaling between code length and the gap to capacity is usually measured in terms of the \emph{scaling exponent} $\mu$. It is well known that the optimal scaling exponent, achieved by random binary codes, is $\mu = 2$. It is also well known that the scaling exponent of conventional polar codes on the binary erasure channel (BEC) is $\mu =3.627$, which falls far short of the optimal value. On the other hand, it was recently shown that polar codes derived from $\ell\times\ell$ \emph{binary polarization kernels} approach the optimal scaling exponent $\mu = 2$ on the BEC as $\ell \to \infty$, with high probability over a random choice of the kernel. Herein, we focus on \emph{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 \emph{polarization behavior of $K_\ell$}, determine the resulting scaling exponent $\mu(K_\ell)$. We first introduce a class of \emph{self-dual} binary kernels and prove that their polarization behavior satisfies a strong symmetry property. This reduces the problem of constructing $K_\ell$ to that of producing a certain nested chain of only $\ell/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 $\mu(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 $\mu(K_{64})\simeq 2.87$. We augment this estimate with a rigorous proof that $\mu(K_{64})< 2.97$.