Algebraic soft decoding of reed-solomon codes
US6634007B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 23, 2000 |
| Grant date | Oct 14, 2003 |
| Priority date | — |
| Expiry date | Jun 23, 2020 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M13/458
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
An algorithmic soft-decision decoding method for Reed-Solomon codes proceeds as follows. Given the reliability matrix Π showing the probability that a code symbol of a particular value was transmitted at each position, computing a multiplicity matrix M which determines the interpolation points and their multiplicities. Given this multiplicity matrix M, soft interpolation is performed to find the non-trivial polynomial QM(X,Y) of the lowest (weighted) degree whose zeros and their multiplicities are as specified by the matrix M. Given this non-trivial polynomial QM(X,Y), all factors of QM(X,Y) of type Y−ƒ(X) are found, where ƒ(X) is a polynomial in X whose degree is less than the dimension k of the Reed-Solomon code. Given these polynomials ƒ(X), a codeword is reconstructed from each of them, and the most likely of these codewords selected as the output of the algorithm. The algorithmic method is algebraic, operates in polynomial time, and significantly outperforms conventional hard-decision decoding, generalized minimum distance decoding, and Guruswami-Sudan decoding of Reed-Solomon codes. By varying the total number of interpolation points recorded in the …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.