Universal galois field multiplier

• US 5,768,168 A
• Filed: 05/30/1996
• Issued: 06/16/1998
• Est. Priority Date: 05/30/1996
• Status: Expired due to Term

• Current Assignee: LG Semicon Co Ltd (SK Hynix Inc.)
• Original Assignee: LG Semicon Co Ltd (SK Hynix Inc.)
• Inventors: Im, Jin-Hyeok
• Primary Examiner(s): Elmore, Reba I.
• Assistant Examiner(s): Lewis, Monica
• Application Number:
  US08/656,784
• Time in Patent Office: 747 Days
• Field of Search: 364/746.1, 371/37, 371/40.1, 371/37.1
• 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 universal Galois field multiplier which is adaptable to any form of polynomial having a predetermined n-order when it is controlled by a coefficient of polynomial which defines a Galois field, which includes second AND-gates each for ANDing a corresponding bit value of the multiplicand and one bit value among the remaining bits of the multiplier; first XOR-gates each for XORing a corresponding leftwardly rotated output value of the second AND-gates and a corresponding output value of the preceding operation unit; third AND-gates each for ANDing the corresponding coefficient value of the generating polynomial and a most significant bit value among the output values of the preceding operation unit; and second XOR-gates for XORing output values of the third AND-gates and the first XOR-gates, wherein the second XOR-gates become effective in accordance with outputs of the third AND-gates.

Claims

1. A universal Galois field multiplier, comprising:

a first operation unit including first AND-gates for ANDing a corresponding bit value of a multiplicand and a most significant bit value of a multiplier; and

a plurality of second operation units connected to the first operation unit or a preceding operation unit for logically operating upon a bit value of a multiplicand and the second most significant bit to a least significant bit, respectively, of the multiplier in accordance with coefficient values of a generating polynomial which defines a Galois field, said second operation unit including;

second AND-gates each for ANDing a corresponding bit value of the multiplicand and one bit value among the remaining bits of the multiplier;

first XOR-gates each for XORing a corresponding leftwardly rotated output value of the second AND-gates and a corresponding output value of the preceding operation unit;

third AND-gates each for ANDing the corresponding coefficient value of the generating polynomial and a most significant bit value among the output values of the preceding operation unit; and

second XOR-gates for XORing output values of the third AND-gates and the first XOR-gates, wherein the second XOR-gates become effective in accordance with outputs of the third AND-gates.

2. The multiplier of claim 1, wherein said second XOR-gates are connected to first XOR-gates and third AND-gates except for the first XOR-gate corresponding to the least significant bit among the first XOR-gates.

3. The multiplier of claim 1, wherein said universal Galois field multiplier is connected to a memory device which receives the generating polynomial, stores the coefficients of the inputted generating polynomial, and outputs the coefficients to the second operation units.

4. A universal Galois field multiplier, comprising:

a first operation unit including first AND-gates for ANDing a corresponding bit value of a multiplicand and a most significant bit value of a multiplier; and

a plurality of second operation units connected to the first operation unit or a preceding operation unit for logically operating upon a bit value of a multiplicand and the second most significant bit to a least significant bit, respectively, of the multiplier in accordance with coefficient values of a generating polynomial which defines a Galois field, said second operation unit including;

second AND-gates each for ANDing a corresponding bit value of the multiplicand and one bit value among the remaining bits of the multiplier;

a first XOR-gate for XORing an output value of a second AND-gate among the second AND-gates and an output value of a preceding operation unit which is leftwardly rotated;

third AND-gates for ANDing a coefficient value of the generating polynomial, and a most significant bit value among output values of the predetermined operation unit; and

second XOR-gates each for XORing a corresponding output value of the third AND-gates, a corresponding output value of the second AND-gates, and a corresponding output value of a preceding operation unit which is leftwardly rotated.

5. The multiplier of claim 4, wherein said XORing gate XOR'"'"'s an output value of a preceding operation unit which is leftwardly rotated, and a least significant value among output values of the second AND-gates.

6. The multiplier of claim 4, wherein said universal Galois field multiplier is connected to a memory device which receives the generating polynomial, stores the coefficients of the inputted generating polynomial, and outputs the coefficients to the second operation units.

7. A universal Galois field multiplier, comprising:

a first operation unit including first AND-gates for ANDing a corresponding bit value of a multiplicand and a most significant bit value of a multiplier; and

a plurality of second operation units connected to the first operation unit or a preceding operation unit for logically operating upon a bit value of a multiplicand and the second most significant bit to a least significant bit, respectively, of the multiplier in accordance with coefficient values of a generating polynomial which defines a Galois field, said second operation unit including;

second AND-gates each for ANDing a corresponding bit value of the multiplicand and one bit value among the remaining bits of the multiplier;

first XOR-gates each for XORing a corresponding leftwardly rotated output value of the second AND-gates and a corresponding output value of the preceding operation unit;

third AND-gates for ANDing a corresponding coefficient value of a generating polynomial and a most significant bit value among output values of a preceding operation unit when at least one term among opposing terms of generating polynomials which define a Galois field has a coefficient value of one (1); and

second XOR-gates for XORing output values of the third AND-gates and the first XOR-gates, wherein the second XOR-gates become effective in accordance with outputs of the third AND-gates.

8. The multiplier of claim 7, wherein said first XOR-gate are directed to outputting a leftwardly rotated output value to a following operation unit when the third AND-gates corresponding to the first XOR-gates are not present.

9. The multiplier of claim 7, wherein said universal Galois field multiplier includes a memory device which receives a generating polynomial, stores coefficients of the inputted generating polynomial, and outputs the coefficients to a universal Galois field multiplier.

10. The multiplier of claim 7, wherein said generating polynomial is one of G3(X) (G3(X)=X⁴ +X+1) and G4(X) (G4(X)=X⁴ +X³ +1) which define a Galois field GF(16).

11. A reconfigurable Galois field multiplier comprising:

zeroith to n^th power means for using at least one logical gate to represent a zeroith to n^th power of a variable, X, respectively, in a first polynomial f₁ (X)=1+k₁ X+k₂ X² +k₃ X³ + . . . k_n-1 X^n-1 +Xⁿ, where n is an integer and n>

1, where k_j is an integer equal to one or zero, and where j is an integer and j=1, 2, . . . (n-1); and

first to (n-1)^th coefficient means for selectively setting said coefficients k₁, k₂, k₃, . . . k_n-1 at a value of either one or zero to selectively nullify an effect of said first to (n-1)^th power means so as to achieve multiplication according to a second polynomial having the same or fewer terms than said polynomial f₁ (X).

12. The reconfigurable Galois field multiplier as in claim 11, wherein n=8, said first polynomial f₁ (X)=1+k₁ X+k₂ X² +k₃ X³ +k₄ X⁴ +k₅ X⁵ +k₆ X⁶ +k₇ X⁷ +X⁸, and said first to (n-1)^th coefficient means are operable to selectively nullify terms of f₁ (X) so that said second polynomial is f₂ (X)=1+X+X² +X⁷ +X⁸.

13. The reconfigurable Galois field multiplier as in claim 11, wherein n=8, said first polynomial f₁ (X)=1+k₁ X+k₂ X² +k₃ X³ +k₄ X⁴ +k₅ X⁵ +k₆ X⁶ +k₇ X⁷ +X⁸, and said first to (n-1)^th coefficient means are operable to selectively nullify terms of f₁ (X) so that said second polynomial is f₂ (X)=1+X² +X³ +X⁴ +X⁸.

14. The reconfigurable Galois field multiplier as in claim 11, wherein n=4, said first polynomial f₁ (X)=1+k₁ X+k₂ X² +k₃ X³ +X⁴, and said first to (n-1)^th coefficient means are operable to selectively nullify terms of f₁ (X) so that said second polynomial is f₂ (X)=1+X³ +X⁴.

15. The reconfigurable Galois field multiplier as in claim 11, wherein n=4, said first polynomial f₁ (X)=1+k₁ X+k₂ X² +k₃ X³ +X⁴, and said first to (n-1)^th coefficient means are operable to selectively nullify terms of f₁ (X) so that said second polynomial is f₂ (X)=1+X+X⁴.

16. The reconfigurable Galois field multiplier as in claim 11, further comprising a memory for storing values of said coefficients k₁, k₂, k₃, . . . k_n-1, said first to (n-1)^th coefficient means being operable according to said coefficients k₁, k₂, . . . k_n-1 stored in said memory.