Reed-Muller codes achieve capacity on erasure channels

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 block lengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In a nutshell, 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 affine-invariant codes and, thus, to all extended primitive narrow-sense BCH codes. This is used to resolve, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proofs are the sharp threshold property for symmetric monotone boolean functions and the area theorem for extrinsic information transfer (EXIT) functions.

References

1. E. Abbe, A. Shpilka, and A. Wigderson. Reed-Muller codes for random erasures and errors. In Proc. of the Annual ACM Symp. on Theory of Comp., STOC ’15, pages 297–306, New York, NY, USA, 2015. ACM.
2. E. Abbe, A. Shpilka, and A. Wigderson. Reed-Muller codes for random erasures and errors. IEEE Trans. Inform. Theory, 61(10):5229–5252, Oct 2015.
3. D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435(7043):759–764, 2005.
4. R. Ahlswede and G. Dueck. Good codes can be produced by a few permutations. IEEE Trans. Inform. Theory, 28(3):430–443, May 1982.
5. E. Arıkan. A performance comparison of polar codes and Reed-Muller codes. IEEE Commun. Letters, 12(6):447–449, June 2008.
6. E. Arıkan. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans. Inform. Theory, 55(7):3051–3073, July 2009.
7. E. Arıkan. A survey of Reed-Muller codes from polar coding perspective. In Proc. IEEE Inform. Theory Workshop, pages 1–5, Jan 2010.
8. A. Ashikhmin, G. Kramer, and S. ten Brink. Extrinsic information transfer functions: model and erasure channel properties. IEEE Trans. Inform. Theory, 50(11):2657–2674, Nov. 2004.
9. C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding: Turbo-codes. In Proc. IEEE Int. Conf. Commun., volume 2, pages 1064–1070, Geneva, Switzerland, May 1993. IEEE.
10. S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
11. J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson, and N. Linial. The influence of variables in product spaces. Israel Journal of Mathematics, 77(1-2):55–64, 1992.
12. J. Bourgain and G. Kalai. Influences of variables and threshold intervals under group symmetries. Geometric & Functional Analysis, 7(3):438–461, 1997.
13. P. Camion, C. Carlet, P. Charpin, and N. Sendrier. On correlation-immune functions. In Advances in Cryptology–CRYPTO’91, pages 86–100. Springer, 1992.
14. A. Canteaut, C. Carlet, P. Charpin, and C. Fontaine. On cryptographic properties of the cosets of R(1, m). IEEE Trans. Inform. Theory, 47(4):1494–1513, 2001.
15. C. Carlet, D. K. Dalai, K. C. Gupta, and S. Maitra. Algebraic immunity for cryptographically significant boolean functions: analysis and construction. IEEE Trans. Inform. Theory, 52(7):3105–3121, 2006.
16. C. Carlet and P. Gaborit. On the construction of balanced boolean functions with a good algebraic immunity. In Proc. IEEE Int. Symp. Inform. Theory, pages 1101–1105, Sept 2005.
17. J. Coffey and R. Goodman. Any code of which we cannot think is good. IEEE Trans. Inform. Theory, 36(6):1453–1461, Nov 1990.
18. A. Coja-Oghlan. The asymptotic k-SAT threshold. In Proc. of the Annual ACM Symp. on Theory of Comp., STOC ’14, pages 804–813, New York, NY, USA, 2014. ACM.
19. D. J. Costello, Jr. and G. D. Forney, Jr. Channel coding: The road to channel capacity. Proc. of the IEEE, 95(6):1150–1177, June 2007.
20. P. Delsarte, J. Goethals, and F. M. Williams. On generalized Reed-Muller codes and their relatives. Inform. and Control, 16(5):403–442, 1970.
21. F. Didier. A new upper bound on the block error probability after decoding over the erasure channel. IEEE Trans. Inform. Theory, 52(10):4496–4503, Oct 2006.
22. F. Didier and J.-P. Tillich. Computing the algebraic immunity efficiently. In Fast Software Encryption, pages 359–374. Springer, 2006.
23. J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k. In Proc. of the Annual ACM Symp. on Theory of Comp., STOC ’15, pages 59–68, New York, NY, USA, 2015. ACM.
24. I. Dinur and S. Safra. On the hardness of approximating minimum vertex cover. Ann. of Math., pages 439–485, 2005.
25. I. Dumer. Recursive decoding and its performance for low-rate Reed-Muller codes. IEEE Trans. Inform. Theory, 50(5):811–823, May 2004.
26. I. Dumer. Soft-decision decoding of Reed-Muller codes: a simplified algorithm. IEEE Trans. Inform. Theory, 52(3):954–963, March 2006.
27. I. Dumer and P. G. Farrell. Erasure correction performance of linear block codes. In Algebraic Coding, pages 316–326. Springer, 1994.
28. I. Dumer and K. Shabunov. Soft-decision decoding of Reed-Muller codes: recursive lists. IEEE Trans. Inform. Theory, 52(3):1260–1266, March 2006.
29. E. Friedgut and J. Bourgain. Sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc., 12(4):1017–1054, 1999.
30. E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124(10):2993–3002, 1996.
31. R. G. Gallager. Low-Density Parity-Check Codes. The M.I.T. Press, Cambridge, MA, USA, 1963.
32. P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson. Self-testing/correcting for polynomials and for approximate functions. In Proc. of the Annual ACM Symp. on Theory of Comp., STOC ’91, pages 33–42, New York, NY, USA, 1991. ACM.
33. P. Gemmell and M. Sudan. Highly resilient correctors for polynomials. Information processing letters, 43(4):169–174, 1992.
34. B. Gérard and J.-P. Tillich. Using tools from error correcting theory in linear cryptanalysis. Adv. Linear Cryptanalysis of Block and Stream Ciphers, 7:87, 2011.
35. E. Grigorescu, T. Kaufman, and M. Sudan. 2-transitivity is insufficient for local testability. In Annual IEEE Conf. on Comp. Complex., pages 259–267, June 2008.
36. W. C. Huffman and V. Pless. Fundamentals of error-correcting codes. Cambridge University Press, 2003.
37. G. Kalai and S. Safra. Threshold phenomena and influence with some perspectives from mathematics, computer science, and economics. Comp. Complexity and Stat. Phy., Santa Fe Institute Studies in Sci. of Complexity, 19517738, 2005.
38. T. Kasami, S. Lin, and W. W. Peterson. New generalizations of the Reed-Muller codes–I: Primitive codes. IEEE Trans. Inform. Theory, 14(2):189–199, Mar 1968.
39. T. Kasami and N. Tokura. On the weight structure of Reed-Muller codes. IEEE Trans. Inform. Theory, 16(6):752–759, Nov 1970.
40. T. Kasami, N. Tokura, and S. Azumi. On the weight enumeration of weights less than 2.5d of Reed-Muller codes. Inform. and Control, 30(4):380 – 395, 1976.
41. T. Kaufman, S. Lovett, and E. Porat. Weight distribution and list-decoding size of Reed-Muller codes. IEEE Trans. Inform. Theory, 58(5):2689–2696, May 2012.
42. T. Kaufman and M. Viderman. Locally testable vs. locally decodable codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 670–682. Springer, 2010.
43. S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. ¸ Sa¸so˘ glu, and R. L. Urbanke. Reed-Muller codes achieve capacity on erasure channels. Submitted to IEEE Trans. Inform. Theory, 2016. {Online}. Available: http://arxiv.org/pdf/1601.04689.pdf.
44. S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, and R. L. Urbanke. Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS Channels. Submitted to ISIT, 2016.
45. S. Kudekar, T. Richardson, and R. L. Urbanke. Spatially coupled ensembles universally achieve capacity under belief propagation. IEEE Trans. Inform. Theory, 59(12):7761–7813, Dec. 2013.
46. S. Kudekar, T. J. Richardson, and R. L. Urbanke. Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC. IEEE Trans. Inform. Theory, 57(2):803–834, Feb. 2011.
47. S. Kumar, A. J. Young, N. Macris, and H. D. Pfister. Threshold saturation for spatially-coupled LDPC and LDGM codes on BMS channels. IEEE Trans. Inform. Theory, 60(12):7389–7415, Dec. 2014.
48. M. Lentmaier, A. Sridharan, D. J. Costello, and K. S. Zigangirov. Iterative decoding threshold analysis for LDPC convolutional codes. IEEE Trans. Inform. Theory, 56(10):5274–5289, Oct. 2010.
49. S. Lin. RM codes are not so bad. In Proc. IEEE Inform. Theory Workshop, June 1993. Invited talk.
50. S. Lin and D. J. Costello, Jr. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ, USA, 2nd edition, 2004.
51. ISBN-13: 978-0130426727.
52. M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Efficient erasure correcting codes. IEEE Trans. Inform. Theory, 47(2):569–584, Feb. 2001.
53. D. J. C. MacKay. Good error-correcting codes based on very sparse matrices. IEEE Trans. Inform. Theory, 45(2):399–431, March 1999.
54. F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes, volume 16. Elsevier, 1977.
55. G. A. Margulis. Probabilistic characteristics of graphs with large connectivity. Problems of Inform. Transm., 10(2):101–108, 1974.
56. C. Méasson, A. Montanari, T. J. Richardson, and R. Urbanke. The generalized area theorem and some of its consequences. IEEE Trans. Inform. Theory, 55(11):4793–4821, Nov. 2009.
57. C. Méasson, A. Montanari, and R. L. Urbanke. Maxwell construction: The hidden bridge between iterative and maximum a posteriori decoding. IEEE Trans. Inform. Theory, 54(12):5277–5307, Dec. 2008.
58. M. Mondelli, S. H. Hassani, and R. L. Urbanke. From polar to Reed-Muller codes: A technique to improve the finite-length performance. IEEE Trans. Commun., 62(9):3084–3091, Sept 2014.
59. D. Muller. Application of Boolean algebra to switching circuit design and to error detection. IRE Tran. on Electronic Computers, EC-3(3):6–12, Sept 1954.
60. O. Ordentlich and U. Erez. Cyclic-coded integer-forcing equalization. IEEE Trans. Inform. Theory, 58(9):5804–5815, 2012.
61. I. Reed. A class of multiple-error-correcting codes and the decoding scheme. IRE Tran. on Information Theory, 4(4):38–49, September 1954.
62. T. J. Richardson and R. L. Urbanke. Modern Coding Theory. Cambridge University Press, New York, NY, 2008.
63. L. Russo. An approximate zero-one law. Prob. Th. and Related Fields, 61(1):129–139, 1982.
64. R. Saptharishi, A. Shpilka, and B. L. Volk. Efficiently decoding Reed-Muller codes from random errors. {Online}. Available: http://arxiv.org/abs/1503.09092v2, 2015.
65. R. Shaltiel and C. Umans. Simple extractors for all min-entropies and a new pseudo-random generator. In Proc. IEEE Symp. on the Found. of Comp. Sci., pages 648–657, 2001.
66. C. E. Shannon. A mathematical theory of communication. The Bell Syst. Techn. J., 27:379–423, 623–656, July / Oct. 1948.
67. V. M. Sidel’nikov and A. Pershakov. Decoding of Reed-Muller codes with a large number of errors. Problems of Inform. Transm., 28(3):80–94, 1992.
68. N. Sloane and E. Berlekamp. Weight enumerator for second-order Reed-Muller codes. IEEE Trans. Inform. Theory, 16(6):745–751, Nov 1970.
69. D. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42(6):1723–1731, Nov 1996.
70. A. Ta-Shma, D. Zuckerman, and S. Safra. Extractors from Reed-Muller codes. In Proc. IEEE Symp. on the Found. of Comp. Sci., pages 638–647, 2001.
71. M. Talagrand. Isoperimetry, logarithmic sobolev inequalities on the discrete cube, and margulis’ graph connectivity theorem. Geometric & Functional Analysis, 3(3):295–314, 1993.
72. M. Talagrand. On Russo’s approximate zero-one law. The Ann. of Prob., pages 1576–1587, 1994.
73. S. ten Brink. Convergence of iterative decoding. Electronic Letters, 35(10):806–808, May 1999.
74. J.-P. Tillich and G. Zémor. Discrete isoperimetric inequalities and the probability of a decoding error. Combinatorics, Probability and Computing, 9(05):465–479, 2000.
75. J.-P. Tillich and G. Zemor. The Gaussian isoperimetric inequality and decoding error probabilities for the Gaussian channel. IEEE Trans. Inform. Theory, 50(2):328–331, Feb 2004.
76. S. Yekhanin. Locally decodable codes. Found. Trends Theor. Comput. Sci., 7(4):169–174, 1992.
77. G. Zémor. Threshold effects in codes. In Algebraic Coding, pages 278–286. Springer, 1994.

Index Terms

• Mathematics of computing

  • Information theory

    • Coding theory

• Security and privacy

  • Cryptography

    • Mathematical foundations of cryptography