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.
Best Answer
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.