On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures
On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures
复制标题
关于 Reed-Muller 码相对于随机错误和擦除的性能
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Amir Shpilka
中科院分区：
文献类型：
--
作者：
Ori Sberlo;Amir Shpilka
这项工作证明了新的结果的能力，二进制Reed-Muller码解码的随机错误和擦除。我们得到这些结果证明改进的Reed-Muller码的重量分布的高度上的界限。具体而言，给定权重$eta in（0，1）$我们证明了相对权重最多$的码字数量的上界eta$。我们在两种不同的设置中获得了新的结果：对于权重$eta < 1/2$，权重接近1/2$。
我们的新的界限上的重量分布意味着RM码与$m$变量和度$伽玛m$，为一些明确的常数$伽玛$，实现随机擦除（即二进制擦除信道）和随机错误（二进制对称信道）的能力。早先，已知RM码实现了对于度r = o（m）$的二进制对称信道的容量。对于二进制擦除信道，已知RM码在[m/2 pm O（sqrt{m}）]$中实现度$o（m）$或$r的容量。因此，我们的研究结果提供了一个新的参数范围，RM实现这两个良好的研究渠道的能力。此外，我们的结果意味着，对于每个$k> 0$（实际上，我们可以得到$k = Omegaleft（sqrt{frac{log m}{m}}
8）r<（1/2-n）m的RM码可以以很高的概率纠正1-o（1）$的一部分随机擦除。我们还表明，信息理论上，这样的代码可以处理一小部分的1/2-o（1）$随机错误的高概率。因此，例如，给定次数为0.499 m $多项式的噪声评估，即使评估的随机0.499 $部分被破坏，也可以以高概率对其进行插值。虽然$o（1）$项不是确保容量的正确项，但这些结果表明，这种度数的RM码在某种意义上接近于实现容量。
This work proves new results on the ability of binary Reed-Muller codes to decode from random errors and erasures. We obtain these results by proving improved bounds on the weight distribution of Reed-Muller codes of high degrees. Specifically, given weight $eta in (0,1)$ we prove an upper bound on the number of codewords of relative weight at most $eta$. We obtain new results in two different settings: for weights $eta < 1/2$ and for weights that are close to $1/2$.
Our new bounds on the weight distribution imply that RM codes with $m$ variables and degree $gamma m$, for some explicit constant $gamma$, achieve capacity for random erasures (i.e. for the binary erasure channel) and for random errors (for the binary symmetric channel). Earlier, it was known that RM codes achieve capacity for the binary symmetric channel for degrees $r = o(m)$. For the binary erasure channel it was known that RM codes achieve capacity for degree $o(m)$ or $r in [m/2 pm O(sqrt{m})]$. Thus, our result provide a new range of parameters for which RM achieve capacity for these two well studied channels. In addition, our results imply that for every $epsilon > 0$ (in fact we can get up to $epsilon = Omegaleft(sqrt{frac{log m}{m}}
ight)$) RM codes of degree $r<(1/2-epsilon)m$ can correct a fraction of $1-o(1)$ random erasures with high probability. We also show that, information theoretically, such codes can handle a fraction of $1/2-o(1)$ random errors with high probability. Thus, for example, given noisy evaluations of a degree $0.499m$ polynomial, it is possible to interpolate it even if a random $0.499$ fraction of the evaluations were corrupted, with high probability. While the $o(1)$ terms are not the correct ones to ensure capacity, these results show that RM codes of such degrees are in some sense close to achieving capacity.