Galois field multiply/ multiply-add/multiply accumulate

• US 20030110196A1
• Filed: 08/26/2002
• Published: 06/12/2003
• Est. Priority Date: 11/30/2001
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Stein, Yosef, Primo, Haim, Sapir, Yaniv
• Granted Patent: US 7,082,452 B2
• Time in Patent Office: Days
• 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 multiply/multiply-add/multiply-accumulate 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; a storage circuit for supplying to the Galois field linear transformer circuit a set of coefficient for predicting the modulo remainder for a predetermined irreducible polynomial; and a Galois field adder circuit for adding the product of the multiplier circuit with a third polynomial with coefficients over a Galois field for performing the multiplication and add operations in a single cycle.

Claims

1. A Galois field multiply/multiply-add/multiply-accumulate 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 responsive to said multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial;

a storage circuit for supplying to said Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for a predetermined irreducible polynomial; and

a Galois field adder circuit for adding said product of said multiplier circuit with a third polynomial with coefficients over a Galois field for performing the multiply and add operations in a single cycle.

2. The Galois field multiply/multiply-add/multiply-accumulate system of claim 1 in which said third polynomial is the additive identity polynomial and the add operation is nulled.

3. The Galois field multiply/multiply-add/multiply-accumulate system of claim 1 in which said multiplier circuit product is recursively fed back as the third polynomial and said adder circuit performs a multiply-accumulate operation.

4. The Galois field multiply/multiply-add/multiply-accumulate system of claim 1 in which said multiplication product is delivered to a first output register and the multiply-add/multiply-accumulate result is delivered to a second output register

5. The Galois field multiply/multiply-add/multiply-accumulate system of claim 1 in which said Galois field adder circuit includes a plurality of adder cells associated with said Galois field linear transformer circuit for combining said third polynomial with the product of the first and second in one cycle.

6. The Galois field multiply/multiply-add/multiply-accumulate system of claim 5 in which said Galois field adder circuit includes a gate associated with each of said adder cells for inhibiting the adding of said third polynomial to the product of said first and second polynomials to null the add operation.