Codes on Algebraic Curves

This is a self-contained introduction to algebraic curves over finite fields and geometric Goppa codes. There are four main divisions in the book. The first is a brief exposition of basic concepts and facts of the theory of error-correcting codes (Part I). The second is a complete presentation of the theory of algebraic curves, especially the curves defined over finite fields (Part II). The third is a detailed description of the theory of classical modular curves and their reduction modulo a prime number (Part III). The fourth (and basic) is the construction of geometric Goppa codes and the production of asymptotically good linear codes coming from algebraic curves over finite fields (Part IV). The theory of geometric Goppa codes is a fascinating topic where two extremes meet: the highly abstract and deep theory of algebraic (specifically modular) curves over finite fields and the very concrete problems in the engineering of information transmission. At the present time there are two essentially different ways to produce asymptotically good codes coming from algebraic curves over a finite field with an extremely large number of rational points. The first way, developed by M. A. Tsfasman, S. G. Vladut and Th. Zink [210], is rather difficult and assumes a serious acquaintance with the theory of modular curves and their reduction modulo a prime number. The second way, proposed recently by A. This book provides a self-contained introduction to the theory of error-correcting codes and related topics in number theory, Algebraic Geometry and the theory of Sphere Packings. The material is presented in an easily understandable form. This book is devoted to geometric Goppa codes; the recently discovered areas which combines Coding Theory, Algebraic Geometry, Number Theory, and Theory of Sphere Packings. It has an interdisciplinary nature and demonstrates the close interconnection of Coding Theory with various classical areas of mathematics. There are four main themes in the book. The first is a brief exposition of the basic concepts and facts of error-correcting code theory. The second is a complete presentation of the theory of algebraic curves; especially the curves defined over finite fields. The third is a detailed description of the theory of elliptic and modular codes, and their reductions modulo a prime number. The fourth is a construction of geometric Gappa codes producing rather long linear codes with very good parameters coming from algebraic curves, and with a lot of rational points. The aim of the book is to present these themes in a simple, easily understandable manner, and explain their close interconnection. At the same time the book introduces the reader to topics which are at the forefront of current research. Front Matter....Pages i-xiii Front Matter....Pages 1-1 Codes and Their Parameters....Pages 3-23 Bounds on Codes....Pages 25-39 Examples and Constructions....Pages 41-67 Front Matter....Pages 69-69 Algebraic Curves....Pages 71-101 Curves over a Finite Field....Pages 103-142 Counting Points on Curves over Finite Fields....Pages 143-172 Front Matter....Pages 173-173 Elliptic Curves....Pages 175-192 Classical Modular Curves....Pages 193-217 Reductions of Modular Curves....Pages 219-240 Front Matter....Pages 241-241 Constructions and Properties....Pages 243-255 Examples....Pages 257-288 Decoding Geometric Goppa Codes....Pages 289-314 Bounds....Pages 315-322 Back Matter....Pages 323-350