Methods and apparatus for providing a reduction array
View Patent ↗Methods and apparatus provide for accumulating bit streams from four partial products and producing a carry-save output pair, including: producing the save, S, portion of the carry-save output pair, in accordance with the following Boolean expression: S=d 3 XOR ((d 0 XOR d 1 ) XOR (d 2 XOR Cin)), wherein d 0 , d 1 , d 2 , d 3 are the bit streams from the four partial products, and Cin is a carry in bit stream receivable from an adjacent compression circuit of an overall partial product reduction array.
1. A 4 to 2 compression circuit operable to receive bit streams from at least three partial products and produce a carry-save output pair, comprising:
a plurality of logic gates that are operable to produce the save, S, portion of the carry-save output pair, in accordance with the following Boolean expression:
S=d3XOR ((d0XORd1) XOR (d2XOR Cin)),
wherein d 0 , d 1 , d 2 , d 3 are the bit streams from the four partial products, and Cin is a carry in bit stream receivable from an adjacent compression circuit of an overall partial product reduction array.
2. The compression circuit of claim 1 , further comprising: a multiplexer circuit operable to produce the carry, C, portion of the carry-save output pair, such that:
(i) C=di or Cin, when (d 0 XOR d 1 ) XOR (d 2 XOR Cin) is true; and
(ii) C=d 3 , when (d 0 XOR d 1 ) XOR (d 2 XOR Cin) is false,
where di is d 0 , d 1 , d 2 , or d 3 .
3. The compression circuit of claim 1 , further comprising: a majority function circuit operable to produce a carry output, Cout, for receipt by an adjacent compression circuit of an overall partial product reduction array, wherein Cout may be expressed in accordance with the following formula:
Cout= d 0 .d 1= d 1 .d 2+ d 0 .d 2.
4. A method for accumulating bit streams from four partial products and producing a carry-save output pair, comprising:
producing the save, S, portion of the carry-save output pair, in accordance with the following Boolean expression:
S=d3XOR ((d0XOR d1) XOR (d2XOR Cin)),
wherein d 0 , d 1 , d 2 , d 3 are the bit streams from the four partial products, and Cin is a carry in bit stream receivable from an adjacent compression circuit of an overall partial product reduction array.
5. The method of claim 4 , further comprising: producing the carry, C, portion of the carry-save output pair, such that:
(i) C=di or Cin, when (d 0 XOR d 1 ) XOR (d 2 XOR Cin) is true; and
(ii) C=d 3 , when (d 0 XOR d 1 ) XOR (d 2 XOR Cin) is false,
where di is d 0 , d 1 , d 2 , or d 3 .
6. The method of claim 4 , further comprising: producing a carry output, Cout, for receipt by an adjacent compression circuit of an overall partial product reduction array, wherein Cout may be expressed in accordance with the following formula:
Cout= d 0 .d 1= d 1 .d 2+ d 0 .d 2.