Algebraic soft decoding of reed-solomon codes

A method of decoding an algebraic-geometric error-correcting code comprising a plurality of codewords, each codeword having multiple symbols, the method of decoding comprising the steps of:

• 1) converting reliability information concerning individual code symbols into algebraic interpolation conditions;
• 2) finding a non-trivial polynomial that satisfies said interpolation conditions;
• and
• 3) generating a list of candidate codewords of the algebraic-geometric code.

A method of decoding a Reed-Solomon error-correcting code of length n and rate R over a finite field q with q elements or a Bose-Chaudhuri-Hocquenghem (BCH) error-correcting code of length n and rate R′ over the finite field q on a channel of type drawn from the group consisting of q-ary symmetric channels, q-ary symmetric erasure channels, and q-PSK channels,

• where input to the decoding method consists of data that includes:
• a vector y=(y1,y2, . . . , yn) observed at the channel output, where all the n elements of the vector y belong to the finite field q in the case of q-ary symmetric channels and q-PSK channels, whereas in the case of q-ary symmetric erasure channels, all the n elements of the vector y belong to q∪{φ}, where the special symbol φ denotes erasure,
• the decoding method comprising:
• 1) given the vector y=(y1,y2, . . . , yn), computing from this vector y a set of algebraic interpolation conditions that specify values of an interpolation polynomial;
• 2) given the algebraic interpolation conditions interpolating to find a (non-trivial) interpolation polynomial that satisfies these conditions;
• and
• 3) given the interpolation polynomial, factoring this polynomial to find factors that correspond to codewords of the Reed-Solomon code or the BCH code, thereby generating a list of candidate codewords.

A method of decoding an algebraic-geometric error-correcting code of length n, dimension k≦n, and rate R=k/n, over a finite field q with q elements, the algebraic-geometric code being constructed on an algebraic curve of genus g, the method of decoding being applied to decode the algebraic-geometric code on a channel of type drawn from the group consisting of q-ary symmetric channels, q-ary symmetric erasure channels, and q-PSK channels, p1 where input to the decoding method consists of data that includes:

• a vector y=(y1,y2, . . . , yn) observed at the channel output, where all the n elements of the vector y belong to the finite field q in the case of q-ary symmetric channels and q-PSK channels, whereas in the case of q-ary symmetric erasure channels, all the n elements of the vector y belong to q∪{φ}, where the special symbol φ denotes erasure,
• the decoding method comprising:
• 1) given the vector y=(y1,y2, . . . , yn), computing from this vector y a set of algebraic interpolation conditions that specify values of an interpolation polynomial;
• 2) given the algebraic interpolation conditions, interpolating to find a (non-trivial) interpolation polynomial that satisfies these conditions;
• and
• 3) given the interpolation polynomial, factoring this polynomial to find factors that correspond to codewords of the algebraic-geometric code, thereby generating a list of candidate codewords.