Method and apparatus for performing arithmetic in large galois field GF(2.sup.n)
AssigneeUniversity of New Mexico
InventorKelly Cameron
Life of this patent
Estimating the term…
Abstract
A method and apparatus for decoding Reed-Solomon codes in large Galois Fields GF(2.sup.n) represents the finite field as a quadratic extension field of one or more subfields GF(2.sup.m). This type of field representation allows embedded subfields, as well as the primary extension field to be simultaneously represented in normal form. The basic arithmetic operations for the extension field are written solely in terms of operations performed in one or more subfields. The operations of multiplication, inverse, square, square root and conjugation are performed in GF(2.sup.n), utilizing only operations from the subfield GF(2.sup.m).
Claims41
A method of controlling errors in an electronically communicated 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 GF(2.sup.pi) of a finite field GF(2.sup.n), comprising steps of:
- a. factoring a composite number n into a set of factors p.sub.i wherein the composite number n is a number of bits of each element in the finite field GF(2.sup.n);
- b. forming a plurality of primitive polynomials F.sub.i wherein each primitive polynomial is of a degree equal to p.sub.i and defines a subfield GF(2.sup.pi) of the finite field GF(2.sup.n);
- and
- c. performing at least one of the plurality of predetermined arithmetic operations on the data message by utilizing an arithmetic circuit coupled to receive the data message, wherein the arithmetic operation is performed in one or more of the plurality of subfields GF(2.sup.pi) of the finite field GF(2.sup.n).
An apparatus for controlling errors in an electronically communicated 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 GF(2.sup.pi) of a finite field GF(2.sup.n), comprising:
- an arithmetic circuit for performing at least one of the plurality of predetermined arithmetic operations on the data message, wherein the arithmetic operation is performed in one or more of the plurality of subfields GF(2.sup.pi) of the finite field GF(2.sup.n) and wherein each subfield GF(2.sup.pi) of the plurality of subfields is defined by a primitive polynomial F.sub.i of a degree equal to a factor p.sub.i of a number of bits of each element in the finite field GF(2.sup.n).
A method controlling errors in an electronically communicated digital data message by performing at least one of a plurality of arithmetic operations on the data message in one or more of a plurality of subfields GF(2.sup.pi) of a finite field GF(2.sup.n), comprising steps of:
- a. setting a number of bits in the field, n, equal to .PI.p.sub.i, a composite number, where p.sub.i is a set of factors of the number of bits in the field;
- b. forming a primitive polynomial F.sub.1 over a finite field GF(2) used to represent a p.sub.1.sup.th extension field of the finite field GF(2);
- c. forming a primitive polynomial F.sub.2 over a finite field GF(2.sup.pi) used to represent a p.sub.2.sup.th extension field of the finite field GF(2.sup.pi);
- d. repeating step c for all factors, p.sub.i, of the number of bits in the field, n, until a desired finite field GF(2.sup.n) is constructed;
- and
- e. providing an arithmetic circuit for performing at least one of the plurality of arithmetic operations on the data message in one or more of the plurality of subfields GF(2.sup.pi) of the finite field GF(2.sup.n).
An apparatus for controlling errors in an electronically communicated digital data message by performing at least one of a plurality of arithmetic operations on the data message in one or more of a plurality of subfields GF(2.sup.pi) of a finite field GF(2.sup.n) comprising:
- an arithmetic circuit wherein the arithmetic circuit performs at least one of the plurality of arithmetic operations on the data message in one or more of the plurality of subfields GF(2.sup.pi) of the finite field GF(2.sup.n) wherein a first subfield GF(2) of the plurality of subfields GF(2.sup.pi) is represented by a primitive polynomial F.sub.1 having a degree of one, and wherein each of a plurality of successive primitive polynomials F.sub.i represents a successive one of the plurality of subfields GF(2.sup.pi) wherein each of the plurality of successive primitive polynomials F.sub.i corresponds to each factor pi of a number of bits in the field n.
Dependencies are inferred from the claim text.