Adder and multiplier circuits employing logic gates having discrete, weighted inputs and methods of performing combinatorial operations therewith

Abstract

A circuit and method for deriving an adder output bit from adder input bits, a multiplier circuit, a method of multiplying, a microprocessor and digital signal processor (DSP) employing the circuit or the method and a method of selecting weights and thresholds for logic gates. In one embodiment, the circuit includes: (1) first, second and third logic gates that generate intermediate bits based on threshold comparisons of concatenations of ones of the adder input bits and (2) combinatorial logic that generates the adder output bit from the intermediate bits. In one embodiment, the multiplier includes a summer having at least two inputs with corresponding weights, the inputs corresponding to bits of a multiplicand, the weights based on a multiplier, the summer generating a weighted sum of the multiplicand that represents a multiplication of the multiplicand and the multiplier that is a function of the weighted sum.

What is claimed is:  
     
         1 . A circuit for deriving an adder output bit from adder input bits, comprising: 
 first, second and third logic gates that generate intermediate bits based on threshold comparisons of concatenations of said adder input bits; and    combinatorial logic that generates said adder output bit from said intermediate bits.    
     
     
         2 . The circuit as recited in  claim 1  wherein said adder output bit is selected from the group consisting of: 
 a carry out bit,  
 a carry-generate bit, and  
 a carry-propagate bit.  
 
     
     
         3 . The circuit as recited in  claim 1  wherein said adder input bits are selected from the group consisting of: 
 a carry in bit,  
 first and second addend and augend bits,  
 first and second carry-generate bits, and  
 first and second carry-propagate bits.  
 
     
     
         4 . The circuit as recited in  claim 1  wherein said first logic gate generates a first intermediate bit based on a comparison between a concatenation of ones of said adder input bits and zero.  
     
     
         5 . The circuit as recited in  claim 1  wherein said second logic gate generates a second intermediate bit based on a comparison between a concatenation of ones of said adder input bits and two.  
     
     
         6 . The circuit as recited in  claim 1  wherein said third logic gate generates a third intermediate bit based on a comparison between a concatenation of ones of said adder input bits and four.  
     
     
         7 . The circuit as recited in  claim 1  wherein said combinatorial logic comprises first and second AND gates and an OR gate coupled to outputs thereof.  
     
     
         8 . The circuit as recited in  claim 1  wherein said combinatorial logic generates said carry out bit from ones of said adder input bits.  
     
     
         9 . The circuit as recited in  claim 1  wherein each of said first, second and third logic gates comprises: 
 a summer, having at least two binary inputs with corresponding discrete weights, that generates a-weighted sum of input binary digits presented at said at least two binary inputs; and  
 a quantizer, coupled to said summer, that generates an output binary digit at a binary output thereof that is a function of said weighted sum.  
 
     
     
         10 . The circuit as recited in  claim 9  wherein said discrete weights are integer multiples of a predetermined number.  
     
     
         11 . The circuit as recited in  claim 9  wherein each of said at least two binary inputs comprises: 
 a current source capable of producing a substantially constant electrical current corresponding to a particular discrete weight; and  
 a switch, coupled to said current source, that switches said electrical current as a function of a -corresponding particular input binary digit.  
 
     
     
         12 . The circuit as recited in  claim 9  further comprising a threshold input that provides a threshold number to said quantizer, said output binary digit being a function of a relationship between said weighted sum and said threshold number.  
     
     
         13 . The circuit as recited in  claim 1  further comprising a plurality of other of said circuits coupled together to form a multiplier circuit.  
     
     
         14 . A method of deriving an adder output bit from adder input bits, comprising: 
 generating intermediate bits based on threshold comparisons of concatenations of said adder input bits; and    generating said adder output bit from said intermediate bits.    
     
     
         15 . The method as recited in  claim 14  wherein said adder output bit is selected from the group consisting of: 
 a carry out bit,  
 a carry-generate bit, and  
 a carry-propagate bit.  
 
     
     
         16 . The method as recited in  claim 14  wherein said adder input bits are selected from the group consisting of: 
 a carry in bit,  
 first and second addend and augend bits,  
 first and second carry-generate bits, and  
 first and second carry-propagate bits.  
 
     
     
         17 . The method as recited in  claim 14  wherein said generating said intermediate bits comprises generating a first intermediate bit based on a comparison between a concatenation of ones of said adder input bits and zero.  
     
     
         18 . The method as recited in  claim 14  wherein said generating said intermediate bits comprises generating a second intermediate bit based on a comparison between a concatenation of ones of said adder input bits and two.  
     
     
         19 . The method as recited in  claim 14  wherein said generating said intermediate bits comprises generating a third intermediate bit based on a comparison between a concatenation of ones of said adder input bits and four.  
     
     
         20 . The method as recited in  claim 14  wherein said generating said adder output bit is carried out by first and second AND gates and an OR gate coupled to outputs thereof.  
     
     
         21 . The method as recited in  claim 14  wherein said generating said adder output bit comprises generating said adder output bit from ones of said adder input bits.  
     
     
         22 . The method as recited in  claim 14  wherein said generating said intermediate bits comprises: 
 generating a weighted sum of input binary digits presented at said at least two binary inputs; and  
 generating an output binary digit at a binary output thereof that is a function of said weighted sum.  
 
     
     
         23 . The method as recited in  claim 22  wherein said discrete weights are integer multiples of a predetermined number.  
     
     
         24 . The method as recited in  claim 22  wherein each of said at least two binary inputs comprises: 
 a current source capable of producing a substantially constant electrical current corresponding to a particular discrete weight; and  
 a switch, coupled to said current source, that switches said electrical current as a function of a corresponding particular input binary digit.  
 
     
     
         25 . The method as recited in  claim 22  further comprising providing a threshold number, said output binary digit being a function of a relationship between said weighted sum and said threshold number.  
     
     
         26 . A circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, comprising: 
 a first logic gate that generates a first intermediate bit based on a comparison between a concatenation of said second addend and augend bits and zero;    a second logic gate that generates a second intermediate bit based on a comparison between said concatenation of said second addend and augend bits and two;    a third logic gate that generates a third intermediate bit based on a comparison between a concatenation of said first addend and augend bits and said carry in bit and four;    a first OR gate that generates a fourth intermediate bit based on said first addend and augend bits;    a first AND gate that generates a fifth intermediate bit based on said first addend and augend bits;    a second AND gate that generates a sixth intermediate bit based on said first and third intermediate bits;    a third AND gate that generates a seventh intermediate bit based on said second and fourth intermediate bits; and    a second OR gate that generates said carry out bit based on said sixth, seventh and fifth intermediate bits.    
     
     
         27 . The circuit as recited in  claim 26  wherein each of said first, second and third logic gates comprises: 
 a summer, having at least two binary inputs with corresponding discrete weights, that generates a weighted sum of input binary digits presented at said at least two binary inputs; and  
 a quantizer, coupled to said summer, that generates an output binary digit at a binary output thereof that is a function of said weighted sum.  
 
     
     
         28 . A multiplier circuit, comprising a summer having at least two inputs with corresponding weights, said inputs corresponding to bits of a multiplicand, said weights based on a multiplier, said summer generating a weighted sum of said multiplicand that represents a multiplication of said multiplicand and said multiplier.  
     
     
         29 . The multiplier as recited in  claim 28  wherein said weights are created by bit-shifting said multiplier.  
     
     
         30 . The multiplier as recited in  claim 28  further comprising a further input that provides a bias to said quantizer to bias said multiplication.  
     
     
         31 . The multiplier as recited in  claim 28  wherein said discrete weights are integer multiples of a predetermined number.  
     
     
         32 . The multiplier as recited in  claim 28  wherein each of said at least two inputs comprises: 
 a current source capable of producing a substantially constant electrical current corresponding to a particular weight; and  
 a switch, coupled to said current source, that switches said electrical current as a function of a corresponding particular bits of said multiplicand.  
 
     
     
         33 . A method of multiplying a multiplicand by a multiplier, comprising generating a weighted sum of said multiplicand with a summer having at least two inputs with corresponding weights, said inputs corresponding to bits of said multiplicand, said weights based on a multiplier; and 
 generating an output representing a multiplication of said multiplicand and said multiplier that is a function of said weighted sum.    
     
     
         34 . The method as recited in  claim 33  wherein said generating said weighted sum comprises bit-shifting said multiplier to create said weights.  
     
     
         35 . The method as recited in  claim 33  further comprising providing a bias to said multiplication.  
     
     
         36 . The method as recited in  claim 33  wherein said discrete weights are integer multiples of a predetermined number.  
     
     
         37 . The method as recited in  claim 33  wherein each of said at least two inputs comprises: 
 a current source capable of producing a substantially constant electrical current corresponding to a particular weight; and  
 a switch, coupled to said current source, that switches said electrical current as a function of a corresponding particular bits of said multiplicand.  
 
     
     
         38 . A microprocessor, comprising: 
 a cache memory; and    an arithmetic and logic unit containing at least one of an adder and a multiplier, said at least one including a circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, including: 
 first, second and third logic gates that generate intermediate bits based on threshold comparisons of concatenations of said carry in bit and said first and second addend and augend bits, and  
 combinatorial logic that generates said carry out bit from said intermediate bits.  
   
     
     
         39 . The microprocessor as recited in  claim 38  wherein said first logic gate generates a first intermediate bit based on a comparison between a concatenation of said second addend and augend bits and zero.  
     
     
         40 . The microprocessor as recited in  claim 38  wherein said second logic gate generates a second intermediate bit based on a comparison between a concatenation of said second addend and augend bits and two.  
     
     
         41 . The microprocessor as recited in  claim 38  wherein said third logic gate generates a third intermediate bit based on a comparison between a concatenation of said first addend and augend bits and said carry in bit and four.  
     
     
         42 . The microprocessor as recited in  claim 38  wherein said combinatorial logic comprises first, second and third AND gates and first and second OR gates coupled to outputs thereof.  
     
     
         43 . The microprocessor as recited in  claim 38  wherein said combinatorial logic generates said carry out bit from said first augend bit and said carry in bit.  
     
     
         44 . The microprocessor as recited in  claim 38  wherein each of said first, second and third logic gates comprises: 
 a summer, having at least two binary inputs with corresponding discrete weights, that generates a weighted sum of input binary digits presented at said at least two binary inputs; and  
 a quantizer, coupled to said summer, that generates an output binary digit at a binary output thereof that is a function of said weighted sum.  
 
     
     
         45 . The microprocessor as recited in  claim 44  wherein said discrete weights are integer multiples of a predetermined number.  
     
     
         46 . The microprocessor as recited in  claim 44  wherein each of said at least two binary inputs comprises: 
 a current source capable of producing a substantially constant electrical current corresponding to a particular discrete weight; and  
 a switch, coupled to said current source, that switches said electrical current as a function of a corresponding particular input binary digit.  
 
     
     
         47 . The microprocessor as recited in  claim 44  wherein said circuit further includes a threshold input that provides a threshold number to said quantizer, said output binary digit being a function of a relationship between said weighted sum and said threshold number.  
     
     
         48 . The microprocessor as recited in  claim 38  wherein said circuit further includes a plurality of other of said circuits coupled together to form a multiplier circuit.  
     
     
         49 . A digital signal processor, comprising: 
 a signal input;    a signal output; and    a signal transformation unit containing at least one of an adder and a multiplier, said at least one including a circuit for deriving a carry out bit from a carry in bit and first and second addend and augend bits, including: 
 first, second and third logic gates that generate intermediate bits based on threshold comparisons of concatenations of said carry in bit and said first and second addend and augend bits, and  
 combinatorial logic that generates said carry out bit from said intermediate bits.  
   
     
     
         50 . The DSP as recited in  claim 49  wherein said first logic gate generates a first intermediate bit based on a comparison between a concatenation of said second addend and augend bits and zero.  
     
     
         51 . The DSP as recited in  claim 49  wherein said second logic gate generates a second intermediate bit based on a comparison between a concatenation of said second addend and augend bits and two.  
     
     
         52 . The DSP as recited in  claim 49  wherein said third logic gate generates a third intermediate bit based on a comparison between a concatenation of said first addend and augend bits and said carry in bit and four.  
     
     
         53 . The DSP as recited in  claim 49  wherein said combinatorial logic comprises first, second and third AND gates and first and second OR gates coupled to outputs thereof.  
     
     
         54 . The DSP as recited in  claim 49  wherein said combinatorial logic generates said carry out bit from said first augend bit and said carry in bit.  
     
     
         55 . The DSP as recited in  claim 49  wherein each of said first, second and third logic gates comprises: 
 a summer, having at least two binary inputs with corresponding discrete weights, that generates a weighted sum of input binary digits presented at said at least two binary inputs; and  
 a quantizer, coupled to said summer, that generates an output binary digit at a binary output thereof that is a function of said weighted sum.  
 
     
     
         56 . The DSP as recited in  claim 55  wherein said discrete weights are integer multiples of a predetermined number.  
     
     
         57 . The DSP as recited in  claim 55  wherein each of said at least two binary inputs comprises: 
 a current source capable of producing a substantially constant electrical current corresponding to a particular discrete weight; and  
 a switch, coupled to said current source, that switches said electrical current as a function of a corresponding particular input binary digit.  
 
     
     
         58 . The DSP as recited in  claim 55  wherein said circuit further includes a threshold input that provides a threshold number to said quantizer, said output binary digit being a function of a relationship between said weighted sum and said threshold number.  
     
     
         59 . The DSP as recited in  claim 55  wherein said circuit further includes a plurality of other of said circuits coupled together to form a multiplier circuit.  
     
     
         60 . A logic gate, comprising: 
 first, second and third current paths having preset current magnitudes representing discrete weights;    first, second and third switches coupled to said first, second and third current paths, respectively, and adapted to receive binary digits to open or close said first, second and third switches; and    a quantizer, coupled to said first, second and third switches, that receives an electrical current that is a function of a value of said discrete weights and said binary digits, said electrical current representing a result of an operation with respect to said binary digits.    
     
     
         61 . The logic gate as recited in  claim 60  wherein said first current path is selected from the group consisting of: 
 a current source, and  
 a current sink.  
 
     
     
         62 . The logic gate as recited in  claim 60  wherein said second current path is selected from the group consisting of: 
 a current source, and  
 a current sink.  
 
     
     
         63 . The logic gate as recited in  claim 60  wherein said third current path is selected from the group consisting of: 
 a current source, and  
 a current sink.  
 
     
     
         64 . The logic gate as recited in  claim 60  wherein said quantizer comprises a threshold input that provides a threshold current to the quantizer, said quantizer producing an output that represents a relationship between said electrical current and said threshold current.  
     
     
         65 . A processor containing the logic gate as recited in  claim 60 .  
     
     
         66 . A DSP containing the logic gate as recited in  claim 60 .  
     
     
         67 . A method of selecting weights and a threshold value for a threshold gate having a given fan-in (Δ), comprising: 
 solving  
           v     Δ   /   2       =     1   +       ∑     i   =   0         Δ   /   2     -   1            ν   i       +       ∑     i   =   0         Δ   /   2     -   1            w   i                         
 for v Δ/2 ;  
 solving  
           w     Δ   /   2       =       ∑     i   =   0         Δ   /   2     -   1            ν   i                       
 for w Δ/2 ;  
 solving t Δ+2 =−v Δ/2  for t Δ+2 , wherein w 0 32 0, v 0 =1, w 1 =1 and v 1 =2; and  
 employing said v Δ/2  and said w Δ/2  as said weights and said t Δ+2  as said threshold value in said threshold gate.  
 
     
     
         68 . The method as recited in  claim 67  wherein said v Δ/2  and said w Δ/2  are of minimum value.  
     
     
         69 . The method as recited in  claim 67  wherein said t Δ+2  is of minimum value.