Reed-Muller Codes Achieve Capacity on Erasure Channels

In this talk, we show that a sequence of Reed-Muller codes with increasing length achieves capacity on the binary erasure channel if the sequence of rates converges.  This possibility was first discussed by Dumer and Farrell in 1994 but has been settled so far only for some cases where the limiting code rate is 0 or 1.  In fact, our primary technical result is quite general and also includes extended primitive narrow-sense BCH codes and all other affine-invariant codes.  The method can be seen as 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, this method requires only that the codes are highly symmetric. 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. This also provides a rare example in information theory where symmetry alone implies near-optimal performance.  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.

 

This work is joint with Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Eren Sasoglu, Ruediger Urbanke.