Root solver and associated method for solving finite field polynomial equations
US6792569B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 24, 2001 |
| Grant date | Sep 14, 2004 |
| Priority date | — |
| Expiry date | Jan 14, 2023 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M13/1515
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
An error correction algebraic decoder uses a key equation solver for calculating the roots of finite field polynomial equations of degree up to six, and lends itself to efficient hardware implementation and low latency direction calculation. The decoder generally uses a two-step process. The first step is the conversion of quintic equations into sextic equations, and the second step is the adoption of an invertible Tschirnhausen transformation to reduce the sextic equations by eliminating the degree 5 term. The application of the Tschirnhausen transformation considerably decreases the complexity of the operations required in the transformation of the polynomial equation into a matrix. The second step defines a specific Gaussian elimination that separates the problem of solving quintic and sextic polynomial equations into a simpler problem of finding roots of a quadratic equation and a quartic equation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.