On-the-fly algebraic error correction system and method for reducing error location search
US6671850B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | May 1, 2000 |
| Grant date | Dec 30, 2003 |
| Priority date | — |
| Expiry date | May 1, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2207/7209
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
An on-the-fly algebraic error correction system and corresponding method for reducing error location search are presented. The method transforms an error locator polynomial into two transformed polynomials whose roots are elements in a smaller subfield, in order to significantly simplify the complexity, and to reduce the latency of the error correcting system hardware implementation. More specifically, if the error locator polynomial is over a finite field of (22n) elements, the transformed polynomial is over a finite subfield of (2n) elements. Thus, the problem of locating the roots of the error locator polynomial is reduced to locating the roots of the transformed polynomials. Assuming the error locator polynomial is of degree m, the present method requires at most (m2/2) evaluations of polynomials over the Galois field GF(22n) and (2n+1) evaluations over the subfield GF(2n) or root finding of two polynomials of at most a degree m over the subfield GF(2n).
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.