Binary Adders with 3+ inputs

Thread Starter

budhunter

Joined Feb 29, 2012
3
I want to design a binary adder that adds three numbers (# bits arbitrary, but let's use 3 bits for example). And I have noticed there are relatively convenient ways to do this with carry-save adders where you use the Cin input as the third number input and then you finish the addition with a normal ripple adder. Key point here being that it is significantly faster then designing dual ripple adders.

But these carry-save architectures (also called Wallace Trees) always seem to have N+1 output bits (where N = input bits), and this does not seem like enough for full resolution so I am confused by this.

For example, adding three 3-bit numbers requires 5 output bits for full resolution, but the relatively "standard" architecture I refer to above would only result in 4 output bits.

Am I missing something here, or is this an obvious limitation to the carry-save architecture? Is there a better option?
 

Papabravo

Joined Feb 24, 2006
21,159
You are missing something. A three bit unsigned number can represent 8 different values. The maximum 3 bit unsigned value is 7. Now 7 + 7 + 7 = 21. To figure out how many bits are required you take the ceiling of log to the base 2 of 21.
Rich (BB code):
log_2(21) = log_10(21) / log_10(2) = (1.3222 / .301) = 4.39
Ceiling(4.39) = 5
So it takes 5 bits to represent 22 values in the range [0..21]
Is that clear?
 

Thread Starter

budhunter

Joined Feb 29, 2012
3
Papa -

Thanks for the response but I think you misunderstood my questions. In your code example I understand and agree with you that 5 output bits are required for full resolution for three 3bit numbers.

The problem is that for the circuit architectures I have seen called carry save adders or wallace trees will usually only have N+1 output bits, so four in the above case.

See the example in this pdf for four 4bit numbers:

http://www.ele.uri.edu/Courses/ele444/class/csave_add.pdf

The outputs are labeled S0:S4 which is not enough resolution for four 4bit numbers.

However, after viewing this pdf I am wondering if the last Co output of the ripple adder would be the 6th output bit S5?
 

Papabravo

Joined Feb 24, 2006
21,159
There are five outputs in the range S0:S4, not four. The example adds three four bit numbers. So by the previous example you need:
Rich (BB code):
15 + 15 + 15 = 45
log_2(45) = log_10(45) / log_10(2) = 5.49
Ceiling(5.49) = 6
So representing the set of outputs in the range [0,..,45] will require 6 bits which the diagram shows as five outputs labeled S0:S4 plus the Carry Out which can be considered as the sixth output bit.
 
Last edited:
Top