Artin automorphisms, cyclotomic function fields, and folded list-decodable codes

ABSTRACT

Algebraic codes that achieve list decoding capacity 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 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 ∈ F_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 one places that can be used for encoding.

Our methods shed new light on algebraic codes and their list decoding, and lead to new codes achieving list decoding capacity. 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.

REFERENCES

• 1: L. Carlitz. A class of polynomials. Trans. Amer. Math. Soc., 43:167--182, 1938.
• 2: G. Frey, M. Perret, and H. Stichtenoth. On the different of abelian extensions of global fields. In Coding theory and algebraic geometry, volume 1518 of Lecture Notes in Mathematics, pages 26--32. Springer Berlin/Heidelberg, 1992.
• 3: A. Garcia and H. Stichtenoth. A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vluadut bound. Inventiones Mathematicae, 121:211--222, 1995.
• 4: A. Garcia and H. Stichtenoth. On the asymptotic behavior of some towers of function fields over finite fields. Journal of Number Theory, 61(2):248--273, 1996.
• 5: V. Guruswami and A. Patthak. Correlated Algebraic-Geometric codes: Improved list decoding over bounded alphabets. Mathematics of Computation, 77(261):447--473, 2008.
• 6: V. Guruswami and A. Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory, 54(1):135--150, 2008.
• 7: V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
• 8: V. Guruswami and M. Sudan. On representations of algebraic-geometry codes. IEEE Transactions on Information Theory, 47(4):1610--1613, 2001.
• 9: D. R. Hayes. Explicit class field theory for rational function fields. Trans. Amer. Math. Soc., 189:77--91, March 1974.
• 10: M.-D. Huang and A. K. Narayanan. Folded algebraic geometric codes from Galois extensions. Personal communication, 2008.
• 11: J. Justesen. A class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory, 18:652--656, 1972.
• 12: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 13: D. A. Marcus. Number Fields. Springer-Verlag, New York Inc., 1977.
• 14: H. Niederreiter and C. P. Xing. Explicit global function fields over the binary field with many rational places. Acta Arithmetica, 75:383--396, 1996.
• 15: H. Niederreiter and C. P. Xing. Cyclotomic function fields, Hilbert class fields and global function fields with many rational places. Acta Arithmetica, 79:59--76, 1997.
• 16: Farzad Parvaresh , Alexander Vardy, Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.285-294, October 23-25, 2005 [doi>10.1109/SFCS.2005.29]
• 17: H.-G. Quebbemann. Cyclotomic Goppa codes. IEEE Trans. Info. Theory, 34:1317--1320, 1988.
• 18: M. Rosen. Number Theory in Function Fields. Springer-Verlag New York, Inc., 2002.
• 19: G. D. V. Salvador. Topics in the theory of algebraic function fields. Birkhauser, Boston, 2006.
• 20: B.-Z. Shen. A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate. IEEE Transactions on Information Theory, 39(1):239--241, 1993.
• 21: H. Stichtenoth. Algebraic function fields and codes. Springer, Berlin, 1993.
• 22: H. Stichtenoth. Transitive and self-dual codes attaining the Tsfasman-Vladut-Zink bound. IEEE Transactions on Information Theory, 52(5):2218--2224, 2006.
• 23: Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

General Terms:
Algorithms, Theory

Keywords:
algebraic-geometric codes, cyclotomic function fields, error-correcting codes, frobenius automorphism, galois extensions, list decoding capacity