Circuitry and methods for implementing Galois-field reduction

Patent metadata

Field	Value
Publication number	US-9740456-B2
Application number	US-201514694396-A
Country	US
Kind code	B2
Filing date	Apr 23, 2015
Priority date	Apr 23, 2015
Publication date	Aug 22, 2017
Grant date	Aug 22, 2017

Abstract

Galois-field reduction circuitry for reducing a Galois-field expansion value, using an irreducible polynomial, includes a plurality of memories, each for storing a respective value derived from the irreducible polynomial and a respective combination of expansion bit values, wherein expansion bits of the expansion value address the plurality of memories to output one or more of the respective values. The Galois-field reduction circuitry also includes exclusive-OR circuitry for combining output of the plurality of memories with in-field bits of said expansion value. There are also a method of operating such Galois-field reduction circuitry to reduce a Galois-field expansion value, a programmable integrated circuit device incorporating the circuitry, a method of performing a Galois-field multiplication operation on such a programmable integrated circuit device, and a method of configuring a programmable integrated circuit device to perform such a Galois-field multiplication operation.

First claim

What is claimed is:

1. Galois-field reduction circuitry for reducing a Galois-field expansion value using an irreducible polynomial, the Galois-field reduction circuitry comprising:
a plurality of memories, each for storing a predetermined value, wherein precalculated in-field values corresponding to predefined Galois-field expansion values having a single ‘1’ in an out-of-field bit are determined based on said irreducible polynomial and said predefined Galois-field expansion values, wherein each of the predetermined values is determined based on one or more of said precalculated in-field values, and wherein out-of-field bits of said expansion value address said plurality of memories to output one or more of said predetermined values; and
exclusive-OR circuitry for combining output of said plurality of memories with in-field bits of said expansion value.

2. The Galois-field reduction circuitry of claim 1 wherein:
different ranges of said out-of-field bits address different ones of said plurality of memories to output a plurality of said predetermined values; and
said exclusive-OR circuitry comprises:
first exclusive-OR circuitry for combining said plurality of said predetermined values with each other, and
second exclusive-OR circuitry for combining output of said first exclusive-OR circuitry with said in-field bits of said expansion value.

3. A method of operating Galois-field reduction circuitry to reduce a Galois-field expansion value using an irreducible polynomial, where the Galois-field reduction circuitry includes a plurality of memories, and exclusive-OR circuitry for combining output of said plurality of memories with in-field bits of said expansion value; said method comprising:
for each predefined Galois-field expansion value having a single ‘1’ in an out-of-field bit, deriving a precalculated in-field value from said predefined Galois-field expansion value and said irreducible polynomial;
for different possible combinations of out-of-field bits, combining ones of said precalculated in-field values to yield combined values;
storing each said combined value in one of said plurality of memories;
using values of said out-of-field bits to address said plurality of memories and select corresponding one or more of said combined values; and
operating on said select corresponding one or more of said combined values and said in-field bits to determine a reduced Galois-field value.

4. The method of claim 3 wherein said combining comprises performing an exclusive OR operation.

5. The method of claim 4 wherein said operating comprises performing a further exclusive OR operation.

6. The method of claim 3 wherein said operating comprises performing an exclusive OR operation.

7. The method of claim 3 wherein said deriving said precalculated in-field value from said predefined Galois-field expansion value and said irreducible polynomial comprises performing an exclusive OR operation between said predefined Galois-field expansion value and said irreducible polynomial.

8. The method of claim 3 wherein said using values of said out-of-field bits to address said plurality of memories and select corresponding one or more of said combined values comprises using different ranges of said out-of-field bits to address different ones of said plurality of memories to select a plurality of said combined values.

9. The method of claim 8 wherein said operating comprises:
using a first exclusive OR operation to further combine said plurality of combined values; and
using a second exclusive OR operation to combine said further combined plurality of combined values with said in-field bits.

10. The method of claim 9 wherein said operating further comprises using a third exclusive OR operation to combine one of said plurality of combined values with said in-field bits prior to said using said first exclusive OR operation and prior to said using said second exclusive OR operation.

Assignees

• Altera Corp

Inventors

• Chu Pohrong Rita

Classifications

• G06F7/724 Primary

  Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10) · CPC title

• G06F7/535 Primary

  Dividing only · CPC title