Circuitry and methods for implementing Galois-field reduction
View Patent ↗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.
1. A method of performing a Galois-field multiplication operation on two m-bit numbers using an irreducible polynomial, on a programmable integrated circuit device having a plurality of specialized processing blocks, each of said specialized processing blocks comprising a multiplier stage including an adder having carry circuitry and AND-gate circuitry for selectably deactivating said carry circuitry, an input stage upstream of said multiplier stage, said input stage comprising, a plurality of memories addressable by inputs of said specialized processing block, and exclusive-OR circuitry for combining output of said plurality of memories with other inputs of said specialized processing block, and a cascade connection from an output of said multiplier stage to another of said specialized processing blocks; said method comprising:
for each potential expansion bit position in a Galois-field expansion value, deriving a respective value from said potential expansion bit position and said irreducible polynomial;
for different possible combinations of bits in said expansion bit positions, combining ones of said respective values to yield respective combined values;
storing each said respective combined value in a respective one of said plurality of memories;
using said multiplier stage in one of said specialized processing blocks to multiply said two m-bit numbers to derive said Galois-field expansion value; and
combining ones of respective combined values with in-field bits of said Galois-field expansion value in circuitry of said one of said specialized processing blocks and another of said specialized processing blocks.
2. The method of claim 1 , further comprising:
actuating said AND-gate circuitry to deactivate said carry circuitry.
3. The method of claim 1 , wherein said combining comprises:
combining at least one of said respective combined values with in-field bits of said Galois-field expansion value in circuitry of said one of said specialized processing blocks to provide an intermediate value.
4. The method of claim 3 , wherein said combining further comprises:
inputting said intermediate value to said another of said specialized processing blocks via said cascade connection.
5. The method of claim 4 , wherein said combining further comprises:
combining at least one of said respective combined values with in-field bits of said intermediate value in circuitry of said another of said specialized processing blocks.
6. The method of claim 3 wherein said combining at least one of said respective combined values with in-field bits of said intermediate expansion value in circuitry of said another of said specialized processing blocks comprises:
combining at least two of said respective combined values with each other in exclusive-OR circuitry of said another of said specialized processing blocks to provide a derived value.
7. The method of claim 6 , wherein said combining at least one of said respective combined values with in-field bits of said intermediate expansion value in circuitry of said another of said specialized processing blocks further comprises:
combining said derived value with in-field bits of said intermediate value in exclusive-OR circuitry of said another of said specialized processing blocks.
8. A method of configuring a programmable integrated circuit device to perform a Galois-field multiplication operation on two m-bit numbers using an irreducible polynomial, said programmable integrated circuit device having a plurality of specialized processing blocks, each of said specialized processing blocks comprising a multiplier stage including an adder having carry circuitry and AND-gate circuitry for selectably deactivating said carry circuitry, an input stage upstream of said multiplier stage, said input stage comprising, a plurality of memories addressable by inputs of said specialized processing block, and exclusive-OR circuitry for combining output of said plurality of memories with other inputs of said specialized processing block, and a cascade connection from an output of said multiplier stage to another of said specialized processing blocks; said method comprising:
for each potential expansion bit position in a Galois-field expansion value, deriving a respective value from said potential expansion bit position and said irreducible polynomial;
for different possible combinations of bits in said expansion bit positions, combining ones of said respective values to yield respective combined values;
storing each said respective combined value in a respective one of said plurality of memories;
configuring said multiplier stage in one of said specialized processing blocks to multiply said two m-bit numbers to derive said Galois-field expansion value; and
configuring exclusive-OR circuitry of said one of said specialized processing blocks and another of said specialized processing blocks to combine ones of respective combined values with in-field bits of said Galois-field expansion value.
9. The method of claim 8 , further comprising:
configuring said AND-gate circuitry to deactivate said carry circuitry.
10. The method of claim 8 , wherein said configuring exclusive-OR circuitry comprises:
configuring exclusive-OR circuitry of said one of said specialized processing blocks to combine at least one of said respective combined values with in-field bits of said Galois-field expansion value to provide an intermediate value.
11. The method of claim 10 , wherein said configuring exclusive OR circuitry comprises:
configuring said cascade connection to input said intermediate value to said another of said specialized processing blocks.
12. The method of claim 11 , wherein said configuring exclusive OR circuitry comprises:
configuring exclusive-OR circuitry of said another of said specialized processing blocks to combine at least one of said respective combined values with in-field bits of said intermediate value.
13. The method of claim 10 , wherein said configuring exclusive-OR circuitry of said another of said specialized processing blocks comprises:
configuring exclusive-OR circuitry of said another of said specialized processing blocks to combine at least two of said respective combined values with each other to provide a derived value.
14. The method of claim 13 , wherein said configuring exclusive OR circuitry of said another of said specialized processing blocks further comprises:
configuring exclusive-OR circuitry of said another of said specialized processing blocks to combine said derived value with in-field bits of said intermediate value.
15. A non-transitory machine-readable storage medium encoded with instructions for performing a method of configuring a programmable integrated circuit device to perform a Galois-field multiplication operation on two m-bit numbers using an irreducible polynomial, said programmable integrated circuit device having a plurality of specialized processing blocks, each of said specialized processing blocks comprising a multiplier stage including an adder having carry circuitry and AND-gate circuitry for selectably deactivating said carry circuitry, an input stage upstream of said multiplier stage, said input stage comprising, a plurality of memories addressable by inputs of said specialized processing block, and exclusive-OR circuitry for combining output of said plurality of memories with other inputs of said specialized processing block, and a cascade connection from an output of said multiplier stage to another of said specialized processing blocks; said instructions comprising:
for each potential expansion bit position in a Galois-field expansion value, deriving a respective value from said potential expansion bit position and said irreducible polynomial;
for different possible combinations of bits in said expansion bit positions, combining ones of said respective values to yield respective combined values;
instructions to store, in a respective one of said plurality of memories, each of respective combined values derived from combinations of potential expansion bit positions in a Galois-field expansion value and said irreducible polynomial;
instructions to configure said multiplier stage in one of said specialized processing blocks to multiply said two m-bit numbers to derive said Galois-field expansion value; and
instructions to configure exclusive-OR circuitry of said one of said specialized processing blocks and another of said specialized processing blocks to combine ones of respective combined values with in-field bits of said Galois-field expansion value.
16. The non-transitory machine-readable storage medium of claim 15 , wherein said encoded instructions further comprise:
instructions to configure said AND-gate circuitry to deactivate said carry circuitry.
17. The non-transitory machine-readable storage medium of claim 15 , wherein said encoded instructions to configure exclusive-OR circuitry comprise:
instructions to configure exclusive-OR circuitry of said one of said specialized processing blocks to combine at least one of said respective combined values with in-field bits of said Galois-field expansion value to provide an intermediate value.
18. The non-transitory machine-readable storage medium of claim 17 , wherein said encoded instructions to configure exclusive OR circuitry further comprise:
instructions to configure said cascade connection to input said intermediate value to said another of said specialized processing blocks.
19. The non-transitory machine-readable storage medium of claim 18 , wherein said encoded instructions to configure exclusive OR circuitry further comprise:
instructions to configure exclusive-OR circuitry of said another of said specialized processing blocks to combine at least one of said respective combined values with in-field bits of said intermediate value.
20. The non-transitory machine-readable storage medium of claim 17 , wherein said encoded instructions to configure exclusive-OR circuitry of said another of said specialized processing blocks comprise:
instructions to configure exclusive-OR circuitry of said another of said specialized processing blocks to combine at least two of said respective combined values with each other to provide a derived value; and
instructions to configure exclusive-OR circuitry of said another of said specialized processing blocks to combine said derived value with in-field bits of said intermediate value.