Reed–Muller codes achieve capacity on erasure channels

S. Kudekar, S. Kumar, M. Mondelli, H.D. Pfister, E. Sasoglu, R.L. Urbanke, IEEE Transactions on Information Theory 63 (2017) 4298–4316.


Journal Article | Published | English
Author
; ; ; ; ;
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 block length 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.
Publishing Year
Date Published
2017-07-01
Journal Title
IEEE Transactions on Information Theory
Volume
63
Issue
7
Page
4298-4316
ISSN
eISSN
IST-REx-ID

Cite this

Kudekar S, Kumar S, Mondelli M, Pfister HD, Sasoglu E, Urbanke RL. Reed–Muller codes achieve capacity on erasure channels. IEEE Transactions on Information Theory. 2017;63(7):4298-4316. doi:10.1109/tit.2017.2673829
Kudekar, S., Kumar, S., Mondelli, M., Pfister, H. D., Sasoglu, 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, Shrinivas, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, and Ridiger L. Urbanke. “Reed–Muller Codes Achieve Capacity on Erasure Channels.” IEEE Transactions on Information Theory 63, no. 7 (2017): 4298–4316. https://doi.org/10.1109/tit.2017.2673829.
S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Sasoglu, and R. L. Urbanke, “Reed–Muller codes achieve capacity on erasure channels,” IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4298–4316, 2017.
Kudekar S, Kumar S, Mondelli M, Pfister HD, Sasoglu E, Urbanke RL. 2017. Reed–Muller codes achieve capacity on erasure channels. IEEE Transactions on Information Theory. 63(7), 4298–4316.
Kudekar, Shrinivas, et al. “Reed–Muller Codes Achieve Capacity on Erasure Channels.” IEEE Transactions on Information Theory, vol. 63, no. 7, IEEE, 2017, pp. 4298–316, doi:10.1109/tit.2017.2673829.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1601.04689

Search this title in

Google Scholar