Paper Title | Explicit Polar Codes with Small Scaling Exponent |
---|---|

Paper Identifier | TH1.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$. |