Reed–Muller Codes Achieve Capacity on Erasure Channels

DOI10.1109/TIT.2017.2673829MaRDI QIDQ5358571zbMATH OpenFDO

Authors Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry David Pfister, Eren Şaşoğlu, Ruediger Urbanke

Publication date 21 September 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.04689

Mathematics Subject Classification ID

Measures of information, entropy (94A17)

Abstract: We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing blocklength and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone boolean functions and the area theorem for extrinsic information transfer functions.

Cited in

(12)

• The all-or-nothing phenomenon in sparse linear regression
• Towards a proof of the Fourier-entropy conjecture?
• 2-neighbour-transitive codes with small blocks of imprimitivity
• Reed–Muller Codes for Random Erasures and Errors
• Using Reed–Muller ${\hbox{RM}}\,(1, m)$ Codes Over Channels With Synchronization and Substitution Errors
• Reed-Muller Codes
• Hypercontractivity for global functions and sharp thresholds
• New classes of affine-invariant codes sandwiched between Reed-Muller codes
• Neural decoders with permutation invariant structure
• Stochastic secret sharing with 1-bit shares and applications to MPC
• Coxeter codes: extending the Reed-Muller family
• Influences of some families of error-correcting codes

This page was built for publication: Reed–Muller Codes Achieve Capacity on Erasure Channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5358571)