Galois field multiplier

• US 5,999,959 A
• Filed: 02/18/1998
• Issued: 12/07/1999
• Est. Priority Date: 02/18/1998
• Status: Expired due to Term

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Langer, Diana, Shen, Ba-Zhong, Weng, Lih-Jyh
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/025,419
• Time in Patent Office: 657 Days
• Field of Search: 708/492, 708/620, 708/625
• US Class Current: 708/492
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A Galois field multiplier for GF(2ⁿ), with n=2m, multiplies two n-bit polynomials to produce a(x)*b(x)=a(x)b(x) mod g(x), where g(x) is a generator polynomial for the Galois field and "*" represents multiplication over the Galois field, by treating each polynomial as the sum of two m-bit polynomials:

a(x)=a.sub.H (x)x.sup.m +a.sub.L (x) and b(x)=b.sub.H (x)x.sup.m +b.sub.L

(x),

with

a.sub.H (x)x.sup.m =[a.sub.n-1 x.sup.(n-1)-m +a.sub.n-2 x.sup.(n-2)-m + . .

. +a_m+1 x.sup.(m+1)-m +a_m ]x^m

a.sub.L (x)=a.sub.m-1 x.sup.m-1 +a.sub.m-2 x.sup.m-2 + . . . +a.sub.2

x² +a₁ x+a₀

and b_H and b_L having corresponding terms. Multiplying the two polynomials then becomes:

a(x)*b(x)=(a.sub.H (x)x.sup.m +a.sub.L (x))*(b.sub.H (x)x.sup.m +b.sub.L

(x))=[(a_H (x)b(x)_H)x^m mod g(x)

+(b.sub.H (x)a.sub.L (x)+a.sub.L (x)b.sub.L (x))]x.sup.m mod g(x)+a.sub.L

(x)b_L (x).

The Galois field multiplier produces four degree-(n-2) polynomial products, namely, a_H (x)b_H (x)=V₃ ; b_H (x)a_L (x)=V₂ ; a_H (x)b_L (x)=V₁ ; and a_L (x)b_L (x)=V₀, in parallel in four m-bit polynomial multipliers. Next, a modulo subsystem multiplies V₃ by x^m and performs a modulo g(x) operation on the product V₃ x^m by treating V₃ as V_3H x^m +V_3L, with V_3H including as a leading term 0x^n-1. The modulo operation is performed by appropriately cyclically shifting (m-(k-2)) versions of an n-bit symbol that consists of the coefficients of V_3H followed by m zeros, summing the results and adding the sum to an n-bit symbol that consists of the coefficients of V_3L, V_3H. The Galois field multiplier for GF(2ⁿ) with n=2m+1 operates in essentially the same manner, with a_L and b_L each including m+1 terms.

Claims

1. A Galois field multiplier for multiplying two polynomials a(x) and b(x) over GF(2ⁿ), with n=2m the Galois field multiplier including:

A. four m-bit polynomial multipliers to produce products a_H (x)b_H (x), b_L (x)a_L (x), a_H (x)b_L (x), and b_H (x)a_L (x) where

space="preserve" listing-type="equation">a.sub.H (x)x.sup.m =[a.sub.n-1 x.sup.(n-1)-m +a.sub.n-2 x.sup.(n-2)-m + . . . +a.sub.m+1 x+a.sub.m ]x.sup.m

space="preserve" listing-type="equation">a.sub.L (x)=a.sub.m-1 x.sup.m-1 +a.sub.m-2 x.sup.m-2 + . . . +a.sub.1 x+a.sub.0

space="preserve" listing-type="equation">b.sub.H (x)x.sup.m =[b.sub.n-1 x.sup.(n-1)-m +b.sub.n-2 x.sup.(n-2)-m + . . . +b.sub.m+1 x+b.sub.m ]x.sup.m

and

space="preserve" listing-type="equation">b.sub.L (x)=b.sub.m-1 x.sup.m-1 b.sub.m-2 x.sup.m-2 + . . . +b.sub.1 x+b.sub.0 ;

B. means for determining [a_H (x)b_H (x)]x^m mod g(x);

C. a plurality of Galois field adders for adding the products and [a_H (x)b_H (x)]x^m mod g(x) to produce the sum (a_H (x)b_H (x))x^m mod g(x)+(b_H (x)a_L (x)+a_H (x)b_L (x));

D. means for determining [[a_H (x)b_H (x)]x^m mod g(x)+(b_H (x)a_L (x)+a_H (x)b_L (x))]x^m mod g(x); and

E. an additional Galois field adder for producing the sum [[(a_H (x)b_H (x))x^m mod g(x)+(b_H (x)a_L (x)+a_H (x)b_L (x))]x^m mod g(x)]+b_L (x)a_L (x).

2. The Galois field multiplier of claim 1 wherein the means for determining [a_H (x)b_H (x)]x^m mod g(x) includes:

i. a register for holding coefficients of a_H (x)b_H (x)=V(x) as V_L V_H, where V_H x^m =(0+v_n-2 x.sup.(n-2)-m + . . . +v_m+1 x+v_m)x^m, and V_L =v_m-1 x^m-1 + . . . +v₁ x¹ +v₀ ;

ii. a plurality of shift registers for cyclically shifting n-bit symbols that include the m coefficients of V_H followed by m all-zero symbols by, respectively, m-j_i where j_i is the power of the i^th non-zero term of generator polynomial g(x) for i=k-2, k-1, . . . , 1 and k is the number of non-zero coefficients in the generator polynomial; and

iii. a plurality of Galois field adders for adding together the contents of the register and the plurality of shift registers.

3. The Galois field multiplier of claim 1 wherein the means for determining [a_H (x)b_H (x)]x^m mod g(x)+(b_H (x)a_L (x)+a_H (x)b_L (x))]x^m mod g(x) includes:

i. a register for holding coefficients of [a_H (x)b_H (x)]x^m mod g(x)+(b_H (x)a_L (x)+a_H (x)b_L (x))]=C(x) as C_3L C_3H, where C_3H x^m =(0+c_n-2 x.sup.(n-2)-m + . . . +c_m+1 x+c_m)x^m and C_3L =C_m-1 x^m-1 + . . . +v₁ x¹ +v₀ ;

ii. a plurality of shift registers for cyclically shifting n-bit symbols that include the m coefficients of C_3H followed by m all-zero symbols by, respectively, m-j_i where j_i is the power of the i^th non-zero term of generator polynomial g(x) for i=k-2, k-1 . . . 1 and k is the number of non-zero coefficients in the generator polynomial; and

iii. a plurality of Galois field adders for adding together the contents of the register and the plurality of shift registers.

4. A Galois field multiplier for multiplying two polynomials a(x) and b(x) over GF(2ⁿ), with n=2m+1, the Galois field multiplier including:

A. four (m+1)-bit polynomial multipliers to produce products a_H (x)b_H (x), b_L (x)a_L (x), a_H (x)b_L (x), and b_H (x)a_L (x) where

space="preserve" listing-type="equation">a.sub.H (x)x.sup.m+1 =[a.sub.n-1 x.sup.(n-1)-(m+1) +a.sub.n-2 x.sup.(n-2)-(m+1) + . . . +a.sub.m+1 ]x.sup.m+1

space="preserve" listing-type="equation">a.sub.L (x)=a.sub.m x.sup.m +a.sub.m- x.sup.m-1 + . . . +a.sub.1 x+a.sub.0

space="preserve" listing-type="equation">b.sub.H (x)x.sup.m+1 =[b.sub.n-1 x.sup.(n-1)-(m+1) + . . . +b.sub.m+1 ]x.sup.m+1 ;

B. a plurality of shift registers for

i. cyclically shifting a_H (x)b_H (x) by two bit positions to produce [a_H (x)b_H (x)]x²,

ii. cyclically shifting a_H (x)b_L (x) one bit position to produce [a_H (x)b_L (x)]x, and

iii. cyclically shifting b_H (x)a_L (x) one bit position to produce [b_H (x)a_L (x)]x,

B. means for determining [x² (a_H (x)b_H (x))]x^m mod g(x);

C. a plurality of Galois field adders for adding the products and [x² (a_H (x)b_H (x))]x^m mod g(x) to produce the sum [x² (a_H (x)b_H (x))]x^m mod g(x)+[x(b_H (x)a_L (x))+x(a_H (x)b_L (x))];

D. means for determining [x² (a_H (x)b_H (x))x^m mod g(x)+[x(b_H (x)a_L (x))+x(a_H (x)b_L (x))]x^m mod g(x); and

E. an additional Galois field adder for producing the sum [[x² (a_H (x)b_H (x))x^m mod g(x)+[x(b_H (x)a_L (x))+x(a_H (x)b_L (x))]x^m mod g(x)]+b_L (x)a_L (x).

5. The Galois field multiplier of claim 4 wherein the means for determining [x² (a_H (x)b_H (x)]x^m mod g(x) includes:

i. a register for holding coefficients of a_H (x)b_H (x)=V(x) as V_L V_H, where V_H =v_n-2 x.sup.(n-2)-(m+1) + . . . +v_m+1, and V_L =v_m x^m + . . . +v₁ x¹ +v₀ ;

ii. a plurality of shift registers for cyclically shifting n-bit symbols that include the m+1 coefficients of V_H followed by m all-zero symbols by, respectively, m-j_i where j_i is the power of the i^th non-zero term of generator polynomial g(x) for i=k-2, k-1, . . . , 1 and k is the number of non-zero coefficients in the generator polynomial; and

iii. a plurality of Galois field adders for adding together the contents of the register and the plurality of shift registers.

6. The Galois field multiplier of claim 4 wherein the means for determining [x² (a_H (x)b_H (x))x^m mod g(x)+x(b_H (x)a_L (x))+x(a_H (x)b_L (x))]x^m mod g(x) includes:

i. a register for holding coefficients of x² (a_H (x)b_H (x))x^m mod g(x)+x(b_H (x)a_L (x))+x(a_H (x)b.sub._L (x))=C(x) as C_L C_H, where C_H x^m =(0+c_n+2 x.sup.(n-2)-m + . . . +c_m+1 x+c_m)x^m and C_L =c_m-1 x^m-1 + . . . +v₁ x¹ +v₀ ;

ii. a plurality of shift registers for cyclically shifting n-bit symbols that include the m coefficients of C_H followed by m all-zero symbols by, respectively, m-j_i where j_i is the power of the i^th non-zero term of generator polynomial g(x) for i=k-2, k-1 . . . 1 and k is the number of non-zero coefficients in the generator polynomial; and

iii. a plurality of Galois field adders for adding together the contents of the register and the plurality of shift registers.