Previous algorithms for decoding AG codes up to the designed distance all assumed existence of an extra rational place on the base algebraic curve. The place is used to solve the decoding problem by linear algebra over the base field of the curve. The rationality of the place is essential, and therefore AG codes supported by all rational places on the curve are excluded from the domain of applicability of the decoding algorithms. This paper presents a decoding algorithm for those AG codes using an extra place of higher degree. Hence finally all AG codes, as Goppa defined 40 years ago, are equipped with a fast decoding algorithm.

A fast, area efficient very large scale integration (VLSI) architecture is proposed for a unique decoding algorithm of Hermitian codes which was presented recently by Lee and O'Sullivan from an interpolation perspective. The algorithm iteratively computes the sent message through a majority voting procedure by using the Gröbner bases of interpolation modules. The algorithm has a regular structure which makes it suitable for VLSI implementation. The circuitry is simplified as the decoding algorithm directly gives the message word at the end of the decoding algorithm without separate steps like Chien search and Forney's formula. In terms of hardware requirements, for the widely used high rate Hermitian codes, the Lee–O'Sullivan algorithm is q times faster than Kötters algorithm with the same space complexity of O ( q 4 ). Further speed improvements can be achieved by combining the main idea of Guruswami list decoding with the Lee–O'Sullivan algorithm. In terms of hardware, the addition of this concept, will further reduce the running time of the algorithm and make the circuitry about two times faster than the original Lee–O'Sullivan algorithm. The implementation results for both the Köetter and the Lee–O'Sullivan algorithms on Xilinx Virtex‐5 shows that the proposed decoder can be operated at higher clock frequency with almost same area complexity.

A sharp upper bound for the maximum integer not belonging to an ideal of a numerical semigroup is given and the ideals attaining this bound are characterized. Then, the result is used, through the so-called Feng-Rao numbers, to bound the generalized Hamming weights of algebraic-geometry codes. This is further developed for Hermitian codes and the codes on one of the Garcia-Stichtenoth towers, as well as for some more general families.

A unique decoding algorithm for general AG codes, namely multipoint evaluation codes on algebraic curves, is presented. It is a natural generalization of the previous decoding algorithm which was only for one-point AG codes. As such, it retains the same advantages of fast speed, regular structure, and direct message recovery. Upon this generalization, we add a technique from the Guruswami-Sudan list decoding that boosts the decoding speed significantly. Compared with other known decoding algorithms for general AG codes, it has a similar decoding performance and allows streamlined practical implementation by its simple and regular structure.

We present a unique decoding algorithm of algebraic geometry (AG) codes on plane curves, Hermitian codes in particular, from an interpolation point of view. The algorithm successfully corrects errors of weight up to half of the order bound on the minimum distance of the AG code. It is the first decoding algorithm to combine some features of the interpolation-based list decoding with the performance of the syndrome decoding with the majority voting scheme. The regular structure of the algorithm allows a straightforward parallel implementation.

An algebraic soft-decision decoder for Hermitian codes is presented. We apply Koetter and Vardy's soft-decision decoding framework, now well established for Reed-Solmon codes, to Hermitian codes. First we provide an algebraic foundation for soft-decision decoding. Then we present an interpolation algorithm to find theQ-polynomial that plays a key role in the decoding. With some simulation results, we compare performances of the algebraic soft-decision decoders for Hermitian codes and Reed-Solmon codes, favorable to the former.

A central problem of algebraic soft-decision decoding of Reed-Solomon codes is to find the minimal polynomial of the ideal of interpolating polynomials with respect to a certain monomial order. An efficient algorithm that solves the problem is presented based on the theory of Gröbner bases of modules.

Distance-increasing maps from binary vectors to permutations, namely DIMs, are useful for the construction of permutation arrays. While a simple mapping algorithm defining DIMs of even lengths is known, existing DIMs of odd lengths are defined either by recursively merging DIMs of shorter lengths or by complicated mapping algorithms. In this paper, simple mapping algorithms defining DIMs of all lengths are presented.

Distance-preserving maps (DPMs) from binary vectors to permutations are useful for the construction of permutation arrays. A new construction of DPMs is presented. We study the distance increasing property of the new DPMs that this construction yields. Then we show that new DPMs contain a class of nicely structured DPMs of even length with good distance increasing property.

We propose a new construction of maps preserving the Hamming distance from the set of binary vectors of odd length to the set of permutations of the same length. We investigate their distance increasing property, and show that a class of new maps have better distance increasing property than previously known maps of equal length.