Excellent codes from modular curves

ABSTRACT

We introduce a new construction of error-correcting codes from algebraic curves over finite fields. Modular curves of genus g\ra\infty over a field of size q_0^2 yield nonlinear codes more efficient than the linear Goppa codes obtained from the same curves. These new codes now have the highest asymptotic transmission rates known for certain ranges of alphabet size and error rate. Both the theory and possible practical use of these new record codes require the development of new tools. On the theoretical side, establishing the transmission rate depends on an error estimate for a theorem of Schanuel applied to the function field of an asymptotically optimal curve. On the computational side, actual use of the codes will hinge on the solution of new problems in the computational algebraic geometry of curves.

REFERENCES

• 1: V. G. Drinfeld and S. G. Vlaadut. Thenumber of points of an algebraic curve. Functional Anal. Appl. 17:53-54, 1983 (translated from the Russian paper in Funktsional. Anal. i Prilozhen).
• 2: N. D. Elkies. Explicit modular towers. In Proceedings of the Thirty-Fifth Annual Allerton Conference on Communication, Control and Computing, pages 23-32. Univ. of Illinois at Urbana-Champaign, 1998. http://arXiv.org/abs/math/0103107
• 3: Noam D. Elkies, Shimura Curve Computations, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.1-47, June 21-25, 1998
• 4: N. D. Elkies. Explicit towers of Drinfeld modular curves. In Proceedings of the Third European Congress of Mathematics, Barcelona 2000. http://arXiv.org/abs/math/0005140
• 5: A. Garcia and H. Stichtenoth. A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound. Invent. Math. 121:211-233, 1995.
• 6: A. Garcia and H. Stichtenoth. On the asymptotic behaviour of some towers of function fields over finite fields. J. Number Theory 61:248-273, 1996.
• 7: A. Garcia and H. Stichtenoth. Asymptotically good towers of function fields over finite fields. C. R. Acad. Sci. Paris I 322:1067-1070, 1996.
• 8: A. Garcia, H. Stichtenoth, and M. Thomas. On towers and composita of towers of function fields over finite fields. Finite Fields and their Appl. 3:257-273, 1997.
• 9: V. D. Goppa. Codes on algebraic curves. Soviet Math. Dokl. 24:170-172, 1981.
• 10: V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inform. Theory 45:1757-1767, 1999.
• 11: Y. Ihara: Some remarks on the number of rational points of algebraic curves over finite fields. J. Fac. Sci. Tokyo 28:721-724, 1981.
• 12: S. A. DiPippo. Spaces of Rational Functions on Curves Over Finite Fields. Ph.D. Thesis, Harvard, 1990.
• 13: S. H. Schanuel. Heights in number fields. Bull. Soc. Math. France 107:433-449, 1979.
• 14: J.-P. Serre. Lectures on the Mordell-Weil Theorem (trans. M. Brown). F. Vieweg & Sohn, Braunschweig 1989.
• 15: A. M. Shokrollahi and H. Wasserman. List decoding of algebraic-geometric codes. IEEE Trans. Inform. Theory 45:432-437, 1999.
• 16: M.A. A. Tsfasman , S.G. Vladut, Algebraic-Geometric Codes, Kluwer Academic Publishers, Norwell, MA, 1991
• 17: M. A. Tsfasman, S. G. Vladut, and T.Zink. Modular curves, Shimura curves and Goppa codes better than the Varshamov-Gilbert bound. Math. Nachr. 109:21-28, 1982.
• 18: D. Wan. Heights and Zeta Functions in Function Fields. In The Arithmetic of Function Fields, pages 455-463. W. de Gruyter, Berlin, 1992.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Experimentation, Performance