Compact galois field multiplier

• US 4,847,801 A
• Filed: 10/26/1987
• Issued: 07/11/1989
• Est. Priority Date: 10/26/1987
• Status: Expired due to Fees

• Current Assignee: Eastman Kodak Company
• Original Assignee: Cyclotomics, Inc.
• Inventors: Tong, Po
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Shaw, Dale M.
• Application Number:
  US07/112,335
• Time in Patent Office: 624 Days
• Field of Search: 364/746.1, 364/754
• 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: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

Multiplication of two mq-bit bytes (in GF2^mq) is reduced modulus an irreducible polynomial in GF2^m of degree q to multiplication among two sets of q m bit bytes (in GF2^m) in order to simplify hardware and reduce costs, by distributing the computation among a small number of programmable read only memories (PROMs) and adders.

Claims

1. A Galois field multiplier wherein mq-bit multiplier and multiplicand bytes are each partitioned into a plurality of q m-bit sub-bytes, q and m each being integers greater than zero, and wherein multiplication among selected groups of said multiplier and multiplicand sub-bytes is distributed among a plurality of m-bit multipliers which each compute m-bit intermediate product sub-bytes therefrom, and wherein computation of an mq-bit product is partitioned into computation of q m-bit final product sub-bytes by q respective adders from respective q sets of said m-bit intermediate product sub-bytes.

2. The multiplier of claim 1 wherein said respective q sets of said m-bit intermediate product sub-bytes are selected in accordance with reduction of the product of said mq-bit multiplier and multiplicand bytes into an m-bit field.

3. The multiplier of claim 2 wherein said reduction is modulus an irreducible polynomial of degree q in Galois field GF2^m.

4. The multiplier of claim 1 wherein said plurality of m-bit multipliers comprises a plurality of programmable read only memories each containing the multiplication table of Galois field GF2^m.

5. The multiplier of claim 3 wherein at least one of said m-bit multipliers multiplies at least one of said m-bit intermediate product sub-bytes by at least one of the coefficients of said irreducible polynomial.

13. The multiplier of claim 3, wherein m=3, q=3 and said irreducible polynomial is β

+β

z+z³, where β

is the GF8 element (111).

16. The multiplier of claim 3, wherein m=2, q=2 and said irreducible polynomial is z² +z+ξ

, where ξ

is the GF4 element (10).

6. A Galois field GF2^mq multiplier which multiplies mq-bit multiplier and multiplicand bytes A and B together to produce an mq-bit product byte C, said product byte C comprising a plurality of q m-bit product sub-bytes c₀ and c_1-1, said multiplier comprising:

means for partitioning each of said mq-bit multiplier and multiplicand bytes A and B into a plurality of q m-bit multiplier and multiplicand sub-bytes a₀ through a_q-1 and b₀ through b_q-1, respectively;

a plurality of multiplier means programmed in accordance with a Galois field GF2^m multiplication table and receiving respective q groups of said multiplier and multiplicand sub-bytes and to compute therefrom respective q sets of sub-products a_i b_j ;

a plurality of adder means, each of said adder means receiving a respective plurality of sub-products selected from among said q sets of sub-products a_i b_j, and to compute, from said respective plurality, one of said q product sub-bytes c_i, whereby said adder means computes said q product sub-bytes c₀ through c_q-1 of said product C.

7. The multiplier of claim 6 wherein said q product sub-bytes c₀ through c_q-1 are coefficients of ##EQU2## reduced modulus an irreducible polynomial GF2^m, i and j being positive integers, said irreducible polynomial being of degree q.

8. The multiplier of claim 6 wherein each of said plurality of multiplier means comprises a programmable read only memory.

9. The multiplier of claim 7 wherein at least one of said plurality of multiplier means multiplies at least one of said sub-products a_i b_j by at least one of the coefficients of said irreducible polynomial.

14. The multiplier of claim 7, wherein m=3, q=3 and said irreducible polynomial is β

+β

z+z³, where β

is the GF8 element (111).

17. The multiplier of claim 7, wherein m=2, q=2 and said irreducible polynomial is z² +z+ξ

, where ξ

is the GF4 element (10).

10. A GF2^mq multiplier which multiplies two mq-bit bytes A and B together to produce an mq-bit byte product C, m and q each being integers greater than zero, said multiplier comprising:

means for partitioning each of said mq-bit bytes A and B into q m-bit sub-bytes, wherein A is partitioned into the set of q sub-bytes a_i and B is partitioned into the set of q sub-bytes b_i where i is an integer and ranges from 1 to q-1;

a plurality of multiplier means programmed in accordance with GF2^m multiplication table;

means for distributing q groups of said sub-bytes a_i and b_i to corresponding ones of said multiplier means, each of said multiplier means computing m-bit byte sub-products comprising combinations of the m-bit sub-bytes within the corresponding group;

a plurality of Galois field adder means, each of said adder means receiving at least two of said m-bit byte sub-products, each of said adder means computing a sum equal to a corresponding one of said q product sub-bytes c_i, so that said plurality of adder means together compute all of the q product sub-bytes c_i comprising the mq-bit byte product C.

11. The multiplier of claim 10 wherein said products are coefficients of a polynomial ##EQU3## reduced modulus an irreducible polynomial of degree q in GF2^m.

12. The multiplier of claim 10 wherein each of said multipliers comprises a programmable read only memory containing micro coded instructions representative of the multiplication table of GF2^m.

15. The multiplier of claim 11, wherein m=3, q=3 and said irreducible polynomial is β

+β

z+z³, where β

is the GF8 element (111).

18. The multiplier of claim 11, wherein m=2, q=2 and said irreducible polynomial is z² +z+ξ

, where ξ

is the GF4 element (10).