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
. The
Reed–Solomon case corresponds to the simplest such extension (corresponding to the
case
).
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.
Keywords
list decoding, algebraic-geometric codes, Galois
extensions, Cyclotomic function fields, Reed–Solomon codes,
Frobenius automorphisms
