Combinatorial polynomial multiplier for galois field 256 arithmetic
AssigneeTexas Instruments Incorporated
InventorTod D. Wolf
Life of this patent
Estimating the term…
Abstract
A combinatorial polynomial multiplier for Galois Field 256 arithmetic utilizes fewer components than an iterative Galois Field 256 arithmetic multiplier and operates 8 times faster. The combinatorial multiplier employs AND and XOR functions and operates in a single clock cycle. It can reduce the number of transistors required for the Galois Field 256 arithmetic multiplier for a Reed-Solomon decoder by almost 90%.
Claims6
A combinatorial polynomial multiplier for Galois Field 2n (n>4) arithmetic comprising:
- an AND block comprising a plurality of 2-input AND gates, said plurality having a number of gates equal to the product of the number n of bits in a multiplicand multiplied by the number n of bits in a multiplier, each gate having as inputs a different pair of one bit of said multiplicand and one bit of said multiplier and generating an associated different minterm product as an output;
- a plurality of n XOR blocks for respectively generating the n bits of a Galois Field 2n output, each XOR block comprising a plurality of 2-input XOR gates connected in a binary XOR tree derived from a primitive polynomial for said Galois Field 2n arithmetic, inputs of said XOR block being coupled to the outputs of said AND block to receive those of the minterms associated with said primitive polynomial for generating a corresponding different bit of said Galois Field 2n output without feedback.
A method of multiplying a Galois Field 2n arithmetic n-bit multiplicand by a Galois Field 2n arithmetic n-bit multiplier to generate an n-bit Galois Field 2n arithmetic result, where n>4, comprising the steps of:
- ANDing a different pair of each bit of said multiplicand and each bit in said multiplier to generate a plurality of associated different n×n minterms;
- XORing said minterms in a plurality of n XOR trees derived from a primitive polynomial for said Galois Field 2n arithmetic for respectively generating the bits in said result, each said tree XORing those of the minterms associated with said primitive polynomial for generating a corresponding different bit of said Galois Field result without feedback.
Dependencies are inferred from the claim text.