next up previous
Next: References


Reflections on the ``Decoding of Algebraic-Geometric Codes
up to the Designed Minimum Distance"

Gui-Liang Feng, Member IEEE, and T. R. N. Rao, Fellow IEEE

The Why, What, and How of Algebraic-Geometric Codes

We begin this exposition by looking back at two key developments: (i) reduction of the Shannon problem to the Hamming problem, and (ii) reduction of the Hamming problem to the Riemann problem. During the late 1940's, Shannon and Hamming developed two different approaches for coding discrete information in the presence of noise. Shannon proposed a general model for a noisy channel, in which distortions are described by the conditional probabilities of the transformation of one word into another. He proved an important coding theorem on the possibility of transmitting information in such a way that the probability of error tends to zero as the word length increases. Unfortunately, the statistical description of the channel does not indicate how to construct optimal codes. Therefore, the problem of constructing such codes in Shannon's model has not been accomplished in practice. However, beginning with the very simple parity checks already used in the first computers, Hamming arrived at the idea of error-correcting codes. He proposed a geometrical model in which distortions are described by the distance between words, defined as the number of symbols by which the words differ from each other. The problem of constructing an optimal code in this model reduces to that of the densest possible packing of spheres. To solve this problem, a variety of methods were applied from logic, combinatorics, number theory, algebra, geometry, and topology. The concept of a code associated with an algebraic curve gradually crystallized, and Riemann-Roch theorem became the basic computational tool. The problem of constructing good codes was thus reduced to the analysis of algebraic curves [1].

Why AG codes?

There exist several important classes of linear codes, which have been extensively studied. A linear code of finite length can be defined as the null space of a parity matrix . A linear code with length n over is a linear subspace of . The notation [n,k,d] is commonly used to represent a code of length n with dimension k and minimum distance d. For such a code, the information rate and the relative minimum distance rate, are given by and respectively.

A sequence of linear codes over , such that the code length when , is said to be asymptotically good, if the information rates and the relative minimum distance rates are bounded away from zero.

Let us consider the q-ary entropy function defined as follows:

Since , when q=2, the binary entropy function is reduced to

() () is called the Gilbert-Varshamov curve. It is known that and () = 0. For more than thirty five years, for a fixed , the best lower asymptotic bound on has been referred to as the Gilbert-Varshamov bound, which can be simply described as follows:

Gilbert-Varshamov bound : Suppose . Then there exists an infinite sequence of q-ary linear codes with and rate R satisfying the following condition:

Finding asymptotically good codes, especially a sequence of linear codes, which meet or exceed the Gilbert-Varshamov bound, has been a very active area of research for the past thirty five years. Unfortunately, many known linear codes are asymptotically bad codes. It was previously shown that there exist long Goppa codes which meet the Gilbert-Varshamov bound. However a solution for finding these long Goppa codes has not yet appeared. In 1972, Justesen gave a construction of explicit asymptotically good codes by using concatenated codes [5]. For this work, he received the 1972 Browder J. Thompson prize. However, these codes achieve a lower bound which is below the Gilbert-Varshamov (GV) bound.

It is desirable to construct asymptotically good codes of longer code length for a designed minimum distance, which meet or exceed the Gilbert-Varshamov bound. To this extent considerable research efforts have been made, which investigated a new approach to construct linear codes, especially using the rational points of algebraic-geometric curves as code locations.

What are AG codes?

The most important development in the theory of error-correcting codes in recent years was the introduction of methods from algebraic geometry to construct good codes. The ideas are based on generalizations of the so-called Goppa codes. The "classical" Goppa codes were already a great improvement on codes known at that time. V. D. Goppa [2-4] discovered an amazing connection between the theory of algebraic curves over a finite field and the theory of error-correcting block q-ary codes. His efforts of many years in searching for possible generalizations of Reed-Solomon codes, BCH codes and classical Goppa codes, culminated in the development of algebraic geometric (AG) codes. The codes constructed by choosing a family of points from a curve and a space of rational functions of this curve, are said to be algebraic-geometric codes. These codes are also known as geometric Goppa codes, and can be considered to be a generalization from the Reed-Solomon codes on an affine line to the codes on arbitrary irreducible non-singular curves. In this context, it is to be noted that all linear codes can be described as AG codes.

Algebraic-geometric codes opened new and rather exciting possibilities in coding theory and related topics. They have very good code parameters (like code dimension, minimum distance rate , and information rate R), and offer flexibility in the choice of these parameters. For a long time there was serious doubt whether it would be possible to give an explicit algebraic construction of a sequence of codes such that both R and are bounded away from zero.

A very sensational development in the theory of AG codes was presented in a paper, [6], by Tsfasman, Vladut and Zink in 1982. In this paper, the idea of codes from algebraic curves was combined with some recent results from algebraic geometry, to produce a sequence of polynomially constructive error-correcting codes over . This led to a new lower bound, the Tsfasman-Vladut-Zink (TVZ) bound, on the information rate of good codes, which is better than the GV bound when . For this paper, the authors received the IEEE Information Theory Group Paper Award in 1983.

The novice reader should realize that the GV-bound could not be improved until 1982, and was believed by many researchers to be the best possible lower bound. Several binary coding experts still feel that for linear codes over , it is not possible to achieve any improvement of the GV bound. Furthermore, there exists no known explicit or simple (or with a polynomial complexity of length n and a lower degree) construction of a sequence of codes meeting this bound.

In 1984, Katsman, Tsfasman and Vladut [7] gave a construction which uses a class of codes over a fixed field GF(), , and meeting the TVZ bound. However, the time complexity of construction of these codes is very high.

For any desired minimum distance, codes of longer length can be constructed using the principles based on AG curves. The basic computational tool for determining the minimum distance of these codes is the Riemann-Roch theorem. We shall now discuss the construction of AG codes from algebraic-geometric curves.

How to construct AG codes?

Reed-Solomon codes can be regarded as a special type of AG codes. For these codes, the points on an affine plane line can be considered as the code locations. However, the number of points is limited by the number of elements in the field. We illustrate the construction of Reed-Solomon code by considering an example over GF(). The line y = 0 contains four points (0, 0), (1, 0), (, 0) and (, 0). Using these four points, we can construct Reed-Solomon code of length 4. The basis of ( = ) comprises the following four vectors:

These vectors can be regarded as the evaluated vectors of the monomials { 1, x, , } at these four points. By considering the first r 3 vectors (i.e., monomials) of the basis as a parity check matrix, we can define the Reed-Solomon code over GF(). In general, the code has the minimum distance r+1. For example, we define the parity check matrix of the first r = 2 vectors as follows:

The Reed-Solomon code defined by this parity check matrix has the minimum distance r+1 = 3.

Now we give a simple example illustrating the construction of AG codes from Hermitian curves in a two-dimensional affine space. Consider a Hermitian curve defined as follows:

The roots (i.e., rational points) of this curve are given as follows: (, ) = (0, 0), (, ) = (0, 1), (, ) = (1, ), (, ) = (1, ), (, ) = (, ), (, ) = (, ), (, ) = (, ), and (, ) = (, ). These rational points constitute a location set LS, whose elements also denote the locations of a linear code. Each f(x,y) is associated with an evaluated vector, evaluated on these rational points as: f(x,y) (f(), f(), f(), f(), f(), f(), f(), f() ). Then the monomials { 1, x, y, , xy, , , } are associated with the following evaluated vectors:

By considering the first r vectors, (i.e., the first r monomials), we can define the parity matrix of the code . For example, the parity matrix obtained by the first 5 vectors is as shown below, and defines the code .

In general, by considering the first r vectors, (i.e., the first r monomials of the sequence H), as a parity check matrix , we can define codes with length n and the points of LS as the code locations. The minimum distance of these codes can be determined by using the Riemann-Roch theorem, i.e., d() r-g+1, where g is the genus of the curve. By choosing a larger set of rational points, we can construct AG codes of larger code lengths.

Let us consider the following curve in a three-dimensional space over GF():

This curve has rational points, and from these rational points we can construct AG codes over GF(), up to length 16.

If we consider curves, surfaces or other varieties in high-dimensional spaces, we get an increase in the number of rational points and thus can construct AG codes of larger code lengths.

Decoding AG Codes up to the Designed Minimum Distance

The construction and decoding of AG codes are two important problems of study in the development of the theory of algebraic-geometric codes. Good code constructions are very important. Moreover, it is desirable and essential to derive simple decoding procedures which can correct as many errors as possible. The algebraic decoding of block codes by first determining an error-locator polynomial and subsequently evaluating its zeroes which yield the error locations, was presented by Peterson in 1960 for binary BCH codes, and extended by Gorenstein and Zierler to q-ary BCH codes. By generalizing their idea to AG codes, in 1989, Justesen, Larsen, Jensen, Havemose and Hoholdt [8] published the first decoding procedure for a class of AG codes based on plane curves. This decoding procedure is a generalization of the Peterson's decoding procedure for AG codes on plane curves, and can correct up to errors, where is the designed minimum distance of the code and g is the genus of the curve involved in the construction. For this paper, they received the IEEE Information Theory Group Paper Award in 1991.

Subsequent research based on this approach resulted in several improvements. Skorobogatov and Vladut [9] generalized their ideas and gave a decoding procedure for AG codes derived from arbitrary algebraic curves, which can correct any or fewer errors. In their paper, Skorobogatov and Vladut also presented a modified algorithm which corrects more errors, though in general, not up to the designed minimum distance. Independently, Krachkovskii proved the same result, but his work was only published as a preprint in Russian [10]. Using profound results from algebraic geometry, Pellikaan [11] gave a decoding procedure which can correct up to errors. However, his decoding procedure is very complex and is not efficient. Justesen et al. [12], improved on their original decoding procedure in several ways and gave a new decoding procedure for AG codes from arbitrary regular plane curves, which can correct up to errors. Porter, Shen and Pellikaan [13] proposed a decoding procedure using an extra place, and Duursma [14] suggested a decoding procedure which uses a special divisor. Unfortunately, all these decoding procedures can not correct up to errors, which is the error-correcting capacity of AG codes. During the past few years, the problem of decoding AG codes up to errors has become very active and to a large extent has remained intangible.

In 1991, we gave a generalized Peterson's decoding procedure which looks simple and can correct up to errors for the AG codes , where G=mQ [15]. Similar to the previous decoding algorithms, this decoding procedure also uses the technique of solving systems of linear equations and can be explained purely in terms of linear algebra, in the same manner by which one can abstract from AG codes to linear codes. But we add a majority voting scheme to determine the value of the next unknown syndrome, until the error locator polynomial can be uniquely determined, or until the values of all the unknown syndromes can be determined. At about the same time, Ehrhard independently found another decoding algorithm which can also decode AG codes up to the designed minimum distance, but only for the case of , [16].

It is well-known that the decoding of Reed-Solomon codes is equivalent to solving a system of special non-linear equations with one variable. Peterson's decoding procedure reduces this problem to finding a linear dependence of the initial columns for the syndrome matrix, i.e., finding an error locator polynomial, and solving the error locator equation. However, the correctness depends on the fact that the syndrome matrix can be decomposed into a product of three matrices, i.e., S = X E Y, where E is a diagonal matrix, and X is a full rank matrix. We must mention that some of the entries of matrix S are unknown. Hence we can only find the partial linear dependent relations of columns of S. Using the Vandermonde matrix in the decoding of Reed-Solomon codes, X is guaranteed to be a full rank matrix, whose rank is given by the number of errors. Thus, from the partial linear dependent relations of columns of the syndrome matrix S, we can find the same linear dependent relations of the corresponding columns of the unknown matrix Y, i. e., we can find the functions that must be satisfied by all the error locations. Hence, from the syndrome matrix S, we need to find the partial linear dependent relations of the columns. Furthermore, from these partial linear dependent relations, i.e., error-locator polynomials, we can determine the error locations. The error magnitudes can be determined by solving a system of linear equations. Similarly, the decoding of AG codes is equivalent to solving a system of special non-linear equations with several variables. We can also use the Peterson's decoding procedure to reduce it to solving some linear problems. However, in the case of AG codes with a non-zero genus g, the matrix X is not guaranteed to be a full rank matrix. Thus, the partial linear dependent relations of the columns of the syndrome matrix S may not represent the linear dependent relations of the corresponding columns of matrix Y. Hence, these partial linear dependent relations can not be used to directly determine the error locations.

Our idea considers the fact that all the fully linear dependent relations of columns of S will also be satisfied by the error locations, i.e., these fully linear dependent relations also represent the error locator polynomials. However, some of the partial linear dependent relations of columns of S may not be the fully linear dependent relations of the same columns, because X is not a full rank matrix. Hence, we refer to the partial linear relations of the columns of the syndrome matrix S as candidate linear dependent relations of the columns of S, and also of the corresponding columns of Y. However, it is very difficult to determine the fully linear dependent relations of the columns of S. We rationalized that if this candidate linear dependent relation is a fully linear dependent relation, then the value of the next unknown syndrome that can be uniquely determined by extending the candidate linear dependent relation to this unknown syndrome will be a true syndrome value, provided there is no column leader at its previous columns in the same row. The next unknown syndrome satisfying this condition is called a candidate next unknown syndrome. Fortunately, we were able to prove that among the candidate next unknown syndromes, the number of true values of the syndromes is greater than the number of false values of these syndromes. This enabled us to determine the true values of the next unknown syndromes, using the majority voting scheme. Thus, instead of determining the true candidate linear dependent relations, we determine the true candidate next unknown syndromes. The error vector can be determined in either of the following two ways: (i) by determining the values of all the unknown syndromes and then using the Fourier inverse transform to obtain the error vector, (i.e. Blahut's decoding approach), or (ii) by finding the values of the next g unknown syndromes, determining the error locator polynomial and further calculating the error magnitudes to obtain the error vector, (i.e. Berlekamp-Massey's approach). The second approach is possible because if r+g syndromes are known, the partial linear dependent relations of columns of matrix S also denote the fully linear dependent relations of the columns of matrix S, i. e., they represent the linear dependent relations of the corresponding columns of matrix Y. Using either of these two approaches, we can correct errors up to the designed minimum distance. The complexity is O(), similar to the complexity of solving a system of linear equations with n variables. When the syndrome matrix S satisfies some conditions, (e. g. it is a Hankel matrix, or a block-Hankel matrix, or a Hankel-block-Hankel matrix), the complexity will be further reduced [17,18].

Improved AG Codes without Algebraic-Geometric Curves

For a long time AG codes were thought to be very difficult for engineers to understand, because they are based on the theory of algebraic geometry or algebraic geometric curves. This area has become very active recently due to its utility in solving many important problems. Unfortunately however, it also requires special mathematical knowledge and skills. After the introduction of AG codes, though several papers and books dealing with these codes have been published, these codes are still not clearly understood by many engineers. The current AG codes have many good advantages and are more efficient than the Reed-Solomon codes. However, we believe that the current AG codes can be further improved. Some of the questions of major concern to engineers include (i) the development of techniques and methods to simplify the understanding of AG codes, and (ii) the improvement of the current AG codes to yield more efficient codes.

Justesen et. al. [8], made a significant contribution to the understanding of algebraic-geometric codes. Their approach involves the use of monomials of two variables instead of rational functions in three variables, for deriving the current AG codes from affine plane curves. Blahut [19] gave a simple interpretation of AG codes derived without the use of algebraic-geometric curves. He demonstrated that some codes derived from Klein curves can be considered to be the weighted sums of Reed-Solomon codes.

It is common knowledge that a linear code with length n over a field is a linear subspace in an n-dimensional affine space over this field. A set of n linearly independent vectors of this n-dimensional affine space can be used to construct a sequence of linear codes. For instance, let with the field being GF(). Furthermore, let a monomial represent the evaluated vector (, , , ..., ), where expresses a value 1, for 0 . Then { 1, x, ..., } is a set of linearly independent vectors. The first r vectors define a Reed-Solomon code. For the parity check matrix of this code, a lower bound of the minimum distance can be easily determined by using the Vandermonde matrix. It is therefore very important to choose the n linearly independent vectors such that a lower bound of the minimum distance of the code defined by a subset of the vector sequence can be easily determined. For the Reed-Solomon codes defined by the first r monomials (i.e., vectors) from the sequence { 1, x, ..., }, a lower bound of the minimum distance can be determined by using the Vandermonde matrix, and thus Reed-Solomon codes can be easily constructed. For the AG code over GF() defined by the first r monomials (i.e., evaluated vectors) from the sequence { 1, x, y, , xy, ..., , , , , }, a lower bound of the minimum distance can be determined by using the Reimann-Roch theorem and we can construct Hermitan codes over GF().

>From the majority voting scheme for decoding AG codes up to the designed minimum distance, it can be easily realized that a lower bound , called Feng-Rao bound [20], can be derived by simply calculating the number of the next unknown syndromes in the syndrome matrix, instead of using the Reimann-Roch theorem. This implies that the new decoding scheme can be considered to be a new method for determining a lower bound of the minimum distance. This method does not require the use of the theory of algebraic-geometry. Thus, a sequence of linearly independent vectors which need not be derived from irreducible non-singular curves, can also be used to construct linear codes, and their designed minimum distance can be easily determined by simply calculating the number of the next unknown syndromes in the syndrome matrix. This is the basic idea used for deriving the improved geometric Goppa codes without using algebraic-geometric curves [21-22]. The improvement of the improved geometric Goppa codes over the current AG codes is essentially two-fold: (i) the location set whose elements define the code locations, need not consist of only rational points from irreducible and non-singular curves - these points can be derived from curves, surfaces, hyperplanes or other varieties; (ii) the monomial sequence H need not be made from the first r monomials.

This procedure leads to the definition of a location set whose elements need to satisfy a certain set of equations. These elements may be derived from surfaces, curves or other varieties, and do not necessarily have to be points on irreducible non-singular algebraic curves. This adds to the flexibility in the choice of code parameters of these AG codes.

Apart from us, several eminent researchers including Pellikaan, Wei, Heegard, Saints, and Hoholdt, are currently pursuing active research work in this area. Though the current emphasis of research is towards constructing AG codes without using the theory of algebraic-geometric curves, we feel that with the combined use of the concepts from algebraic coding theory and the insights provided by the theory of algebraic-geometry, it will be possible to witness in the near future, the construction of very simple AG-like codes which are more efficient than the current AG codes.

Some Afterthoughts

Our decoding procedure which is based on the majority voting scheme, finds many interesting applications. For instance, the decoding procedure can be extended to handle the AG codes , where G = , as considered by Duursma [23]. It can also be used in decoding binary cyclic codes up to the true minimum distance, as demonstrated by Feng and Tzeng [24]. Furthermore, we have also applied the majority voting scheme to the erasures-and-errors decoding of AG codes [25].

We now discuss some fascinating implementation details. Decoding of AG codes up to errors has been successfully done in the past by several researchers, using various approaches which include solving a system of linear equations, defining and solving the key equations, using Grobner bases, using Sakata's algorithm, and so on. By applying the majority voting scheme in the decoding procedure, and using the technique of solving a set of linear equations, we can decode AG codes up to the designed minimum distance. Some researchers have recently applied this majority voting scheme in decoding procedure while using some of the other above mentioned approaches, and were also successful in decoding AG codes up to the designed minimum distance [26-29].

Using faster computing algorithms, decoding of AG codes can be improved. For example, in a collaborative research effort with Wei and Tzeng [17], by using a fast algorithm for the Hankel-Block-Hankel matrices to implement the majority voting scheme, we have derived a fast decoding procedure with complexity O(), for the AG codes from the affine plane curves. In [18], we generalized this decoding procedure to the AG codes from m-dimensional affine spaces and obtained a decoding procedure with complexity O(). Using the Sakata algorithm and the majority voting scheme, Sakata, Justesen, and Hoholdt [26] have derived a new decoding procedure for AG codes with the same complexity, O().

Based on the idea of the majority voting scheme, a new approach has been developed for determining a lower bound of the minimum distance. This new approach does not make use of the Reimann-Roch theorem. More general linear codes with some efficient parameters have been constructed. Some of them are called improved geometric Goppa codes, and some are known as AG codes derived without using the theory of algebraic geometry. Recently, research work dealing with the construction of asymptotically good linear codes exceeding the GV bound or the TVZ bound, especially over small finite fields such as GF(4) and GF(8), has become very active, [30]. It is extremely difficult to construct binary linear codes exceeding the GV bound. However, we strongly believe that in the not-too-distant future, many significant results will appear in this area of research.





next up previous
Next: References




Ramesh Rao
Thu Jul 20 17:05:06 PDT 1995