Skip to main content

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

Publication ,  Conference
Kumar, S; Calderbank, R; Pfister, HD
Published in: 2016 IEEE Information Theory Workshop, ITW 2016
October 21, 2016

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 qt-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.

Duke Scholars

Published In

2016 IEEE Information Theory Workshop, ITW 2016

DOI

Publication Date

October 21, 2016

Start / End Page

241 / 245
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Kumar, S., Calderbank, R., & Pfister, H. D. (2016). Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels. In 2016 IEEE Information Theory Workshop, ITW 2016 (pp. 241–245). https://doi.org/10.1109/ITW.2016.7606832
Kumar, S., R. Calderbank, and H. D. Pfister. “Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels.” In 2016 IEEE Information Theory Workshop, ITW 2016, 241–45, 2016. https://doi.org/10.1109/ITW.2016.7606832.
Kumar S, Calderbank R, Pfister HD. Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels. In: 2016 IEEE Information Theory Workshop, ITW 2016. 2016. p. 241–5.
Kumar, S., et al. “Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels.” 2016 IEEE Information Theory Workshop, ITW 2016, 2016, pp. 241–45. Scopus, doi:10.1109/ITW.2016.7606832.
Kumar S, Calderbank R, Pfister HD. Beyond double transitivity: Capacity-achieving cyclic codes on erasure channels. 2016 IEEE Information Theory Workshop, ITW 2016. 2016. p. 241–245.

Published In

2016 IEEE Information Theory Workshop, ITW 2016

DOI

Publication Date

October 21, 2016

Start / End Page

241 / 245