Skip to main content

Reed-muller codes achieve capacity on erasure channels

Publication ,  Journal Article
Kudekar, S; Kumar, S; Mondelli, M; Pfister, HD; Sasoǧlu, E; Urbanke, RL
Published in: IEEE Transactions on Information Theory
July 1, 2017

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.

Duke Scholars

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

July 1, 2017

Volume

63

Issue

7

Start / End Page

4298 / 4316

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kudekar, S., Kumar, S., Mondelli, M., Pfister, H. D., Sasoǧlu, E., & Urbanke, R. L. (2017). Reed-muller codes achieve capacity on erasure channels. IEEE Transactions on Information Theory, 63(7), 4298–4316. https://doi.org/10.1109/TIT.2017.2673829
Kudekar, S., S. Kumar, M. Mondelli, H. D. Pfister, E. Sasoǧlu, and R. L. Urbanke. “Reed-muller codes achieve capacity on erasure channels.” IEEE Transactions on Information Theory 63, no. 7 (July 1, 2017): 4298–4316. https://doi.org/10.1109/TIT.2017.2673829.
Kudekar S, Kumar S, Mondelli M, Pfister HD, Sasoǧlu E, Urbanke RL. Reed-muller codes achieve capacity on erasure channels. IEEE Transactions on Information Theory. 2017 Jul 1;63(7):4298–316.
Kudekar, S., et al. “Reed-muller codes achieve capacity on erasure channels.” IEEE Transactions on Information Theory, vol. 63, no. 7, July 2017, pp. 4298–316. Scopus, doi:10.1109/TIT.2017.2673829.
Kudekar S, Kumar S, Mondelli M, Pfister HD, Sasoǧlu E, Urbanke RL. Reed-muller codes achieve capacity on erasure channels. IEEE Transactions on Information Theory. 2017 Jul 1;63(7):4298–4316.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

July 1, 2017

Volume

63

Issue

7

Start / End Page

4298 / 4316

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing