Book contents
- Frontmatter
- Contents
- Preface
- 1Ramsey classes: examples and constructions
- 2Recent developments in graph Ramsey theory
- 3Controllability and matchings in random bipartite graphs
- 4Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5Randomly generated groups
- 6Curves over finite fields and linear recurring sequences
- 7New tools and results in graph minor structure theory
- 8Well quasi-order in combinatorics: embeddings and homomorphisms
- 9Constructions of block codes from algebraic curves over finite fields
- References
9 - Constructions of block codes from algebraic curves over finite fields
Published online by Cambridge University Press: 05 July 2015
Book contents
- Frontmatter
- Contents
- Preface
- 1Ramsey classes: examples and constructions
- 2Recent developments in graph Ramsey theory
- 3Controllability and matchings in random bipartite graphs
- 4Some old and new problems in combinatorial geometry I: around Borsuk's problem
- 5Randomly generated groups
- 6Curves over finite fields and linear recurring sequences
- 7New tools and results in graph minor structure theory
- 8Well quasi-order in combinatorics: embeddings and homomorphisms
- 9Constructions of block codes from algebraic curves over finite fields
- References
Summary
Abstract
Since the discovery of algebraic geometry codes by Goppa in 1978–1982, mathematicians have been looking for other constructions of block codes from algebraic curves or varieties of higher dimension. In this survey article, we present various constructions of block codes from algebraic curves. As there is a one-to-one correspondence between algebraic curves and function fields, we adopt the function field language throughout this paper; this is advantageous for most of the constructions in this paper.
1 Introduction
The discovery of algebraic geometry codes by Goppa has greatly stimulated research in both coding theory and number theory [1, 4, 5, 6, 7, 8, 9, 12, 16, 21, 24, 25, 33, 34, 44]. As there have been many other constructions of block codes via algebraic geometry, henceforth Goppa's algebraic geometry codes are called the Goppa geometric codes.
The major breakthrough of the Goppa geometric codes is that they improved the long-standing benchmark bound, the Gilbert–Varshamov (GV, for short) bound. Before the Goppa geometric codes, the GV bound had remained for more than 30 years and many people even conjectured that the GV bound is optimal and could not be improved.
The Goppa geometric codes are a natural generalization of the well-known Reed–Solomon codes from projective curves to algebraic curves of higher genus. Due to rich structures of algebraic function fields, there is a great potential to construct block codes via algebraic curves through other methods. Indeed, in the last few decades, various constructions of codes via algebraic curves have been found [2, 3, 8, 9, 17, 24, 26, 29, 37, 39, 40, 41, 42, 43, 44]. In this survey article, we present quite a few constructions of codes through algebraic curves. Many of these constructions have been discovered by the authors and their collaborators.
The paper is organised as follows. In Section 2, we present some preliminaries on codes and algebraic curves. Section 3 is devoted to various constructions of codes.
Information
- Type
- Chapter
- Information
- Surveys in Combinatorics 2015 , pp. 295 - 324Publisher: Cambridge University PressPrint publication year: 2015
References
[1] , Ray class fields of global function fields with many rational places, Acta Arith. 95, 97–122, 2000.
[2] , , and , Some new codes from al-gebraic curves, IEEE Trans. Inform. Theory 46, No. 7, 2638–2642, 2000.
[3] , Excellent nonlinear codes from modular curves, in STOC'01: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Hersonissos, Crete, 200–208, 2001.
[4] , , and , On maximal curves, J. Number Theory 67, 29–51, 1997.
[5] and , A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladuţ bound, Invert. Math. 121, 211–222, 1995.
[6] , and , On subfields of the Hermitian function field, Compositio Math. 120, 137–170, 2000.
[7] der Geer and der Vlugt, Tables of curves with many points, Math. Comp. 69, 797–810, 2000.
[8] , Codes on algebraic curves, Soviet Math. Dokl. 24, 170–172, 1981.
[9] , Algebraic-geometric codes, Izv. Akad. Nauk. SSSR Ser. Mat. 46, 762–781, 1982.
[10] , Geometry and Codes, Kluwer, Dordrecht, 1988.
[11] , and , Function-field codes, Appl. Algebra Engrg. Comm. Comput. 19, 201–211, 2008.Google Scholar
[12] and , Group codes on certain algebraic curves with many rational points, AAECC 1, 67–77, 1990.
[13] , Explicit class field theory for rational function fields, Trans. Amer. Math. Soc. 189, 77–91, 1974.
[14] , , and , Algebraic Curves over a Finite Field, Princeton Series in Applied Mathematics, Princeton Univ. Press, 2008.
[15] , , and , Algebraic Geometry Codes, Handbook in Coding Theory, Vol. 1, Elsevier, Amsterdam, 871–961, 1998.
[16] , Some remarks on the number of rational points of algebraic curves over finite fields, J. Fac. Sci. Tokyo 28, 721–724, 1981.
[17] , , and , New binary linear codes from algebraic curves, IEEE Trans. Inform. Theory 48, 285–287, 2002.
[18] and , Coding Theory: A First Course, Cambridge University Press, Cambridge, 2004.
[19] and , The Theory of Error-Correcting Codes, Amsterdam, the Netherlands: North Holland, 1977.
[20] , Algebraic Curves over Finite Fields, Cambridge Tracts in Math., Vol. 97, Cambridge University Press, Cambrige, 1991.
[21] and , Towers of global function fields with asymptotically many rational places and an improvement on the Gilbert-Varshamov bound, Math. Nach. 195, 171–186, 1998.
[22] and , Rational Points on Curves over Finite Fields: Theory and Applications, LMS 285, Cambridge, 2001.
[23] and , Algebraic Geometry in Coding Theory and Cryptography, Princeton University Press, 2009.
[24] , , and , A new construction of algebraic-geometry codes, Appl. Algebra Engr. Comm. Comput. 9, 373–381, 1999.
[25] , , and , Which linear codes are algebraic-geometric? IEEE Trans. Inform. Theory 37, 583–602, 1991.
[26] and , Constructing codes from algebraic curves, IEEE Trans. Inform. Theory 45, 2502–2505, 1999.
[27] and , A characterization of Hermitian function fields over finite fields, J. Reine Angew. Math. 457, 185–188, 1994.
[28] , Rational Points on Curves over Finite Fields, Lecture Notes, Harvard University, 1985.
[29] and , Excellent non-linear codes from al-gebraic function fields, IEEE Trans. Inform. Theory 51, 4044–4046, 2005.
[30] , Algebraic Function Fields and Codes, Graduate Texts in Mathematics 254, Springer Verlag, 2009.
[31] and , Algebraic-Geometric Codes, Dordrecht, The Netherlands: Kluwer, 1991.
[32] , , and , Algebraic Geometric Codes: Basis Notions, American Mathematical Soc., 1990.
[33] and , Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound, Math. Nach. 109, 21–28, 1982.
[34] , Algebraic-geometry codes with aasymptotic parameters better that the Gilbert–Varshamov and the Tsfasman–Vladuţ–Zink bounds, IEEE Trans. Inform. Theory 47, 347–352, 2001.
[35] , Constructions of codes from residue rings of polynomials, IEEE Trans. Inform. Theory 48, 2995–2997, 2002.
[36] , Nonlinear codes from algebraic curves improving the Tsfasman-Vladuf-Zink bound, IEEE Trans. Inform. Theory 49, 1653–1657, 2003.
[37] , Linear codes from narrow ray class groups of algebraic curves, IEEE Trans. Inform. Theory 50, No. 3, 541–543, 2004.
[38] , Goppa geometric codes achieving the Gilbert-Varshamov bound, IEEE Trans. Inform. Theory 51, 259–264, 2005.
[39] , Asymptotically good nonlinear codes from algebraic curves, IEEE Trans. Inform. Theory 57, No. 9, 5991–5995, 2011.
[40] and , A class of linear codes with good parameters from algebraic curves, IEEE Trans. Inform. Theory 46, No. 4, 1527–1532, 2000
[41] , , and , Constructions of algebraic-geometry codes, IEEE Trans. Inform. Theory 45, No. 4, 1186–1193, 1999.
[42] , , and , A construction of algebraic-geometry codes, IEEE Trans. Inform. Theory 45, No. 7, 2498–2501, 1999.
[43] and , New linear codes and algebraic function fields over finite fields, IEEE Trans. Inform. Theory 53, No. 12, 4822–4825, 2007.
[44] and , Construction of global function fields from linear codes and vice versa, Trans. Amer. Math. Soc. 361, 1333–1349, 2009.
Accessibility standard: Unknown
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
Accessibility compliance for the PDF of this chapter is currently unknown and may be updated in the future.