Multiplier circuit design for a programmable logic device

A multiplier circuit in a programmable logic device, said programmable logic device including a plurality of programmable logic elements, said multiplier circuit having as inputs an M bit multiplicand and an N bit multiplier, said multiplier circuit for generating a product, said multiplier circuit comprising:

• a plurality of partial product generator circuits, each of said plurality of partial product generator circuits having as input said multiplicand and a plurality of least significant bits of said multiplier, each of said plurality of partial product generator circuits having as output a partial product;
• a plurality of compression circuits, said compression circuits having as output a first addend and a second addend, each of said plurality of compression circuits coupled to, and receiving outputs from at least two of said partial product generator circuits, each of said plurality of compression circuits having as output a bit of said first addend and a bit of said second addend;
• an adder circuit coupled to said plurality of compression circuits and having as input said first addend and said second addend and having as output said product;
• and wherein at least one of said plurality of said partial product generator circuits includes a Booth recoder circuit coupled to a partial product output circuit, said Booth recoder circuit coupled to said partial product output circuit for providing control signals to indicate a multiple of said multiplicand and a sign of said multiplicand, said Booth recoder circuit and said partial product output circuit being configured within a single programmable logic element.

A multiplier circuit in a programmable logic device, said programmable logic device including a plurality of programmable logic elements, said multiplier circuit having as inputs an M bit multiplicand and an N bit multiplier, said multiplier circuit for generating a product, said multiplier circuit comprising:

• a plurality of partial product generator circuits, each of said plurality of partial product generator circuits having as input said multiplicand and a plurality of least significant bits of said multiplier, each of said plurality of partial product generator circuits having as output a partial product;
• a plurality of compression circuits, said compression circuits having as output a first addend and a second addend, each of said plurality of compression circuits coupled to, and receiving outputs from, at least two of said partial product generator circuits, each of said plurality of compression circuits having as output a bit of said first addend and a bit of said second addend:
• an adder circuit coupled to said plurality of compression circuits and having as input said first addend and said second addend and having as output said product;
• and wherein at least one of said plurality of said partial product generator circuits includes a Booth recoder circuit coupled to a partial product output circuit, said Booth recoder circuit coupled to said partial product output circuit for providing control signals to indicate a multiple of said multiplicand and a sign of said multiplicand, said Booth recoder circuit and said partial product output circuit being configured within a single programmable logic element, wherein said Booth recoder circuit is coupled to and receiving a bit MRi-1, a bit MRi of said multiplier and wherein a first control signal of said control signals is generated by an exclusive OR of said bit MRi-1 and said bit MRi.

A method of generating a bit of a first addend and a bit of a second addend, said first addend plus said second addend being a product of an N bit multiplicand and an M bit multiplier in a programmable logic device, said programmable logic device including a plurality of programmable logic elements, said method comprising the steps of:

• generating a first set of three partial product bits from said multiplicand and a first plurality of least significant bits of said multiplier, a second set of three partial product bits from said multiplicand and a second plurality of next least significant bits of said multiplier, and a third set of three partial product bits from said multiplicand and a third plurality of most significant bits of said multiplier from a Booth recoder circuit, each of said sets of three partial product bits representing three equally weighted bits of three partial products, each bit of each partial product being generated in a different partial product generator circuit and in a different programmable logic element;
• adding said first set of three partial product bits to form a first value bit;
• adding said second set of three partial product bits to form a second value bit and a third value bit;
• adding said third set of three partial product bits to form a fourth value bit;
• adding said first value bit and said second value bit to form a fifth value bit which is the carry output of such addition;
• generating a fourth partial product bit from said multiplicand and a fourth portion of said multiplier;
• adding said fifth value bit, said third value bit, said fourth value bit and said fourth partial product bit, to generate a carry bit, said carry bit being said bit of said first addend.

An eight bit by eight bit multiplier circuit design for a programmable logic device, said multiplier including:

• a first Booth recoding circuit for generating three partial products from a multiplier and a multiplicand, a first part of a sum, and a first part of a carry;
• a first Wallace Tree circuit coupled to the first Booth recoding circuit and receiving the three partial products for generating a second part of the sum and a second part of the carry from the three partial products;
• and
• a carry propagate adder coupled to said Booth recoding circuit and receiving said first part of the sum and said first part of the carry, said carry propagate adder further coupled to said Wallace tree compression circuit and receiving the second part of the sum and the carry for generating a product from the first and second parts of the sum and the first and second parts of the carry,
• wherein the longest signal path through the multiplier circuit design includes a circuit that generates bit seven of the carry and excludes circuits that generate lower bits of the carry.

A multiplier circuit in a programmable logic device, said programmable logic device including a plurality of programmable logic elements, said multiplier circuit having as inputs an M bit multiplicand and an N bit multiplier, said multiplier circuit for generating a product, said multiplier circuit comprising:

• a plurality of partial product generator circuits, each of said plurality of partial product generator circuits having as input said multiplicand and a portion of said multiplier, each of said plurality of partial product generator circuits having as output a partial product;
• a plurality of compression circuits, said compression circuits having as output a first addend and a second addend, each of said plurality of compression circuits coupled to, and receiving an input from, at least two of said partial product generator circuits, each of said plurality of compression circuits having as output a part of said first addend and a part of said second added, wherein said second addend includes a plurality of correction bits if a partial product is negative;
• at least one of said plurality of compression circuits including a three to two Wallace Tree, said Wallace Tree comprising a first set of adders coupled to and receiving the outputs of a first partial product generator circuit, a second partial product generator circuit, and a third partial product generator circuit, said first set of adders providing a first value and a second value, said Wallace Tree further comprising a second set of adders coupled to and receiving said first value and the outputs of a fourth partial product generator circuit and providing said part of said first addend and said part of said second addend;
• and
• an adder circuit coupled to said plurality of compression circuits and having as input said first addend and said second addend and having as output said product, wherein at least one of said plurality of partial product generator circuits includes a Booth recoder circuit coupled to a partial product output circuit, said Booth recoder circuit coupled to said partial product output circuit for providing control signals to indicate a multiple of said multiplicand and a sign of said multiplicand, said Booth recoder circuit and said partial product output circuit being configured within a single programmable logic element.

A multiplier circuit in a programmable logic device, said programmable logic device including a plurality of programmable logic elements, said multiplier circuit having as inputs an M bit multiplicand and an N bit multiplier, said multiplier circuit for generating a product, said multiplier circuit comprising:

• a plurality of partial product generator circuits, each of said plurality of partial product generator circuits having as input said multiplicand and a portion of said multiplier, each of said plurality of partial product generator circuits having as output a partial product;
• a plurality of compression circuits, said compression circuits having as output a first addend and a second addend, each of said plurality of compression circuits coupled to, and receiving an input from, at least two of said partial product generator circuits, each of said plurality of compression circuits having as output a part of said first addend and a part of said second added, wherein said second addend includes a plurality of correction bits if a partial product is negative;
• at least one of said plurality of compression circuits including a five to three Wallace Tree comprising a first set of adders coupled to and receiving the outputs of a first partial product generator circuit, a second partial product generator circuit, a third partial product generator circuit, and a fourth partial product generator circuit, said first set of adders for generating said part of said first addend and said part of said second addend;
• and
• an adder circuit coupled to said plurality of compression circuits and having as input said first addend and said second addend and having as output said product, wherein at least one of said plurality of partial product generator circuits includes a Booth recoder circuit coupled to a partial product output circuit, said Booth recoder circuit coupled to said partial product output circuit for providing control signals to indicate a multiple of said multiplicand and a sign of said multiplicand, said Booth recoder circuit and said partial product output circuit being configured within a single programmable logic element.

A multiplier circuit in a programmable logic device, said programmable logic device including a plurality of programmable logic elements, said multiplier circuit having as inputs an M bit multiplicand and an N bit multiplier, said multiplier circuit for generating a product, said multiplier circuit comprising:

• a plurality of partial product generator circuits, each of said plurality of partial product generator circuits having as input said multiplicand and a portion of said multiplier, each of said plurality of partial product generator circuits having as output a partial product;
• a plurality of compression circuits, said compression circuits having as output a first addend and a second addend, each of said plurality of compression circuits coupled to, and receiving an input from, at least two of said partial product generator circuits, each of said plurality of compression circuits having as output a part of said first addend and a part of said second added;
• and
• an adder circuit coupled to said plurality of compression circuits and having as input said first addend and said second addend and having as output said product, wherein at least one of said plurality of partial product generator circuits includes a Booth recoder circuit coupled to a partial product output circuit, said Booth recoder circuit coupled to said partial product output circuit for providing control signals to indicate a multiple of said multiplicand and a sign of said multiplicand, wherein said first addend is a sum and said second addend is a carry and wherein bit two of said carry is generated by performing an AND of a bit three of said multiplier and a control signal generated from bits one through three of said multiplier, said control signal is a zero when said bit one, said bit two and said bit three are all one and when said bit one, said bit two and said bit three are all zero, and wherein otherwise said control signal is one, said Booth recoder circuit and said partial product output circuit being configured within a single programmable logic element.