Techniques for performing reduced complexity galois field arithmetic for correcting errors
View Patent ↗Techniques are provided for performing Galois field arithmetic to detect errors in digital data stored on disks. Two 12-bit numbers or two 10-bit numbers are multiplied together in Galois field using tower arithmetic. In the 12-bit embodiment, a base field GF(2) is first extended to GF(2 3 ), GF(2 3 ) is extended to a first quadratic extension GF(2 6 ), and GF(2 6 ) is extended to a second quadratic extension GF(2 12 ). In the 10-bit embodiment, the base field GF(2) is first extended to GF(2 5 ), and GF(2 5 ) is extended to a quadratic extension GF(2 10 ). Each of the extensions for the 10-bit and 12-bit embodiments is performed using an irreducible polynomial. All of the polynomials used to generate the first and the second quadratic extensions of the Galois field are in the form x 2 +x+K, where K is an element of the ground field whose absolute trace equals 1.
1. An integrated circuit having a memory and a microprocessor that performs Galois field arithmetic on 12-bit numbers read from a digital data stored on a disk, the integrated circuit comprising:
an arithmetic unit operable by the microprocessor to extend for the 12-bit numbers a base field GF(2) to GF(2 3 ) using a polynomial a3+a+1 over the base field GF(2),
wherein the arithmetic unit is operable by the microprocessor to extend for the 12-bit numbers GF(2 3 ) to a first quadratic extension GF(2 6 ) using a polynomial b2+b+ai, and values for ai are selected from a first list comprising {trace(ai), i=0, . . . , 6}=[1, 0, 0, 1, 0, 1, 1] wherein trace(ai) =1, and
wherein the arithmetic unit is operable by the microprocessor to extend for the 12-bit numbers GF(2 6 ) to a second quadratic extension GF(2 12 ) using a polynomial c2+c+bi, and values for bi are selected from a second list comprising {trace(trace(bi), i=0, . . . , 62}=[0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0], wherein trace(trace(bi))=1;
wherein the values for ai and the first list produce a first set of irreducible polynomials, and the values for bi and the second list produce a second set of irreducible polynomials; and
wherein the first set of irreducible polynomials and the second set of irreducible polynomials are used to detect errors in digital data stored on a disk.
2. An integrated circuit having a memory and a microprocessor that performs Galois field arithmetic on 12-bit numbers read from a digital data stored on a disk, the integrated circuit comprising:
an arithmetic unit operable by the microprocessor to extend for the 12-bit numbers a base field GF(2) to GF(2 3 ) using a polynomial A3+A2+1 over the base field GF(2),
wherein the arithmetic unit is operable by the microprocessor to extend for the 12-bit numbers GF(2 3 ) to a first quadratic extension GF(2 6 ) using a polynomial B2+B+Ai, and values for Ai are selected from a first list comprising {trace(Ai), i=0, . . . , 6}=[1, 1, 1, 0, 1, 0, 0] where trace(Ai)=1, and
wherein the arithmetic unit is operable by the microprocessor to extend for the 12-bit numbers GF(2 6 ) to a second quadratic extension GF(2 12 ) using a polynomial C2+C +Bi, and values for Bi are selected from a second list comprising {trace(trace(Bi), i =0, . . . ,62}=[0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0], wherein trace(trace(Bi))=1;
wherein the values for Ai and the first list produce a first set of irreducible polynomials, and the values for Bi and the second list produce a second set of irreducible polynomials; and
wherein the first set of irreducible polynomials and the second set of irreducible polynomials are used to detect errors in digital data stored on a disk.
3. An integrated circuit having a memory and a microprocessor that performs Galois field arithmetic on 10-bit numbers read from a digital data stored on a disk, the integrated circuit comprising:
an arithmetic unit operable by the microprocessor to extend for the 10-bit numbers a base field GF(2) to GF(2 5 ) using an irreducible polynomial over the base field GF(2),
wherein the arithmetic unit is operable by the microprocessor to extend for the 10-bit numbers GF(2 5 ) to a quadratic extension GF(2 10 ) using a polynomial b2+b+ai, and values for ai are selected from a list wherein trace(ai)=1;
wherein the irreducible polynomial is a5+a2+1, and the values for ai in the list correspond to {trace(ai), i=0, . . . , 30}=[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0] wherein trace(ai)=1;
wherein the values for ai and the list produce a set of irreducible polynomials used to detect errors in digital data stored on a disk.
4. The integrated circuit according to claim 3 wherein the irreducible polynomial is a5+a3+1, and the values for ai in the list correspond to {trace(ai), i=0, . . . , 30}=[1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0] Wherein trace(ai)=1.
5. The integrated circuit according to claim 3 wherein the irreducible polynomial is a5+a3+a2+a+1, and the values for ai in the list correspond to {trace(ai), i=0, . . . , 30}=[1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1] wherein trace(ai)=1.
6. The integrated circuit according to claim 3 wherein the irreducible polynomial is a5+a4+a2+a+1, and the values for ai in the list correspond to {trace(ai), i=0, . . . , 30}=[1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1] wherein trace(ai)=1.
7. The integrated circuit according to claim 3 wherein the irreducible polynomial is a5+a4+a3+a+1, and the values for ai in the list correspond to {trace(ai), i=0, . . . , 30}=[1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1] wherein trace(ai)=1.
8. The integrated circuit according to claim 3 wherein the irreducible polynomial is a5+a4+a3+a2+1, and the values for ai in the list correspond to {trace(ai), i=0, . . . , 30}=[1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0] wherein trace(ai)=1.