Reed–Muller Codes for Random Erasures and Errors
Reed–Muller Codes for Random Erasures and Errors
复制标题
用于随机擦除和错误的里德-穆勒码
DOI：
10.1145/2746539.2746575
复制
发表时间：
2014
影响因子：
2.5
通讯作者：
A. Wigderson
中科院分区：
文献类型：
--
作者：
E. Abbe;Amir Shpilka;A. Wigderson
研究了二进制Reed-Muller （RM）码在二进制擦除信道和二进制对称信道上能够成功解码的参数，特别是在什么情况下能够达到这两种经典信道的容量。本文还研究了输入随机集上多元GF(2)多项式的求值性质。对于擦除，我们证明了RM码在非常高的速率和非常低的速率下都具有容量。对于错误，我们证明了RM码在非常低的速率下实现了容量，对于非常高的速率，我们证明了它们可以在容量错误数的平方根处唯一地解码。这四个结果的证明基于不同的技术，我们发现它们各自都很有趣。特别地，我们研究了矩阵E（m, r）的下述问题，矩阵E（m, r）的行是m个变量中所有阶≤r的单项式的真值表。什么是最重要的？在E（m, r）中定义一个列秩满的子矩阵的随机列的最少个数。满行秩)与高概率？对于非常小的响应，我们得到了严密的边界。非常大)度r，我们用它来表明RM代码在这些制度中实现了擦除的能力。我们对随机错误的解码来自以下的新颖还原。对于每一个足够高速率的线性码C，我们构造了一个通过张紧C得到的新码C‘，使得对于坐标的每一个子集S，如果C可以从S中的擦除中恢复，那么C’可以从S中的错误中恢复。将此专门用于RM码并使用我们的擦除结果意味着我们对RM码的高速率唯一解码的结果。最后，我们实现结果的两个能力要求RM代码的权重分布有严格的界限。将常次多项式的边界推广到线性次多项式的边界，得到了这样的边界。
This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the binary erasure channel and binary symmetry channel, and, in particular, when can they achieve capacity for these two classical channels. Necessarily, this paper also studies the properties of evaluations of multivariate GF(2) polynomials on the random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about the square root of the number of errors at capacity. The proofs of these four results are based on different techniques, which we find interesting in their own right. In particular, we study the following questions about E(m, r), the matrix whose rows are the truth tables of all the monomials of degree ≤ r in m variables. What is the most (resp. least) number of random columns in E(m, r) that define a submatrix having full column rank (resp. full row rank) with high probability? We obtain tight bounds for very small (resp. very large) degrees r, which we use to show that RM codes achieve capacity for erasures in these regimes. Our decoding from random errors follows from the following novel reduction. For every linear code C of sufficiently high rate, we construct a new code C' obtained by tensorizing C, such that for every subset S of coordinates, if C can recover from erasures in S, then C' can recover from errors in S. Specializing this to the RM codes and using our results for erasures imply our result on the unique decoding of the RM codes at high rate. Finally, two of our capacity achieving results require tight bounds on the weight distribution of RM codes. We obtain such bounds extending the recent bounds from constant degree to linear degree polynomials.