Circuitry and methods for implementing Galois-field reduction

Patent metadata

Field	Value
Publication number	US-9619207-B1
Application number	US-201414524526-A
Country	US
Kind code	B1
Filing date	Oct 27, 2014
Priority date	Oct 27, 2014
Publication date	Apr 11, 2017
Grant date	Apr 11, 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 expansion bit position. Gates select ones of said the plurality of memories corresponding to ones of the respective expansion bit positions that contain ‘1’, and an exclusive-OR gate combines outputs of the gates that select. A specialized processing block includes a multiplier stage, and an input stage upstream of the multiplier stage, with such Galois-field reduction circuitry in the input stage with its output selectably connectable to the multiplier stage and selectably connectable to an output of the specialized processing block. A programmable integrated circuit device includes a plurality of such specialized processing blocks, and additional multiplier and additional exclusive OR gates for concatenating a plurality of specialized processing blocks.

First claim

What is claimed is:

1. Galois-field reduction circuitry for reducing a Galois-field expansion value using an irreducible polynomial, wherein reducing said Galois-field expansion value yields a Galois-field reduction value having a reduced-field width, the Galois-field reduction circuitry comprising:
a plurality of memories, each for storing a respective value derived from the irreducible polynomial and a respective expansion bit position, wherein each memory in said plurality of memories has a memory width;
gates that select ones of said plurality of memories corresponding to ones of said respective expansion bit positions that contain ‘1’;
an exclusive-OR gate for combining outputs of said gates that select; and
cascade circuitry for connection of said Galois-field reduction circuitry to at least one other instance of said Galois-field reduction circuitry; whereby:
when said reduced-field width exceeds said memory width, said cascade circuitry is used to connect said Galois-field reduction circuitry to said at least on other instance of said Galois-field reduction circuitry.

2. The Galois-field reduction circuitry of claim 1 wherein:
each memory in said plurality of memories holds a first number of bits;
said plurality of memories includes a second number of memories; and
said second number is at least equal to said first number.

3. A method of operating Galois-field reduction circuitry to reduce a Galois-field expansion value using an irreducible polynomial to a Galois-field reduction value having a reduced-field width, where the Galois-field reduction circuitry includes cascade circuitry for connection of a plurality of Galois-field reduction circuits, wherein first and second Galois-field reduction circuits of said plurality of Galois-field reduction circuits each comprise: a plurality of memories each having a memory width, gates that select ones of said plurality of memories, and an exclusive-OR gate for combining outputs of said gates that select; said method comprising:
determining whether said reduced-field width exceeds said memory width;
in response to determining that said reduced-field width exceeds said memory width, using said cascade circuitry to couple said first and second Galois-field reduction circuits;
for each respective expansion bit position in said Galois-field expansion, deriving a respective value from said respective expansion bit position and said irreducible polynomial;
storing each said respective value in a respective one of said plurality of memories of said first and second Galois-field reduction circuits;
using ones of said gates corresponding to ones of said respective expansion bit positions that contain ‘1’, selecting corresponding ones of said plurality of memories in said first and second Galois-field reduction circuits; and
combining said respective values stored in said respective ones of said plurality of memories in said first and second Galois-field reduction circuits.

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

5. The method of claim 4 further comprising performing a further exclusive OR operation between results of said exclusive OR operation and base bit positions of said Galois-field expansion value.

6. The method of claim 3 further comprising performing a further combination between results of said combining and base bit positions of said Galois-field expansion value.

7. The method of claim 3 wherein said deriving a respective value from said respective expansion bit position and said irreducible polynomial comprises performing an exclusive OR operation between said respective expansion bit position and said irreducible polynomial.

8. The method of claim 3 wherein said selecting comprises using said expansion bits to control said ones of said gates.

9. A specialized processing block for a programmable integrated circuit device, said specialized processing block comprising:
a multiplier stage;
an input stage upstream of said multiplier stage, said input stage including register file circuitry, said register file circuitry comprising:
a plurality of memories;
gates that select ones of said plurality of memories;
an OR gate for combining outputs of said gates that select;
an exclusive OR gate for combining outputs of said gates that select; and
a register file output that selects between an output of said OR gate and an output of said exclusive OR gate, and is selectably connectable to said multiplier stage and selectably connectable to an output of said specialized processing block.

10. The specialized processing block of claim 9 wherein:
said gates that select are selectably alternatively controlled by a read-address signal that selects one of said memories for output through said OR gate, or a Galois-field expansion-bit signal that selects one of said memories for combination by said exclusive OR gate with a Galois-field base-bit signal.

11. The specialized processing block of claim 10 further comprising a read-address decoder that converts said read-address signal from a binary format to a one-hot format that activates one of said gates that select.

12. The specialized processing block of claim 10 wherein:
each memory in said plurality of memories has a width of a number of bits; and
said plurality of memories comprises a number of memories at least equal to said number of bits.

13. The specialized processing block of claim 9 , further comprising:
a cascade output to another instance of said specialized processing block; and
a multiplexer for selectably connecting said register file output to said cascade output.

14. The specialized processing block of claim 9 , further comprising:
a cascade input from another instance of said specialized processing block; and
a control gate for selectably connecting said cascade input to said exclusive OR gate.

15. A programmable integrated circuit device comprising:
a plurality of specialized processing blocks, each of said specialized processing blocks comprising:
a multiplier stage,
an input stage upstream of said multiplier stage, said input stage including register file circuitry, said register file circuitry comprising,
a plurality of memories, each memory in said plurality of memories having a width of a number of bits, and said plurality of memories comprising a number of memories at least equal to said number of bits,
gates that select ones of said plurality of memories,
an OR gate for combining outputs of said gates that select,
an exclusive OR gate for combining outputs of said gates that select, and
a register file output that selects between an output of said OR gate and an output of said exclusive OR gate, and is selectably connectable to said multiplier stage and selectably connectable to an output of said specialized processing block;
an additional multiplier; and
additional exclusive OR gates; wherein:
inputs of said additional exclusive OR gates are selectably connectable to ranges of an output of said additional multiplier, each of said ranges having a bit width equal to said number of bits, and are selectably connectable to register file outputs of said plurality of specialized processing blocks.

16. The programmable integrated circuit device of claim 15 wherein:
said gates that select are selectably alternatively controlled by a read-address signal that selects one of said memories for output through said OR gate, or a Galois-field expansion-bit signal that selects one of said memories for combination by said exclusive OR gate with a Galois-field base-bit signal.

Assignees

• Altera Corp

Inventors

• Langhammer Martin

Classifications

• G06F7/724 Primary

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