# Are algebraic geometry error correcting codes (Goppa codes) “good” ?

Question (informal version): Are algebraic geometry error correcting codes (V.D. Goppa codes) "good" ?

Some details. There is certain construction of error-correcting codes by means of algebraic geometry, originating from pioneering work by Russian mathematician Valerii Denisovich Goppa (70-ies or early 80-ies ?).

I wonder what is known about these codes: a) are they "capacity-achieving" b) are there some "low-complexity" soft-decoders, like belief propogation which complexity is linear in the length of code c) are there some practical applications of these codes in error-correcting applications, if not - why ?

PS

It is known that they are involved in McEliece cryptosystem, but it is crypto-application, not error-correcting.

-

Given a $q$-ary code $C$ of length $n$ with minimum distance $d$, define its rate to be $(\log_q |C|)/n$, and its relative distance to be $d/n$. The Gilbert-Varshamov lower bound states that for any $q \ge 2$ and any $\delta \in (0,1)$ there is a $q$-ary code $C$ of relative distance $\ge \delta$ whose rate $r$ satisfies

$$r \ge 1 - H_q(\delta)$$

where $H_q(\delta) = \delta \log_q(q-1) - \delta \log_q(\delta) - (1-\delta)\log_q(1-\delta)$ is the $q$-ary entropy function.

The rate of an algebraic geometry Goppa code using a curve over $\mathbb{F}_q$ of genus $g$ satisfies

$$r \ge 1 - \delta - \frac{g-1}{n}.$$

This suggests that such codes could beat the Gilbert-Varshamov bound, and this was shown in 1982 by Tsfasman, Vladut and Zink. However I believe the best known improvement on the lower bound is very small, and so Goppa codes do not come close to meeting the Hamming bound $r \le 1-H_q(\delta/2)$.

In any case there are stronger generic bounds than the Hamming bound, for example, the Elias-Bassalygo bound, that show it is impossible to attain the channel capacity of a $q$-ary symmetric channel by hard nearest neighbour decoding in the Hamming setup.

I don't know much about decoding algebraic geometry Goppa codes. A quick web search found this paper from 1992. Roughly stated, the results in its introduction say that a Goppa code of length $n$ and minimum distance $d$ can be decoded in $O(n^3)$ time provided at most $d/2$ errors occur. There has been some more recent work on soft-decoding for Reed-Solomon codes (which are a special case of Goppa codes): see here, for example.

-
Thank you very much for yours answer ! –  Alexander Chervov Mar 25 '12 at 7:28
IIRC at least for some classes of Goppa codes $O(n^{7/3})$ decoding algorithms are known (search for Kötter, Feng-Rao, the Danes: Refslund, Hoholdt et al at least published something about it). A few years ago I asked Alex Vardy and Ralf Kötter, whether their soft decoding algorithm (a generalization of the list decoding algorithm due to Madhu Sudan) will generalize to one-point Goppa codes. Ralf Kötter in particular was convinced that it would. I don't know, whether they published anything on it, and sadly Kötter died a few year ago. –  Jyrki Lahtonen Mar 29 '12 at 6:17