Cyclotomic function fields, Artin–Frobenius automorphisms, and list error correction with optimal rate
Venkatesan Guruswami · Algebra & Number Theory · 2010
Algebraic error-correcting codes that achieve the optimal trade-off between rate and fraction of errors corrected (in the model of list decoding) were recently constructed by a careful "folding" of the Reed-Solomon code.The "low-degree" nature of this folding operation was crucial to the list decoding algorithm.We show how such folding schemes useful for list decoding arise out of the Artin-Frobenius automorphism at primes in Galois extensions.Using this approach, we construct new folded algebraic-geometric codes for list decoding based on cyclotomic function fields with a cyclic Galois group.Such function fields are obtained by adjoining torsion points of the Carlitz action of an irreducible M ∈ ކ q [T ].The Reed-Solomon case corresponds to the simplest such extension (corresponding to the case M = T ).In the general case, we need to descend to the fixed field of a suitable Galois subgroup in order to ensure the existence of many degree 1 places that can be used for encoding.Our methods shed new light on algebraic codes and their list decoding, and lead to new codes with optimal trade-off between rate and error correction radius.Quantitatively, these codes provide list decoding (and list recovery/soft decoding) guarantees similar to folded Reed-Solomon codes but with an alphabet size that is only polylogarithmic in the block length.In comparison, for folded RS codes, the alphabet size is a large polynomial in the block length.This has applications to fully explicit (with no brute-force search) binary concatenated codes for list decoding up to the Zyablov radius.