System for finding roots of degree three and degree four error locator polynomials over GF(2M)

A method of operating a data processing system to identify erroneous symbols in a code word, the method including the steps of:

• A. receiving a code word with erroneous data symbols and producing an associated degree-three polynomial with a term β3 that is an element of GF(22m+1);
• B. raising the element β3 to a power u = 2 2 ⁢ m + 2 - 1 3
• to produce the cubic root of β;
• and
• C. using the cubic root of β, identifying which data symbols of the received code word are erroneous and
• i. correcting the errors in the data symbols of the code word,
• ii. labeling the code word as uncorrectable, or
• iii. requesting receipt of the code word again and repeating steps A-C as necessary.

A method of operating a data processing system to identify erroneous data symbols in a code word, the method including the steps of:

• i. receiving a code word with erroneous data symbols and producing an associated degree-three polynomial with a term β3 that is an element of GF(22m);
• ii. raising the element β3 to a power L, where L is a factor of 22m−1;
• iii. raising , to a power V where L+3V=2Q;
• iv. using βL to enter a stored lookup table to retrieve the cubic root of βL;
• v. multiplying (βL)⅓ by βV;
• vi raising (βL)⅓ βV to a power 22m−Q to produce the cubic root of;
• and
• vii using the cubic root of β, identifying which data symbols of the received code word are erroneous and
• a. correcting the errors in the data symbols of the code word,
• b. labeling the code word as uncorrectable, or
• c. requesting receipt of the code word again and repeating steps i-vii as necessary.

A method of operating a data processing system to identify erroneous data symbols in a received code word, the method including the steps of:

• i. receiving a code word with erroneous data symbols and producing an associated degree-three polynomial with a term β3 that is an element of GF(22m);
• ii. raising the element β to a power L, where L is a factor of 22m−1;
• iii. raising βL to a power u = 2 m 0 - 1 - 1 3
• where m0=2km
• iv. raising the element β to a power V, where L+3V=2Q
• v. multiplying (βL)u by βV;
• vi. raising (βL)u βV to a power 22m−Q to produce the cubic root;
• and
• vii. using the cubic root of β, identifying which data symbols of the received code word are erroneous and
• a. correcting the errors in the data symbols of the code word,
• b. labeling the code word as uncorrectable, or
• c. requesting receipt of the code word again and repeating steps i-vii as necessary.

A data processing system for determining the roots of a degree-three polynomial that is associated with a data codeword over GF(22m+1), the system including:

• A. a processor for receiving a data code word containing errors and determining an associated degree-three polynomial;
• B. manipulation means for substituting variables in the degree three polynomial to produce in an extension field GF(24m+2) an equation (y1, y2)3+(0,b)(y1, y2)+(0, a)=0;
• C. manipulation means for substituting variables to produce a quadratic equation (z1, z2)2+(0,b) (z1, z2)+(0,a)3=0
• where (z1, z2) is an element of GF(24m+2) and solving the quadratic equation for (z1, z2);
• D. calculating means for calculating the cube root, (s,t), of (z1, z2);
• and
• E. means for transforming the roots (s, t) and s+t to the roots of the degree-three polynomial and associating the roots with the locations of erroneous data symbols in the data code word;
• and
• F. an error correction processor for
• i. correcting the erroneous data symbols in the code word,
• ii. labeling the code word uncorrectable, or
• iii. sending a repeat request for the code word.

A data processing system for determining error locations in a data code word, the system including:

• A. a first processor for receiving the data code word and determining an associated degree-three polynomial;
• B. a cubic root processor for calculating the cubic root of a multiple bit symbol β that is associated with the degree-three error locator polynomial and is also an element of GF(22m), the cubic root processor including
• i. one or more first multipliers for raising β to a power L, where L is a factor of 22m−1;
• ii. one or more second multipliers for raising β to a power V where L+3V=2Q;
• iii. means for determining a cubic root of βL;
• iv. one or more third multipliers for multiplying the cubic root by βV;
• and
• v. one or more fourth multipliers for raising the product produced by the one or more third multipliers to a power 22m−Q to produce the multiple bit symbol that is cubic root of β;
• and
• C. a second processor for determining which symbols are in error in the data code word based on the multiple bit symbol that is the cubic root of β, the error location processor providing error location information to an error correction processor.