Arikan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the {\em polarization} of an associated $[0,1]$-bounded martingale, namely its convergence in the limit to either $0$ or $1$. Arikan showed polarization of the martingale associated with the matrix $G_2 = \left(\begin{matrix} 1& 0 \\ 1& 1\end{matrix}\right)$ to get capacity achieving codes. His analysis was later extended to all matrices $M$ that satisfy an obvious necessary condition for polarization. While Arikan's theorem does not guarantee that the codes achieve capacity at small blocklengths, it turns out that a "strong" analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with $G_2$ such a strong polarization was shown in two independent works ([Guruswami and Xia, IEEE IT '15] and [Hassani et al., IEEE IT '14]), resolving a major theoretical challenge of the efficient attainment of Shannon capacity. In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more general, our proofs of strong polarization are also simpler and modular. Specifically, our result shows strong polarization over all prime fields and leads to efficient capacity-achieving codes for arbitrary symmetric memoryless channels. We show how to use our analyses to achieve exponentially small error probabilities at lengths inverse polynomial in the gap to capacity. Indeed we show that we can essentially match any error probability with lengths that are only inverse polynomial in the gap to capacity.
翻译:Arikan令人兴奋地发现了极地代码,这为高效率地实现香农能力提供了全新的新途径。鉴于一个(固定大小)不可倒置的基质,极地代码大家庭可以与这个基质挂钩,其能力来自相关的 $80,1美元绑定的马丁格勒, 即它以零美元或1美元为限。 Arikan展示了与基质 $_2 = left (\ begin{matrix} 1 & 0\ 0\ 1\\ end{matrix{right) 相联的马丁基质, 以获得能力。 他的分析后来扩大到所有满足极化明显必要条件的基质 $M。 虽然 Arikan的理论无法保证代码在小块长度内达到能力, 也就是说, 对基质马丁格尔的极分化只会导致这样的构建。 事实上, 与 与 $G_ 2 相关的马丁基值 和 如此强烈的极分化在两个独立工程( [Guruiswami] 和 Xialalalalalalalalalal dal dalal) 分析中显示我们所需的直径 。