Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
    
Thank you very much for yours answer ! –  Alexander Chervov Mar 25 '12 at 7:28
1  
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

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).

share|improve this answer
    
Thank you very much for yours answer. Let me ask to clarify something. Do you mean that AG will beat turbo&LDPC for q>>2 ? (Actually I did not know about construction of turbo&LDPC for q>2). What if q=2 ? You write "There is no good way known to map algebraic codes to complex constellations" but why AG is worse than turbi&LDPC in this respect ? Would you be so kind to provide some references to the literature ? –  Alexander Chervov Mar 25 '12 at 7:27
    
Hi Alexander: 1) I believe AG codes will beat any other construction that lies below or at the GV bound for all alphabets q>49 for some rates (if the other construction even meets the GV bound for q<49, they will be theoretically superior to AG codes since AG codes do not meet GV bound below q<49). 2) For the mapping question read TCM where if the underlying code words are close in binary, they will be mapped far apart in Euclidean distance. There is no easy way to do this for Block codes. –  J.A Mar 25 '12 at 7:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.