Linear summation multiplier array implementation for both signed and unsigned multiplication

Abstract

A system and method are disclosed which provide a multiplier comprising a linear summation array that is implemented in a manner that enables both signed and unsigned multiplication to be performed. A preferred embodiment utilizes a modified Baugh-Wooley algorithm to enable an optimum even-and-odd linear summation array for performing both signed and unsigned high speed multiplication. That is, a preferred embodiment enables a linear summation array that is smaller in size and simpler in design than the multiplier arrays typically implemented for signed multiplication in the prior art. The modified Baugh-Wooley algorithm of a preferred embodiment translates a signed operand to an unsigned operand to greatly simplify the sign extension for multiplication, and to enable a relatively small multiplier array that does not include sign extension columns to be utilized for performing signed multiplication. The modified Baugh-Wooley algorithm of a preferred embodiment also enables the multiplier to perform unsigned multiplication.

What is claimed is:  
     
         1 . A multiplier comprising: 
 means for receiving at least two operands, A and B;    means for generating a product of said at least two operands, wherein said generating means is arranged to enable both signed and unsigned multiplication; and    wherein said means for generating implements a modified Baugh-Wooley algorithm for signed multiplication that generates a product of operands A and B as the result of ((S A *S B *2 2N−2 )+(S A *(−1)*2 N−1 *B′)+(S B *(−1)*2 N−1 *A′)+(A′*B′)), wherein N is the number of bits in each operand, S A  is the sign bit for operand A, S B  is the sign bit for operand B, A′ is the bits of operand A excluding its sign bit, and B′ is the bits of operand B excluding its sign bit.    
     
     
         2 . The multiplier of  claim 1  wherein said means for generating is further configured to perform unsigned multiplication by generating a product of said operands A and B as a result of:  
       (( S   A   *S   B *2 2N−2 )+( S   A *2 N−1   *B ′)+( S   B *2 N−1   *A ′)+( A′*B ′)).  
     
     
         3 . The multiplier of  claim 1  wherein said modified Baugh-Wooley algorithm translates a signed operand to an unsigned operand.  
     
     
         4 . The multiplier of  claim 1  wherein said generating means is implemented having a static design.  
     
     
         5 . The multiplier of  claim 1  wherein said multiplier is operable at a frequency of 1 GHz or greater.  
     
     
         6 . The multiplier of  claim 1  wherein said multiplier is operable to perform multiplication when multiplication is enabled for said multiplier, and wherein said multiplier is operable to perform population count for a received operand when population count is enabled for said multiplier.  
     
     
         7 . The multiplier of  claim 1  further comprising: 
 means for identifying whether signed or unsigned multiplication is desired.  
 
     
     
         8 . A system comprising: 
 multiplier for generating a product of at least two operands;    said multiplier comprising a linear summation array for summing partial products of said at least two operands, wherein said linear summation array is arranged to enable both signed and unsigned multiplication;    wherein said linear summation array is implemented to generate a product of operands A and B as a result of ((S A *S B *2 2N−2 )+(S A *(−1)*2 N−1 *B′)+(S B *(−1)*2 N−1 *A′)+(A′*B′)) when performing signed multiplication, wherein N is the number of bits in each operand, S A  is the sign bit for operand A, S B  is the sign bit for operand B, A′ is the bits of operand A excluding its sign bit, and B′ is the bits of operand B excluding its sign bit; and    wherein said linear summation array is implemented to generate a product of operands A and B as a result of ((S A *S B *2 2N−2 )+(S A *2 N−1 *B′)+(S B *2 N−1 *A′)+(A′*B′)) when performing unsigned multiplication, wherein N is the number of bits in each operand, S A  is the most significant bit for operand A, S B  is the most significant bit for operand B, A′ is the bits of operand A excluding its most significant bit, and B′ is the bits of operand B excluding its most significant bit.    
     
     
         9 . The system of  claim 8  further comprising at least one processor.  
     
     
         10 . The system of  claim 8  wherein said linear summation array is implemented as an even-and-odd structure having a static design.  
     
     
         11 . The system of  claim 8  wherein the resulting columns of said linear summation array correspond to the input pitch of the operands input to the multiplier.  
     
     
         12 . The system of  claim 11  wherein two operands having  16  bits each are input to the multiplier, said linear summation array resulting for said two operands having size 16 by 14.  
     
     
         13 . A method of performing multiplication comprising the steps of: 
 receiving at least two operands, A and B, in a multiplier;    identifying whether signed or unsigned multiplication is desired;    if signed multiplication is desired, then computing the product of said at least two operands A and B as a result of    ((S A *S B *2 2N−2 )+(S A *(−1)*2 N−1 *B′)+(S B *(−1)*2 N−1 *A′)+(A′*B′)), wherein N is the number of bits in each operand, S A  is the sign bit for operand A, S B  is the sign bit for operand B, A′ is the bits of operand A excluding its sign bit, and B′ is the bits of operand B excluding its sign bit; and    if unsigned multiplication is desired, then computing the product of said at least two operands A and B as a result of ((S A *S B *2 2N−2 )+(S A *2 N−1 *B′)+(S B *2 N−1 *A′)+(A′*B′)), wherein N is the number of bits in each operand, S A  is the most significant bit for operand A, S B  is the most significant bit for operand B, A′ is the bits of operand A excluding its most significant bit, and B′ is the bits of operand B excluding its most significant bit.    
     
     
         14 . The method of  claim 13  further comprising: 
 using a common set of computational resources for computing the product of operands A and B for both signed and unsigned multiplication.  
 
     
     
         15 . The method of  claim 13  further comprising: 
 identifying whether multiplication or population count is enabled; and  
 using said multiplier to perform population count for a received operand when population count is enabled.