Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels

Conference Paper

Recently, sequences of error-correcting codes with doubly-transitive permutation groups were shown to achieve capacity on erasure channels under symbol-wise maximum a posteriori (MAP) decoding. From this, it follows that Reed-Muller and primitive narrow-sense 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 Fq-linear cyclic code whose blocklength N divides q -1 and is coprime with q-1. 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 q-ary erasure channel if all prime divisors of t tend to infinity. t

Full Text

Duke Authors

Cited Authors

  • Kumar, S; Calderbank, R; Pfister, HD

Published Date

  • October 21, 2016

Published In

  • 2016 Ieee Information Theory Workshop, Itw 2016

Start / End Page

  • 241 - 245

International Standard Book Number 13 (ISBN-13)

  • 9781509010905

Digital Object Identifier (DOI)

  • 10.1109/ITW.2016.7606832

Citation Source

  • Scopus