Math @ Duke

Publications [#319313] of Henry Pfister
Papers Published
 Kudekar, S; Pfister, HD; Kumar, S; Şaşoǧlu, E; Mondelli, M; Urbanke, R, ReedMuller codes achieve capacity on erasure channels,
Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 1921June2016
(June, 2016),
pp. 658669, ISBN 9781450341325 [doi]
(last updated on 2018/02/24)
Abstract: © 2016 ACM. 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 nearoptimal performance. An important consequence of this result is that a sequence of ReedMuller 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 affineinvariant codes and, thus, to all extended primitive narrowsense BCH codes. This is used to resolve, in the affirmative, the existence question for capacityachieving 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

