General strong polarization
General strong polarization
复制标题
DOI：
10.1145/3188745.3188816
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Jarosław Błasiok;V. Guruswami;Preetum Nakkiran;A. Rudra;M. Sudan
中科院分区：
文献类型：
--
作者：
Jarosław Błasiok;V. Guruswami;Preetum Nakkiran;A. Rudra;M. Sudan
Arikan对极地代码的令人兴奋的发现提供了一种有效实现Shannon容量的新方法。在相关的[0,1]结合的martingale中，即其在限制为0或1的限制的收敛概率为1。Arikan显示了与矩阵G2相关的Martingale的适当极化实现他的分析的能力。是通道的容量和代码速率之间的差异），事实证明，对基础mar的极化的“强”分析确实会导致这种结构。因此，在这项工作中解决了与有效的香农能力相关的主要理论挑战，我们将结果扩展到与所有满足（弱）极化的条件相关的条件。在我们看来，强大的偏振也更简单，而我们证明的关键是对局部极化的通知，仅取决于马丁格的演变。然后，我们对有条件的熵进行相对简单的推理来证明我们的局部极化，我们的结果在所有素数上都表现出强大的极化，并导致有效的容量源代码。编码任意对称的无内存通道。
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 polarization of an associated [0,1]-bounded martingale, namely its convergence in the limit to either 0 or 1 with probability 1. Arikan showed appropriate polarization of the martingale associated with the matrix G2 = ( [complex formula not displayed] ) to get capacity achieving codes. His analysis was later extended to all matrices M which satisfy an obvious necessary condition for polarization. While Arikan’s theorem does not guarantee that the codes achieve capacity at small blocklengths (specifically in length which is a polynomial in 1/є where є is the difference between the capacity of a channel and the rate of the code), 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 G2 such a strong polarization was shown in two independent works ([Guruswami and Xia, IEEE IT ’15] and [Hassani et al., IEEE IT’14]), thereby resolving a major theoretical challenge associated with 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 (in our view) also much simpler and modular. Key to our proof is a notion of local polarization that only depends on the evolution of the martingale in a single time step. We show that local polarization always implies strong polarization. We then apply relatively simple reasoning about conditional entropies to prove local polarization in very general settings. Specifically, our result shows strong polarization over all prime fields and leads to efficient capacity-achieving source codes for compressing arbitrary i.i.d. sources, and capacity-achieving channel codes for arbitrary symmetric memoryless channels.