Multiple Operand Adder
I was doing a hardware design and found that I needed to add 3 numbers together (i.e. A+B+C), because there was one global offset (A), a offset based on the line of a frame of data that needed to be processed, and then an offset within that line.
The critical path in an adder is always the carry propagation logic because the carry out depends on all the lower bits. The naive way to add 3 numbers would be to do two additions, which would incur 2 carry propagation delays. Surprisingly, at least to me, it turns out that you can actually add 3 numbers while incurring only 1 carry propagation delay.
This trick is probably quite familiar with those designing multipliers, because you have to deal with multiple operand addition when you are adding the partial products. But, I was totally unfamiliar with it before.
Here are the steps.
Say you have to add 3 K bit numbers: A, B, and C.
Pass the 3 inputs through K 3:2 compressors. The logic table for a 3:2 compressor is as follows:
| A | B | C | O1 | O0 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
The output in this truth table is a count of the number of 1s in the 3 inputs, this is nothing but a full adder. Applying K of these 3:2 compressors, one for each bit of the 3 inputs (A,B,C), gives 2 K bit outputs (O1 and O0). Now, multiply O1 by 2 (shift left by 1), and then add it to O0. This will give you your final answer.
2*O1 + O2 = A + B + C
So, we have only incurred the 1 carry propagate delay while adding (2*O1 and O2). Note that we can also use a 4:2 compressor if we have 4 inputs. If we have more than 4 inputs, then we have to break them into 4:2 and 3:2 compressors.
Did you enjoy this post? Why not leave a comment below and continue the conversation, or subscribe to my feed and get articles like this delivered automatically to your feed reader.
Comments
This post has been included in the 42nd Carnival of Mathematics. See this and the other posts at http://www.johndcook.com/blog/2008/10/24/42nd-carnival-of-mathematics/.
Thanks for adding to the variety of the carnival posts by submitting a hardware article.
This, to me, is a custom adder, and could be expanded to any number of bits; you effectively displayed the logic table for adding 3 bits. Look at O1 as the 2’s place.
So you could use the equivalent of a 5:3, 6:3, 7:3 and 8:3 compressor to add up to 8 numbers, and an X:4 compressor to add up to 16 numbers, compressing the number of numbers into its binary representation size.
[...] algorithm for simultaneously adding three integers more efficiently in a microchip. Check out Multiple Operand Adder posted at Thread Pool for an insight into the work that goes into operations most of us take for [...]