期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 67, 期 12, 页码 8034-8050出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3116663
关键词
Reed-Muller codes; polarization
The paper investigates a new type of linear code that can correct random errors with high probability under a certain level of data loss. This differs from the performance of traditional Reed-Muller codes.
This paper considers delta-almost Reed-Muller codes, i.e., linear codes spanned by evaluations of all but a delta fraction of monomials of degree at most d. It is shown that for any delta > 0 and any epsilon > 0, there exists a family of delta-almost Reed-Muller codes of constant rate that correct 1/2-epsilon fraction of random errors with high probability. For exact Reed-Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed-Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC '15). Our proof is based on the recent polarization result for Reed-Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed-Muller code entropies.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据