Method and apparatus for performing arithmetic operations on Galois fields and their extensions
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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(212) or a second GF(28) finite field. The arithmetic operations are selected either from a first group of operations associated with a first subfield GF(24) as cubically extended to the first finite field GF(212) or as quadratically extended to the second finite field GF(28), or selected from a second group of operations associated with a second subfield GF(26) as quadratically extended to the first finite field GF(212).
-
Citations
13 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A logic arrangement for multiplicatively combining a first r=r0 +r1 x+r2 x2 and second s=s0 +s1 x+s2 x2 equal-length bit strings in a first GF212) finite field to produce an output string t=t0 +t1 x+t2 x2 =r*s, for controlling errors in an electronically recorded digital message, said multiplicative combining operating over a first subfield GF(24) 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 r0, r1, and r2 and s0, s1, and s2 and outputs t0, t1, and t2 :
-
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(2.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.- View Dependent Claims (11, 12)
-
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.
-
Specification