Patent ID: 8639738

Claim:
A method for carry estimation of a truncated-width multiplier, comprising: (a) processing a n-bit Baugh-Wooly 2's complement multiplier and an input multiplication of A×B, where A = - a n - 1 ⁢ 2 n - 1 + ∑ j = 0 n - 2 ⁢ a j ⁢ 2 j ; B = - b n - 1 ⁢ 2 n - 1 + ∑ i = 0 n - 2 ⁢ b i ⁢ 2 i , with a j ,b i ε{0,1}, to generate a first group of n partial products and a second group of n partial products; (b) associating each partial product of the first group with a most significant part (MSP) and associating each partial product of the second group with a least significant part (LSP); (c) dividing the least significant part (LSP) into two groups, a first least significant group of β = ∑ i = 0 n - 1 ⁢ P i , n - i - 1 , P i,j =a j b i , which contains a plurality of elements P i,j of partial product of P i,j =a j b i depending on input information a j ,b i , and a second least significant group containing n−1 bits; (d) truncating the second least significant group and using a compensating circuit to generate a estimated group of λ = ∑ i = 0 n - 2 ⁢ ∑ j = 0 n - i - 2 ⁢ P i , j ⁢ 2 j - n in accordance with the input information included in the first least significant group β; (e) generating a carry estimation value of σ = 2 n ⁢ ⌊ β 2 + λ ⌋ r , where └x┘ r is a round operation for rounding x to its nearest number, for the most significant part (MSP) in accordance with the first least significant group β and the estimated group λ; and (f) using an adder circuit to accumulate the most significant part (MSP) and the carry estimation value; the compensating circuit including: a first cell that comprises a half adder and a NAND logical gate receiving the input information a n , b 0 ; a plurality of second cells, each of the second cells comprising a full adder and an AND logical gate receiving the input information a n−1 , a n−2 , . . . a 1 , b 1 , b 2 , . . . b n−1 ; a third cell comprising a full adder and a NAND logical gate receiving the input information a 0 , b n ; and a fourth cell that comprises a plurality of half adders for receiving the input information and respectively outputting the estimated group λ composed of 2 - 1 ⁢ ∑ j = 0 n - 2 ⁢ a j and the third cell; wherein a total number of the first cell, the second cells and the third cell are equal to n, and the second cells are connected between the first cell and the third cell; and the carry estimation value σ is estimated as σ = [ 1 2 ⁢ ( β + 1 2 ⁢ ∑ j = 0 n - 2 ⁢ a j ] r when conditional expectation values are E[P ij |a j =0]=0 and E ⁡ [ P ij ❘ a j = 1 ] = 1 2 , where P ij is generated from a j ×b i and estimated as a j · E ⁡ [ P ij ❘ a j = 1 ] + ( 1 - a j ) · E ⁡ [ P ij ❘ a j = 0 ] = a j 2 .