Compact galois field multiplier

Claim 2

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.

Claim 3

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.

Claim 4

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

Claim 5

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 .

Claim 6

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.

Claim 7

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 0 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 0 through a q-1 and b 0 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 0 through c q-1 of said product C.

Claim 8

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 0 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 0 through a q-1 and b 0 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 0 through c q-1 of said product C.

Claim 9

The multiplier of claim 6 wherein said q product sub-bytes c 0 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.

Claim 10

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

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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 .

Claim 15

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 .

Claim 16

The multiplier of claim 3, wherein m=3, q=3 and said irreducible polynomial is β+βz+z 3 , where β is the GF8 element (111).

Claim 17

The multiplier of claim 7, wherein m=3, q=3 and said irreducible polynomial is β+βz+z 3 , where β is the GF8 element (111).

Claim 18

The multiplier of claim 11, wherein m=3, q=3 and said irreducible polynomial is β+βz+z 3 , where β is the GF8 element (111).

Claim 19

The multiplier of claim 3, wherein m=2, q=2 and said irreducible polynomial is z 2 +z+ξ, where ξ is the GF4 element (10).

Claim 20

The multiplier of claim 7, wherein m=2, q=2 and said irreducible polynomial is z 2 +z+ξ, where ξ is the GF4 element (10).

Claim 21

The multiplier of claim 11, wherein m=2, q=2 and said irreducible polynomial is z 2 +z+ξ, where ξ is the GF4 element (10).