Algebraic Coding for Error Control

Algebraic coding for error control deals with the problem of protecting data which are transmitted via a channel against random errors. Here only block codes are considered, where to k information symbols, which carry the information a sequence of (n-k) check symbols are added. The sequence of n symbols is called codeword. The whole ensemble of such codewords is called a code. The code is constructed in such a way that all codewords differ in as much as possible from each other. There are different metrics to measure the distance (for further details see books on coding theory, a literature list is given in the overview of my lecture notes here). The most common metric is the Hamming metric. The section below about negacyclic codes considers the Lee metric. Usually one prefers so-called linear codes, where the addition of codewords is defined and the sum of two codewords also is a codeword. A linear code is characterised by the triple [n,k,d] where n is the length of the code, k the number of information symbols and d gives the minimum distance (according to a distance function) which means that the distance of any two different codewords is at least equal to d.

Goppa Codes

Goppa codes are codes for error control coding which contain cyclic codes as subset (cyclic codes have the property that any cyclic shift of a codeword leads to another codewort of the code). In addition there are many Goppa codes which are better than cyclic codes (e.g. the binary [16,8,5] Goppa code is better than the cyclic [15,7,5] code). An important feature of Goppa codes is that there are efficient methods for encoding and decoding.

Tables of practical binary Goppa Codes

Tables with practical parameters of Goppa codes are given here: Goppa Codes. Practical means that the length of the code and/or the number of information bits are a multiple of 8 (8 bit = 1 Byte). The tables contain only codes which are the best or best known codes (according to the table of A.E.Brouwer, Bounds on the size of linear codes, pp.295-461 in the book V.S.Pless, W.C.Huffman, editors, Handbook of Coding Theory, Vol.I, Elsevier, 1998).

Error Locator Polynomial of Two-Error Correcting Binary Goppa Codes

The report here gives the two-error locator polynomial of binary Goppa codes, which - to my knowledge - has not been published in the literature. I found the results of this unpublished manuscript about twenty years ago. As I often used the decoding of the [16,8,5] Goppa code as exam problem in my lecture on 'Algebraic coding' (the students had to perform the Patterson algorithm), it was not opportune to treat this in the lecture. Now that I do not hold the lecture any more it perhaps might be of interest for people interested in Goppa codes.

Negacyclic Codes for the Lee Distance

Derivation of Roth's decoding algorithm from Berlekamp's algorithm

A derivation of Roth's decoding algorithm starting from Berlekamps's original approach is described here:Roth's algorithm

Codes for the Mannheim Distance

The Mannheim Distance does the same on a finite two-dimensional grid what the Lee distance does on the circle (the Mannheim distance was introduced in my article K.Huber, "Codes over Gaussian Integers", IEEE Trans. on Inf. Theory, Vol.40, No.1, January 1994, pp.207-216). The Mannheim distance is interesting for coding over QAM-Signalconstellations. An overview talk on this subject is given here (in German).