Condensed Galois field computing system

• US 7,512,647 B2
• Filed: 11/22/2004
• Issued: 03/31/2009
• Est. Priority Date: 11/22/2004
• Status: Expired due to Fees

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Wilson, James, Stein, Yosef, Kablotsky, Joshua
• Primary Examiner(s): Ngo; Chuong D
• Application Number:
  US10/994,699
• Publication Number:
  US 20060123325A1
• Time in Patent Office: 1,590 Days
• Field of Search: 708491-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/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

A condensed Galois field computing system including a multiplier circuit for multiplying first and second polynomials with coefficients over a Galois field to obtain their product; and a Galois field linear transformer circuit for applying an irreducible polynomial of power n to the product including a partial result generator responsive to terms of power n and greater in the product for providing a folded partial result and a Galois field adder for condensing the folded partial result and the terms less than power n in the product to obtain Galois field transformer of power n of the product.

Claims

1. A condensed Galois field computing system comprising:

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

a Galois field transformer circuit for applying an irreducible polynomial of power n to said product including a partial result generator responsive to terms of power n and greater in said product for providing a folded partial result and a Galois field adder for combining said folded partial result and the terms less than power n in the product to obtain Galois field transform of power n of said product, said partial result generator including a look-up table that includes the folded partial results for the terms with the power of n or greater, the computing system used for error correction and/or encryption.

2. The condensed Galois field computing system of claim 1 in which said look-up table includes an address generator for said selecting one of the folded partial results tables.

3. The condensed Galois field computing system of claim 2 in which said address generator provides statically independent address access.

4. The condensed Galois field computing system of claim 2 in which said address generator includes an OR circuit for combining said terms of n and greater and said value of base address to generate the look-up table address.

5. The condensed Galois field computing system of claim 1 in which said Galois field adder includes a three input adder.

6. The condensed Galois field computing system of claim 5 in which said third input to said three input adder is a zero and said Galois field computing system operates as a Galois field multiplier.

7. The condensed Galois field computing system of claim 5 in which said third input to said three input adder is the Galois field adder output fed back and said Galois field computing system operates as a multiplier-accumulator.

8. The condensed Galois field computing system of claim 5 in which the Galois field adder output is fed back to said multiplier circuit with one of said first and second polynomials and the other of said polynomials is the third input to said Galois field adder and said Galois field computing system operates as a multiplier-adder.

9. The condensed Galois field computing system of claim 1 in which the Galois field adder includes an exclusive OR circuit.

10. The condensed Galois field computing system of claim 1 in which said look-up table includes at least one folded partial results table.

11. A condensed Galois field multiplier system comprising:

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

a Galois field transformer circuit for applying an irreducible polynomial of power n to said product including a partial result generator responsive to terms of power n and greater in said product for providing a folded partial result and a Galois field adder for combining said folded partial results and the terms less than power n in the product to perform a Galois field multiply operation, said partial result generator including a look-up table that includes the folded partial results for the terms with the power of n or greater, the multiplier system used for error correction and/or encryption.

12. A condensed Galois field multiply-accumulate system comprising:

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

a Galois field transformer circuit for applying an irreducible polynomial of power n to said product including a partial result generator responsive to terms of power n and greater in said product for providing a folded partial result and a Galois field adder for combining said folded partial results, the terms less than power n in the product and the output of the Galois field adder fed back to perform a Galois field multiply-accumulate operation, said partial result generator including a look-up table that includes the folded partial results for the terms with the power of n or greater, the multiply-accumulate system used for error correction and/or encryption.

13. A condensed Galois field multiplier-adder system comprising:

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

a Galois field transformer circuit for applying an irreducible polynomial of power n to said product including a partial result generator responsive to terms of power n and greater in said product for providing a folded partial result and a Galois field adder whose output is fed back to said multiplier circuit with one of said first and second polynomials and the other of said polynomials is a third input to said Galois field adder along with said folded partial results and the terms less than power n in the product to perform a Galois field multiply-add operation, said partial result generator including a look-up table that includes the folded partial results for the terms with the power of n or greater, the multiplier-adder system used for error correction and/or encryption.