Explicit Polar Codes with Small Scaling Exponent
Explicit Polar Codes with Small Scaling Exponent
复制标题
具有小缩放指数的显式极性代码
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Vardy
中科院分区：
文献类型：
--
作者：
Hanwen Yao;Arman Fazeli;A. Vardy
极性编码产生了第一个明确的编码家族，可以证明它具有高效编码和解码的大范围信道的容量。但是极性编码能多快地将容量作为编码长度的函数呢？在有限长度分析中，代码长度和容量差距之间的缩放通常用缩放指数µ来衡量。众所周知，由随机二进制码实现的最优标度指数是µ= 2。众所周知，在二进制擦除信道（BEC）上，传统极性码的标度指数为µ= 3.627，远远达不到最优值。另一方面，最近的研究表明，由r × r二元极化核得到的极码在BEC上接近最优标度指数μ = 2，且在随机选择核的情况下具有高概率。在此，我们重点研究了对于r≥64，具有小标度指数的r × r二进制核的显式构造。特别是，我们展示了一个二进制线性码序列，它在BEC上接近容量，具有准线性复杂度和标度指数µ< 3。据我们所知，这样的密码序列以前并不存在。建立我们的结果的主要挑战是双重的：如何构建这样的核和如何评估它们的缩放指数。在一个极化阶跃中，一个r × r核K将底层的BEC变换成r个位通道W1， W2，…，W1。W1, W2，…，wl的擦除概率，即K l的极化行为，决定了最终的标度指数µ（K l）。首先引入了一类自对偶二元核，并证明了它们的极化行为满足强对称性。这就把构造K - r的问题简化为构造一个只有r /2个自正交码的嵌套链的问题。我们使用嵌套循环码来构造核K32和K64，其距离在正交性约束下尽可能高。为了评估K32和K64的极化行为，提出了两种可选的栅格表示（这可能是独立的兴趣）。使用得到的网格，我们表明µ(K32) = 3.122，并显式计算K64的一半以上的极化行为系数，此时复杂性变得令人望而却步。为了完成这一计算，我们引入了蒙特卡罗插值方法，得到了一个估计µ(K64)≃2.87。我们用一个严格的证明来增强这个估计，µ(K64) < 2.97。
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 scaling exponent µ. It is well known that the optimal scaling exponent, achieved by random binary codes, is µ = 2. It is also well known that the scaling exponent of conventional polar codes on the binary erasure channel (BEC) is µ = 3.627, which falls far short of the optimal value. On the other hand, it was recently shown that polar codes derived from ℓ × ℓ binary polarization kernels approach the optimal scaling exponent µ = 2 on the BEC as ℓ→∞, with high probability over a random choice of the kernel.Herein, we focus on explicit constructions of ℓ×ℓ binary kernels with small scaling exponent for ℓ ⩽ 64. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent µ < 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 ℓ×ℓ kernel Kℓ transforms an underlying BEC into ℓ bit-channels W1, W2,…, Wℓ. The erasure probabilities of W1, W2,…, Wℓ, known as the polarization behavior of Kℓ, determine the resulting scaling exponent µ(Kℓ). 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ℓ to that of producing a certain nested chain of only ℓ/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 K32 and K64. In order to evaluate the polarization behavior of K32 and K64, two alternative trellis representations (which may be of independent interest) are proposed. Using the resulting trellises, we show that µ(K32) = 3.122 and explicitly compute over half of the polarization-behavior coefficients for K64, at which point the complexity becomes prohibitive. To complete the computation, we introduce a Monte-Carlo interpolation method, which produces the estimate µ(K64) ≃ 2.87. We augment this estimate with a rigorous proof that µ(K64) < 2.97.
影响因子：
2.5
作者：
Hessam Mahdavifar
通讯作者：
Hessam Mahdavifar