Method and apparatus for performing arithmetic operations on Galois fields and their extensions

• US 6,141,786 A
• Filed: 06/04/1998
• Issued: 10/31/2000
• Est. Priority Date: 06/04/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Winograd, Shmuel, Hassner, Martin Aureliano, Cox, Charles Edwin, Trager, Barry Marshall
• Primary Examiner(s): Cady, Albert De
• Assistant Examiner(s): LAMARRE, GUY J
• Application Number:
  US09/090,511
• Time in Patent Office: 880 Days
• Field of Search: 714/784, 714/785, 714/781, 714/763, 708/492
• US Class Current: 714/763
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

The invention relates to an arithmetic unit (AU) in combination with an algebraic block ECC decoder for controlling errors in an electronically recorded digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields of a first GF(2¹²) or a second GF(2⁸) finite field. The arithmetic operations are selected either from a first group of operations associated with a first subfield GF(2⁴) as cubically extended to the first finite field GF(2¹²) or as quadratically extended to the second finite field GF(2⁸), or selected from a second group of operations associated with a second subfield GF(2⁶) as quadratically extended to the first finite field GF(2¹²).

Claims

1. A method for controlling errors in an electronically recorded digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields of a first GF(2.sup.(m)(p)) or a second GF(2.sup.(m)(q)) finite field, using an arithmetic unit including a plurality of multiplier gates and a plurality of addition gates, said method comprising steps of:

(a) factoring a first, second, and third composite number (m)(p), (m)(q), (p)(q) respectively wherein the first and second composite numbers are the number of bits designating each element in the first GF(2.sup.(m)(p)) and second GF(2.sup.(m)(q)) finite fields;

(b) forming a first primitive polynomial cubically extending each element in a first subfield GF(2.sup.(m)) to the first finite field GF(2.sup.(m)(p)), forming a second primitive polynomial quadratically extending each element in the first subfield GF(2.sup.(m)) to the second finite field GF(2.sup.(m)(q)), q≠

p, and forming a third primitive polynomial for quadratically extending each element in a second subfield GF(2.sup.(p)(q)) to the first finite field GF(2.sup.(m(p)); and

(c) performing at least one of the plurality of predetermined arithmetic operations on the data message by utilizing the arithmetic unit coupled to receive the data message, said arithmetic operations being selected either from a first group of operations associated with the first subfield as cubically extended to the first finite field or as quadratically extended to the second finite field, or selected from a second group of operations associated with the second subfield as quadratically extended to the first finite field, wherein the selected arithmetic operation is performed in the associated subfield.

2. The method for controlling errors according to claim 1, wherein the first and second finite fields are respectively GF(2¹²) and GF(2⁸), and further wherein the first and second subfields are respectively GF(2⁴) and GF(2⁶).

3. The method for controlling errors according to claim 1, wherein the first group of operations includes multiplication, the inverse function, addition, and table-driven logarithmic functions, and further wherein the second group of operations includes the inverse function.

4. The method for controlling errors according to claim 1, wherein the first primitive polynomial is of the form (v³ +v+1), and further wherein the second and third primitive polynomials are of the form (u² +u+1).

5. The method for controlling errors according to claim 1, wherein said method further comprises the steps of selectively recording on a storage medium said data messages as codewords in an algebraic block error correction code (ECC) decodable over the first finite field, reading selected recorded data messages, detecting any nonzero syndromes, and ascertaining the location of any errors in messages with nonzero syndromes.

6. The method according to claim 5, wherein said ascertaining of error location step includes the steps of performing at least one operation selected from the first group utilizing the arithmetic unit, said first group consisting of multiplication, the inverse function, addition, and table-driven logarithmic functions, said arithmetic operation being performed in the first subfield GF(2⁴).

7. The method according to claim 5, wherein said ascertaining of error location step includes the steps of performing at least one operation selected from the second group utilizing the arithmetic unit, said second group consisting of table-driven logarithmic functions, said arithmetic operation being performed in the second subfield GF(2⁶) quadratically extended to the first finite field GF(2¹²).

8. The method according to claim 5, wherein the step of selectively recording data messages as codewords in an ECC decodable over a first GF(2¹²) or a second GF(2⁸) finite field, and wherein the steps of detecting nonzero syndromes and ascertaining error locations include arithmetic operations selected from the first group and performed in the associated first GF(2⁴) subfield.

9. A logic arrangement for multiplicatively combining a first r=r₀ +r₁ x+r₂ x² and second s=s₀ +s₁ x+s₂ x² equal-length bit strings in a first GF2¹²) finite field to produce an output string t=t₀ +t₁ x+t₂ x² =r*s, for controlling errors in an electronically recorded digital message, said multiplicative combining operating over a first subfield GF(2⁴) cubically extended to the first finite field, said arrangement comprising a plurality of multiplier gates and a plurality of addition gates arranged in satisfaction of the following logical relations such that for inputs r₀, r₁, and r₂ and s₀, s₁, and s₂ and outputs t₀, t₁, and t₂ :

space="preserve" listing-type="equation">t.sub.0 =(r.sub.0 s.sub.0 +r.sub.1 s.sub.1)+r.sub.2 s.sub.2 +(r.sub.1 +r.sub.2)(s.sub.1 +s.sub.2)

space="preserve" listing-type="equation">t.sub.1 =r.sub.0 s.sub.0 +(r.sub.1 +r.sub.2)(s.sub.1 +s.sub.2)+(r.sub.0 +r.sub.1)(s.sub.0 +s.sub.1)

space="preserve" listing-type="equation">t.sub.2 =(r.sub.0 s.sub.0 +r.sub.1 s.sub.1)+(r.sub.0 +r.sub.2)(s.sub.0 +s.sub.2).

10.

10. An arithmetic unit in combination with an algebraic block ECC decoder for controlling errors in an electronically recorded digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields of a first GF(2.sup.(m)(p)) or a second GF(2.sup.(m)(q)) finite field, comprising:

circuits responsive to the data message as received by the ECC decoder for performing at least one of the plurality of predetermined arithmetic operations on the data message, said arithmetic operations being selected either from a first group of operations associated with a first subfield GF(2.sup.(m)) as cubically extended to the first finite field GF(₂.sup.(m)(p)) or as quadratically extended to the second finite field GF(2.sup.(m)(q)), q≠

p, or selected from a second group of operations associated with a second subfield GF(2.sup.(p)(q)) as quadratically extended to the first finite field GF(2.sup.(m)(p)), wherein the selected arithmetic operation is performed in the associated subfield.

11. The arithmetic unit according to claim 10, wherein the first finite field is GF(2¹²), the second finite field is GF(2⁸), the first subfield is GF(2⁴), and the second subfield is GF(2⁶).

12. The arithmetic unit according to claim 10, wherein said circuits include logic for logarithmically processing a numerical magnitude r, where r=gL≠

0 in a finite field GF(2^2p) as a quadratic extension of GF(2^p), L lying in the range 0≦

L<

M, M being factorable, M=(2^2p -1)=J(K), and including reduced size first and second logarithmic tables.

13. An article of manufacture comprising a machine-readable memory having stored therein indicia of a plurality of processor executable control program steps for controlling errors in an electronically recorded digital data message by performing at least one of a plurality of predetermined arithmetic operations on the data message in one or more of a plurality of subfields of a first GF(2.sup.(m)(p)) or a second GF(2.sup.(m)(q)) finite field, said plurality of indicia of control program steps include:

(a) indicia of a control program step for factoring a first, second, and third composite number (m)(p), (m)(q), (p)(q) respectively wherein the first and second composite numbers are the number of bits designating each element in the first GF(2.sup.(m)(p)) and second GF(2.sup.(m)(q)) finite fields;

(b) indicia of a control program step for forming a first primitive polynomial cubically extending each element in a first subfield GF(2.sup.(m)) to the first finite field GF(2.sup.(m)(p)), forming a second primitive polynomial quadratically extending each element in the first subfield GF(2.sup.(m)) to the second finite field GF(2.sup.(m)(q)), q≠

p, and forming a third primitive polynomial for quadratically extending each element in a second subfield GF(2.sup.(p)(q)) to the first finite field GF(2.sup.(m)(p)); and

(c) indicia of a control program step for performing at least one of the plurality of predetermined arithmetic operations on the data message by utilizing an arithmetic unit coupled to receive the data message, said arithmetic operations being selected either from a first group of operations associated with the first subfield as cubically extended to the first finite field or as quadratically extended to the second finite field, or selected from a second group of operations associated with the second subfield as quadratically extended to the first finite field, wherein the selected arithmetic operation is performed in the associated subfield.