Algebraic-Geometric Codes

In this chapter we define principal notions of the theory of error-correcting codes (coding theory).

In this chapter we present several examples of codes. Each example is in fact a method to construct some family of codes, which (in some way or other) have rather good parameters. Since in many cases these families are predecessors of algebraic-geometric codes, we try to choose constructions that are easy to generalize in that direction.

The parameters of codes of large length n are of particular interest. As it happens quite often, if a problem has no easy answer for each particular n - just as our problem of finding out the best possible parameters of a code - passing to the limit for n → ∞ helps us to avoid “deviations” and to understand the behaviour of parameters better. In this chapter we state the problems rigorously and discuss those results that do not use algebraic-geometric codes. We shall return to asymptotic problems in Chapter 3.4, since asymptotic results are the best to demonstrate the power of algebraic-geometric methods.

Since many important questions of the geometry of curves are reduced to the calculation of ℓ (D) for various divisors D, an explicit expression of ℓ (D) plays an essential role in the theory of curves. Such an expression is given by the Riemann-Roch theorem which is the crucial result of the theory. To state it one should study differential forms on curves which are also useful in many other questions.

In Chapters 2.1 and 2.2 we have assumed the ground field k to be algebraically closed. In fact there are many cases in which the consideration of non-closed field such as Q or F _q is indispensable. For example, applying algebraic geometry to coding theory one should study curves over and their points with coordinates in F _q (such points are called F _q -rational). This section is devoted to the basic properties of curves over a non-closed (mainly finite) field and of their points. In Section 2.3.1 we give the definition and basic properties of rational points and divisors on a curve over a non-closed field; Section 2.3.2 contains basic properties of F _q -rational points on a curve over F _q , including the question about the number of points. In Section 2.3.3 we study the asymptotic behaviour of the number of F _q -rational points on a curve of high genus.

The study of non-singular curves is most important for the theory of curves. Nevertheless the study of singular curves is in many cases indispensable, since many smooth curves have singular models which are useful to prove some of their properties. For example, any curve has a plane (singular) model. In this chapter we discuss some properties of singular curves and describe their connections with smooth curves.

The idea of specialization (or reduction) of an algebraic variety is one of the most important for the geometry and especially for the arithmethic of algebraic varieties. By specialization one can obtain for example varieties over finite fields from varieties over algebraic number fields. The study of specialization using the language of quasi-projective varieties has many disadvantages. For these questions the language of schemes which is now the working language of algebraic geometry is much more adequate. One can consider the theory of schemes as the theory of algebraic varieties over arbitrary commutative rings. It should be also remarked that specialization was one of the main sources of the theory of schemes. Moreover the theory of schemes possesses a powerful technique for constructing algebraic varieties based on the notion of a representable functor. Many results of this book can not be obtained without use of moduli schemes. In this chapter we give a brief introduction to this theme.

These exist several essentially equivalent ways to construct linear codes starting from algebraic curves (and also from varieties of higher dimensions). For curves, the codes we get can be rather well described: we can bound their parameters and weight spectra, we understand the duality.

The general discussion of the previous chapter leaves us a bit in the air without examples of AG-codes for which it is possible to calculate the parameters and to compare them with codes obtained by non-algebraic-geometric constructions.

In this chapter we shall see that algebraic-geometric codes can be effectively decoded. In Section 3.3.1 we present a generalization of the decoding algorithm for Reed-Solomon codes (given in Section 1.2.1) to the case of an arbitrary curve; we call it the basic algorithm. Unfortunately the basic algorithm corrects g/2 errors less than one would like. The reason is that the Riemann-Roch theorem does not answer the question about the exact value of the dimension ℓ(D) for 0 ≤deg D ≤ 2g - 2. Section 3.3.2 is devoted to a modification of the basic algorithm leading in particular in Section 3.3.3 to algorithms decoding elliptic codes and many hyperelliptic codes (for some proper choice of the divisor) up to the half of the designed minimum distance. In Section 3.3.3 we also consider plane curves, for which it is possible to correct about g/4 errors more than in the general case, and also codes obtained from AG-codes by concatenation and field restriction.

The advantages of algebraic-geometric codes are most illustrious when we consider asymptotic problems. It turns out that the parameters of AG-codes constructed from families of algebraic curves are the better, the higher is (asymptotically) the ratio of the number of F _q -points on them to their genus. In Section 3.4.1 we establish the basic algebraic-geometric asymptotic bound, it is a line intersecting the Gilbert-Varshamov bound if q is large enough (thus ameliorating it on a segment). This result shows that highly un-random codes given by subtle algebraic geometry (modular curves are used) can be asymptotically better than random codes (recall that with probability one any linear code lies on the Gilbert-Varshamov bound). Then, in Section 3.4.2, we see that a probabilistic argument can be also applied to AG-codes themselves. An expurgation method leads (varying the divisor) to the expurgation bound. For small q this bound coincides with the Gilbert-Varshamov bound, and if q is large enough, it is a bit better than the maximum of the Gilbert-Varshamov bound and the basic AG-bound, smoothing the angles at points of their intersection. The basic AG-bound is constructive, applying to it various constructions of Section 1.2.3 we (in Section 3.4.3) ameliorate the polynomial Bloch-Ziablov bound for any q and δ. The progress due to AG-codes leads also to amelioration of some other asymptotic bounds (in Section 3.4.4). For non-linear codes ( q being large enough) it can be shown that the expurgation bound is not the best possible; moreover, the amelioration of the Gilbert bound can be extended to arbitrary alphabets. The bound for codes with polynomial construction and polynomial decoding is now also sometimes better than the Gilbert-Varshamov bound. The corresponding bounds for self-dual codes and for constant-weight codes can be also ameliorated by the use of AG-codes.

This chapter is devoted to codes on classical modular curves or, to put it more precisely, on those obtained from modular curves by reduction to a finite characteristic. As we have shown in Part 3, the properties of an AG-code constructed from a curve are determined by its geometry and arithmetic. Here we give some necessary information on the structure of modular curves and of their reductions, and some corollaries for codes on such curves.

Considering codes on reductions of classical modular curves we obtain codes over \({\mathbb{F}_{{p^2}}}\) with good asymptoticp properties. To obtain codes with similar properties over \({\mathbb{F}_{{p^2}}}\), q being an arbitrary power of a prime p, one has q to consider Drinfeld modular curves. The latter have a number of advantages as compared with the classical modular curves; they are in many aspects simpler. Unfortunately this does not regard all the aspects of the theory of modular curves. In some cases classical modular curves are more convenient since they come from characteristic zero, which gives a number of essential results unknown for Drinfeld modular curves (e.g. a characterization of their Weierstrass points).

In this chapter we show that codes on modular curves and Drinfeld curves have polynomial construction complexity.

How can one pack equal non-overlapping spheres in ℝ ^N ? What is the density of such packing and how the density behaves for N → ∞?

In the previous chapter we have seen that there are numerous analogies between linear codes and lattices; we have also constructed the Leech lattice using the Golay code. Here we continue to use codes to obtain packings. In Section 5.2.1 we describe some beautiful constructions which give various dense packings using various code families. Section 5.2.2 is devoted to asymptotically good packings obtained by this construction.

AG-codes are constructed using curves over finite fields. As we have seen in Section 5.3.3 there is a system of analogies between curves over finite fields and algebraic number fields. These analogies lead to a number of constructions of codes and lattices. We discuss here seven constructions of this kind (the construction of AG-codes being the eighth). Each of them can be characterized by the following data: a) we use either number (N), or function (F) fields; b) we use either additive (A), or multiplicative (M) structure; c) we obtain either lattices (L), or codes (C); d) the construction either depends on a divisor (D), or not. These are the meanings of abbreviations we use below. Note that the construction of AG-codes can be abbreviated as FACD. For each construction we estimate parameters and try to produce asymptotically good families.