Galois field multiplier system

• US 6,766,345 B2
• Filed: 01/30/2002
• Issued: 07/20/2004
• Est. Priority Date: 11/30/2001
• Status: Expired due to Fees

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Kablotsky, Joshua A., Stein, Yosef, Primo, Haim
• Primary Examiner(s): NGO, CHUONG D
• Application Number:
  US10/060,699
• Publication Number:
  US 20030105791A1
• Time in Patent Office: 902 Days
• Field of Search: 708/491, 708/492
• 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
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

A Galois field multiplier system includes a multiplier circuit for multiplying two polynomials with coefficients over a Galois field to obtain their product; a Galois field linear transformer circuit responsive to the multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial; and a storage circuit for supplying to the Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for predetermined irreducible polynomial.

Claims

1. A Galois field multiplier system comprising:

a multiplier circuit for multiplying two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a plurality of cells and responsive to said multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial; and

a storage circuit configured to independently program each of said cells for supplying to said Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for a predetermined irreducible polynomial.

2. The Galois field multiplier system of claim 1 in which said Galois field linear transformer circuit divides said polynomial product by said irreducible polynomial to obtain said modulo remainder.

3. The Galois field multiplier system of claim 1 in which said multiplier circuit includes and AND logic circuit for each term of said polynomial product to effect a Galois multiplier.

4. The Galois field multiplier system of claim 1 in which said multiplier circuit includes an exclusive OR logic circuit for each pair of terms in said polynomial product to effect a Galois summation.

5. The Galois field multiplier system of claim 1 in which said Galois field linear transformer circuit includes a matrix responsive to a number of input bits in one or more bit streams and having a plurality of outputs for providing the Galois field linear transformation of those bits;

said matrix including a plurality of cells, each cell including an exclusive OR logic circuit, an AND logic circuit having an output connected to the exclusive OR logic circuit and an input connected to one of said input bits, said storage circuit providing said set of coefficients for setting the matrix to obtain a multicycle Galois field linear transformation of the inputs in a single cycle.

6. The Galois field multiplier system of claim 1 in which said Galois field linear transformer includes a plurality of Galois field transformer units and said storage circuit supplies said coefficients in parallel to said Galois field transformer units.

7. The Galois field multiplier system of claim 1 in which said Galois field linear transformer includes a plurality of Galois field transformer units and said storage circuit includes a plurality of storage units one associated with each of said Galois field linear transformer units.