A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
复制标题
Reed-Muller 码在对称信道上实现香农容量的证明
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Colin Sandon
中科院分区：
文献类型：
--
作者：
E. Abbe;Colin Sandon
1948年，香农用概率论证明了存在一种码，它可以达到由信道容量定义的最大速率。1954年，Muller和Reed引入了一种简单的确定性码结构，不久之后就被用于实现信道容量。在过去的几十年里，建立这个猜想取得了重大进展，涉及离散数学的各个分支，如组合边界，尖锐的阈值，超收缩性，添加剂组合数学和极化理论。特别地，擦除通道的特殊情况由Kudekar等人解决，依赖于Bourgain-Kalai的对称单调性质的尖锐阈值定理。然而，错误通道的主要情况仍然不稳定，特别是由于其性质是非单调的，并且缺乏获得快速局部错误衰减到容量的技术，尽管里夫斯-菲斯特的局部错误界限显着消失。本文结束了该猜想的证明。主要成分是一个新的递归增强编码框架，其中码字是通过对“子空间-向日葵”结构的聚合限制来解码的，类似于Erdens-Rado 1960的结构。向日葵花瓣之间的依赖关系用布尔傅立叶分析方法处理，并使用一个列表解码参数，该参数的权值由Sberlo-Shpilka定义，以控制全局误差和局部误差.对于局部误差，而单调性不适用，我们表明，一个“弱阈值”的结果仍然保持使用单独的对称性。这特别给出了局部误差结果消失的缩短和收紧的论证，并且与先前的工作一起，它还暗示了RM码在纯态经典量子信道上的强窃听保密性。
In 1948, Shannon used a probabilistic argument to show that there exist codes achieving a maximal rate defined by the channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major progress was made towards establishing this conjecture over the last decades, with various branches of discrete mathematics involved such as combinatorial bounds, sharp thresholds, hypercontractivity, additive combinatorics and polarization theory. In particular, the special case of the erasure channel was settled by Kudekar at al., relying on Bourgain-Kalai’s sharp threshold theorem for symmetric monotone properties. The main case of error channels remained however unsettled, due in particular to the property being non-monotone and the lack of techniques to obtain fast local error decay up to capacity, despite the notable vanishing bound on the local error from Reeves-Pfister. This paper closes the conjecture’s proof. The main ingredient is a new recursive boosting framework for coding, where codewords are decoded by aggregating restrictions on a ‘subspace-sunflower’ structure, analogous to the structure from Erdős-Rado 1960. The dependencies between the sunflower petals are handled with an $L_{2}$ and $L_{4}$ Boolean Fourier analysis, and a list-decoding argument with a weight enumerator bound from Sberlo-Shpilka is used to control the global error from the local one. For the local error, while monotonicity does not apply, we show that a ‘weak threshold’ result still holds using solely symmetries. This gives in particular a shortened and tightened argument for the vanishing local error result, and with prior works, it also implies the strong wire-tap secrecy of RM codes on pure-state classical-quantum channels.
BEC 和 BSC 通道上 Reed-Muller 码的近乎最优缩放
DOI：
--
发表时间：
2018
期刊：
2018 IEEE Int. Symp. Inf. Theory (ISIT
影响因子：
--
作者：
Hassani, Hamed;Kudekar, Shrinivas;Ordentlich, Or;Polyanskiy, Yury;Urbanke, Rudiger
通讯作者：
Urbanke, Rudiger
使用冗余代码约束解码 Reed Muller 代码
DOI：
10.1109/isit44484.2020.9174087
发表时间：
2020
期刊：
2020 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Lian, Mengke;Hager, Christian;Pfister, Henry D.
通讯作者：
Pfister, Henry D.