Booth multiplier with enhanced reduction tree circuitry

A system for operation in association with a digital signal processor for performing Booth multiplication in a digital signal processor, comprising:

• processing circuitry for determining a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;
• a multiplier block for performing radix-4 Booth recoding on B to generate a first predetermined number, n, of multiplication factors, said “n” multiplication factors approximating one half of the number of said second plurality of bits;
• a plurality of multiplier units associated with said multiplier block for generating “n” partial products using said “n” multiplication factors as multipliers of A;
• Booth encoding circuitry associated with said plurality of multiplier units for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising a plurality of multiplier bits, said multiplier bits being associated in said multiplier tree for generating a plurality of multiplication factors;
• inverter circuitry associated with said Booth encoding circuitry for the event of a negative multiplication factor, and in such event forming a two's complement of A by inverting said first plurality of bits of A and associating a sticky “1” to complete the two's complementation;
• and
• reduction circuitry associated with said multiplier units for reducing said multiplication factors in multiple stages of reduction to a set of sum and carry components of a pre-determined length;
• and
• inverter circuitry for determining the negative product of A and B by setting −B as the multiplier by determining the additive inverse of said multiplication factors.

A digital signal processor for operation in support of a personal electronics device, said digital signal process comprising means for performing Booth multiplication in a digital signal processor, comprising:

• means for determining a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;
• means for performing radix-4 Booth recoding on B to generate a first predetermined number, n, of multiplication factors, said “n” multiplication factors approximating one half of the number of said second plurality of bits;
• means for generating “n” partial products using said “n” multiplication factors as multipliers of A;
• means for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising a plurality of multiplier bits, said multiplier bits being associated in said multiplier tree for generating a plurality of multiplication factors;
• means for in the event of a negative multiplication factor, forming a two's complement of A by inverting said first plurality of bits of A and associating a sticky “1” to complete the two's complementation;
• and
• means for reducing said multiplication factors in multiple stages of reduction to a set of sum and carry components of a pre-determined length;
• and
• means for determining the negative product of A and B by setting −B as the multiplier by determining the additive inverse of said multiplication factors.

A computer usable medium having computer readable program code means embodied therein for performing Booth multiplication in a digital signal processor, comprising:

• computer readable program code means for determining a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;
• computer readable program code means for performing radix-4 Booth recoding on B to generate a first predetermined number, n, of multiplication factors, said “n” multiplication factors approximating one half of the number of said second plurality of bits;
• computer readable program code means for generating “n” partial products using said “n” multiplication factors as multipliers of A;
• computer readable program code means for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising a plurality of multiplier bits, said multiplier bits being associated in said multiplier tree for generating a plurality of multiplication factors;
• computer readable program code means for in the event of a negative multiplication factor, forming a two's complement of A by inverting said first plurality of bits of A and associating a sticky “1” to complete the two's complementation;
• and
• computer readable program code means for reducing said multiplication factors in multiple stages of reduction to a set of sum and carry components of a pre-determined length;
• and
• computer readable program code means for determining the negative product of A and B by setting −B as the multiplier by determining the additive inverse of said multiplication factors.