Are algebraic geometry error correcting codes (Goppa codes) "good" ? - MathOverflow

Are algebraic geometry error correcting codes (Goppa codes) "good" ?

2012-03-24T11:01:11Z

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 ?

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

Answer by Mark Wildon for Are algebraic geometry error correcting codes (Goppa codes) "good" ?

2012-03-24T13:37:02Z

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.

Answer by unknown (google) for Are algebraic geometry error correcting codes (Goppa codes) "good" ?

2012-03-24T17:15:52Z

AG codes for a given length n and alphabet q will beat corresponding turbo and LDPC but only over a channel with finite field alphabets (and over a complex channel if properly mapped and decoded properly).

Firstly hamming metric is not the true metric of gaussian channels which are the real channels (remember Trellis coded modulation which naively achieves coding gain by proper mapping of constellations that ordinary algebraic codes could not). There is no good way known to map algebraic codes to complex constellations (an analogy would be smaller distance code words should be mapped far apart in the complex constellations.. there is no subexponential way to do this). So even turbo and ldpc inspite of their bad minimum distance properties have an advantage.

Secondly even if you have a good map complex constellations (say gaussian distribution), there is no efficient soft decoder or hard decision ML decoder for AG codes and the notion of MAP decoding is hard (computationally). That is why even turbo and ldpc perform better inspite of having just a suboptimal MAP decoder over a complex channel.

My intuition is AG codes should achieve capacity faster (that is for a given rate could use much shorter codes) than inferior turbo and ldpc. However there is no proof for this. I believe the situation is due to the complexity involved in providing an argument through the first point (namely you have to show how many points are closer than distance d from each other and how should one map them over complex channels and how will the gains scale up.... these all seem to hit a wall due to the formidable computing complexity involved for any given n).