Search

A major problem in coding theory is the question of whether the class of cyclic codes is asymptotically good. In this correspondence--as a generalization of cyclic codes--the notion of transitive codes is introduced (see Definition 1.4 in Section I), and it is shown that the class of transitive codes is asymptotically good. Even more, transitive codes attain the Tsfasman-Vladut-Zink bound over [F.sub.q], for ali squares q = [l.sup.2]. It is also shown that self-orthogonal and self-dual codes attain the Tsfasman-Vladut-Zink bound, thus improving previous results about self-dual codes attaining the Gilbert-Varshamov bound. The main tool is a new asymptotically optimal tower [E.sub.o] [??] [E.sub.1] [??] [E.sub.2] [??] ... of function fields over [F.sub.q] (with q : [l.sup.2]), where all extensions [E.sub.n]/[E.sub.0] are Galois. Index Terms--Asymptotically good codes, cyclic codes, self-dual codes, towers of function fields, transitive codes, Tsfasman-Vladut-Zink bound.

We show that the concept of "generalized algebraic geometry codes" which was recently introduced by Xing, Niederreiter, and Lam gives a natural framework for constructing linear unequal error protection codes. Index Terms--Algebraic-geometry codes, algebraic curves, algebraic function fields, linear unequal error protection codes.

Algebraic function fields (or equivalently, algebraic curves) provide a useful tool for coding theory (for instance, algebraic-geometric codes and trace codes), but also for other branches of information theory. In these applications, the number of rational places of a function field plays a crucial role. One is particularly interested in function fields having a large number of rational places. After a short introduction into the mathematical theory of algebraic functions, the paper gives a survey of old and new results on the number of rational places of function fields. Index Terms - Algebraic function fields, algebraic curves, geometric Goppa codes, AG codes, trace codes, m-sequences, bounds for the number of rational places, bounds for the code parameters.

The weight hierarchy of a linear code is the set of generalized Hamming weights of the code. In this paper, we consider geometric Goppa codes and provide a lower bound on their generalized Hamming weights similar to Goppa's lower bound on their minimum distance. In the particular case of Hermitian codes, exact results on the second and third generalized Hamming weights are given for any m except a few cases, where m is a parameter that governs the dimension of these codes. In many instances, we are able to provide considerably more information on their generalized Hamming weights. An upper bound relating the generalized Hamming weights of Hermitian codes to the pole numbers at a special point on the curve is also provided. Similar results are given in the case of codes from some subfields of the Hermitian function fields, which are also maximal. Finally, a nontrivial family of codes is also presented whose weight hierarchy is completely determined.

Linear codes over [F.sub.p] often admit a natural representation as trace codes of codes that are defined over an extension field [F.sub.p]m. In this paper, we obtain estimates for the weights of subcodes of such trace codes. Our main result is a far-reaching generalization of the Carlitz-Uchiyama bound for the duals of binary BCH codes. In particular, we prove sharp bounds for the generalized Hamming weights of a large class of codes, including duals of BCH codes, classical Goppa codes, Melas codes, and arbitrary cyclic codes of length n = [p.sup.m] - 1. Our main tool is the theory of algebraic functions over finite fields, in particular the Hasse-Weil bound for the number of places of degree one.

The Gilbert-Varshamov (GV) bound for asymptotic families of codes over [F.sub.q] has been improved by Tsfasman, Vladut, and Zink (TVZ) in 1982, and only recently further improvements have been obtained by Xing, Elkies, and Niederreiter-Ozbudak, by considering also nonlinear codes. These improvements involve higher derivations in function fields and are very computational. We give in this correspondence a much simpler proof for those improvements. Our construction of asymptotically good nonlinear codes is very similar to Goppa's construction of algebraic-geometry codes. Index Terms--Algebraic function fields, algebraic-geometry codes, asymptotic bounds, Tsfasman-Vladut-Zink (TVZ) bound.

Since the proof in 1982, by Tsfasman Vladut and Zink of the existence of algebraic-geometric (AG) codes with asymptotic performance exceeding the Gilbert--Varshamov (G--V) bound, one of the challenges in coding theory has been to provide explicit constructions for these codes. In a major step forward during 1995-1996, Garcia and Stichtenoth (G--S) provided an explicit description of algebraic curves, such that AG codes constructed on them would have performance better than the G--V bound. We present here the first low-complexity algorithm for obtaining the generator matrix for AG codes on the curves of G--S. The symbol alphabet of the AG code is the finite field of [q.sup.2], [q.sup.2] [is greater than or equal to] 49, elements. The complexity of the algorithm, as measured in terms of multiplications and divisions over the finite field GF [(q.sup.2)], is upper-bounded by [[[N log.sub.q](N)].sup.3] where N is the length of the code. An example of code construction using the above algorithm is presented. By concatenating the AG code with short binary block codes, it is possible to obtain binary codes with asymptotic performance close to the G--V bound. Some examples of such concatenation are included. Index Terms--Algebraic-geometric (AG) codes, concatenated codes, function field tower, Gilbert--Varshamov (G--V) bound.

A description of how places split in an asymptotically optimal tower of function fields studied by Garcia and Stichtenoth is provided and an exact count of the number of places of degree one is given. This information is useful in the setting up of generator matrices for algebraic-geometry codes constructed over this function field tower. These long codes have performance that asymptotically improves upon the Gilbert-Varshamov bound. Index Terms--Agebraic-geometry (AG) codes, function field tower, Garcia-Stichtenoth tower.

We discuss some recent constructions of codes from algebraic curves due to Xing, Niederreiter, and Lam, and we investigate their relations with Goppa's algebraic-geometric codes. Index Terms--Algebraic curves, algebraic function fields, AG codes, geometric Goppa codes.