Method and apparatus for performing arithmetic in large galois field GF(2.sup.n)

• US 5,689,452 A
• Filed: 10/31/1994
• Issued: 11/18/1997
• Est. Priority Date: 10/31/1994
• Status: Expired due to Term

• Current Assignee: Science & Technology Corporation
• Original Assignee: The University of New Mexico
• Inventors: Cameron, Kelly
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/332,235
• Time in Patent Office: 1,114 Days
• Field of Search: 364/746.1, 371/37.1
• US Class Current: 708/492
• CPC Class Codes: G06F 2207/7209 Calculation via subfield, i.e. the subfield being GF(q) with q a prime power, e.g. GF ((2**m)**n) via GF(2**m)
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: G06F 7/726 Inversion; Reciprocal calculation; Division of elements of a finite field

Abstract

A method and apparatus for decoding Reed-Solomon codes in large Galois Fields GF(2ⁿ) represents the finite field as a quadratic extension field of one or more subfields GF(2^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ⁿ), utilizing only operations from the subfield GF(2^m).

Claims

1. 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^pi) of a finite field GF(2ⁿ), comprising steps of:

a. factoring a composite number n into a set of factors p_i wherein the composite number n is a number of bits of each element in the finite field GF(2ⁿ);

b. forming a plurality of primitive polynomials F_i wherein each primitive polynomial is of a degree equal to p_i and defines a subfield GF(2^pi) of the finite field GF(2ⁿ); 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^pi) of the finite field GF(2ⁿ).

2. The method as claimed in claim 1 wherein one of the plurality of primitive polynomials is a primitive polynomial F₁ used to represent an extension field GF(2).

3. The method as claimed in claim 1 wherein the plurality of primitive polynomials includes one or more quadratic polynomials and one or more non-quadratic polynomials.

4. The method as claimed in claim 3 wherein the plurality of primitive polynomials includes a normalized polynomial having the form:

x² +x+β

=0.

5. The method as claimed in claim 1 wherein the plurality of primitive polynomials includes only quadratic polynomials.

6. The method as claimed in claim 5 wherein the plurality of primitive polynomials includes a normalized polynomial x² +x+β

=0.

7. The method as claimed in claim 1 wherein the plurality of primitive polynomials includes only non-quadratic polynomials.

8. 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^pi) of a finite field GF(2ⁿ), 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^pi) of the finite field GF(2ⁿ) and wherein each subfield GF(2^pi) of the plurality of subfields is defined by a primitive polynomial F_i of a degree equal to a factor p_i of a number of bits of each element in the finite field GF(2ⁿ).

9. The apparatus as claimed in claim 8 wherein one of the plurality of primitive polynomials is a primitive polynomial F₁ used to represent an extension field GF(2).

10. The apparatus as claimed in claim 8 wherein the plurality of primitive polynomials includes one or more quadratic polynomials and one or more non-quadratic polynomials.

11. The apparatus as claimed in claim 10 wherein the plurality of primitive polynomials includes a normalized polynomial x² +x+β

=0.

12. The apparatus as claimed in claim 8 wherein the plurality of primitive polynomials includes only quadratic polynomials.

13. The apparatus as claimed in claim 8 wherein the plurality of primitive polynomials includes only non-quadratic polynomials.

14. The apparatus as claimed in claim 8 wherein the arithmetic operation is a multiplication operation.

15. The apparatus as claimed in claim 14 wherein the multiplication operation is implemented using an equation

16. The apparatus as claimed in claim 14 wherein the multiplication operation is implemented using an equation

17. The apparatus as claimed in claim 8 wherein the arithmetic operation is a division operation.

18. The apparatus as claimed in claim 8 wherein the arithmetic operation is an inverse operation.

19. The apparatus as claimed in claim 8 wherein the arithmetic operation is a square root operation.

20. The apparatus as claimed in claim 8 wherein the arithmetic operation is a conjugate operation.

21. The apparatus as claimed in claim 8 wherein the arithmetic operation is a cube root operation.

22. The apparatus as claimed in claim 8 wherein the arithmetic operation is a discrete logarithm operation.

23. 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^pi) of a finite field GF(2ⁿ), comprising steps of:

a. setting a number of bits in the field, n, equal to Π

p_i, a composite number, where p_i is a set of factors of the number of bits in the field;

b. forming a primitive polynomial F₁ over a finite field GF(2) used to represent a p₁^th extension field of the finite field GF(2);

c. forming a primitive polynomial F₂ over a finite field GF(2^pi) used to represent a p₂^th extension field of the finite field GF(2^pi);

d. repeating step c for all factors, p_i, of the number of bits in the field, n, until a desired finite field GF(2ⁿ) 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^pi) of the finite field GF(2ⁿ).

24. The method according to claim 23 wherein the set of factors of the number of bits in the field includes a factor that is repeated.

25. The method as claimed in claim 23 wherein the plurality of primitive polynomials includes one or more quadratic polynomials and one or more non-quadratic polynomials.

26. The method as claimed in claim 25 wherein the plurality of primitive polynomials includes a normalized polynomial having the form:

x² +x+β

=0.

27. The method as claimed in claim 23 wherein the plurality of primitive polynomials includes only quadratic polynomials.

28. The method as claimed in claim 27 wherein the plurality of primitive polynomials includes a normalized polynomial x² +x+β

=0.

29. The method as claimed in claim 23 wherein the plurality of primitive polynomials includes only non-quadratic polynomials.

30. 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^pi) of a finite field GF(2ⁿ) 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^pi) of the finite field GF(2ⁿ) wherein a first subfield GF(2) of the plurality of subfields GF(2^pi) is represented by a primitive polynomial F₁ having a degree of one, and wherein each of a plurality of successive primitive polynomials F_i represents a successive one of the plurality of subfields GF(2^pi) wherein each of the plurality of successive primitive polynomials F_i corresponds to each factor pi of a number of bits in the field n.

31. The apparatus according to claim 30 wherein the plurality of primitive polynomials includes one or more quadratic polynomials and one or more non-quadratic polynomials.

32. The apparatus according to claim 30 wherein the plurality of primitive polynomials includes only quadratic polynomials.

33. The apparatus according to claim 30 wherein the plurality of primitive polynomials includes only non-quadratic polynomials.

34. The apparatus as claimed in claim 30 wherein the plurality of primitive polynomials includes a normalized polynomial x² +x+β

=0.

35. The apparatus as claimed in claim 30 wherein the arithmetic operation is a multiplication operation.

36. The apparatus as claimed in claim 35 wherein the multiplication operation is implemented using an equation

37. The apparatus as claimed in claim 35 wherein the multiplication operation is implemented using an equation

38. The apparatus as claimed in claim 30 wherein the arithmetic operation is an inverse operation.

39. The apparatus as claimed in claim 30 wherein the arithmetic operation is a square root operation.

40. The apparatus as claimed in claim 30 wherein the arithmetic operation is a conjugate operation.

41. The apparatus as claimed in claim 30 wherein the arithmetic operation is a discrete logarithm operation.