Math @ Duke

Publications [#326751] of Robert Calderbank
Papers Published
 Kumar, S; Calderbank, R; Pfister, HD, Beyond double transitivity: Capacityachieving cyclic codes on erasure channels,
2016 IEEE Information Theory Workshop, ITW 2016
(October, 2016),
pp. 241245, ISBN 9781509010905 [doi]
(last updated on 2018/07/20)
Abstract: © 2016 IEEE. Recently, sequences of errorcorrecting codes with doublytransitive permutation groups were shown to achieve capacity on erasure channels under symbolwise maximum a posteriori (MAP) decoding. From this, it follows that ReedMuller and primitive narrowsense BCH codes achieve capacity in the same setting. In this article, we extend this result to a large family of cyclic codes by considering codes whose permutation groups satisfy a condition weaker than double transitivity. The article combines two simple technical contributions. First, we show that the transition width of a monotone boolean function is O(1/log k), where k is the size of the smallest orbit induced by its symmetry group. The proof is based on Talagrand's lower bound on influences for monotone boolean functions. Second, we consider the extrinsic information transfer (EXIT) function of an Fqlinear cyclic code whose blocklength N divides q t 1 and is coprime with q1. We show that this EXIT function is a monotone boolean function whose symmetry group contains no orbits of size smaller than the smallest prime divisor of t. Combining these, we show that sequences of cyclic codes, whose blocklengths satisfy the above conditions, achieve capacity on the qary erasure channel if all prime divisors of t tend to infinity.


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

