2
\$\begingroup\$

I thought I understood the concept but wikipedia has confused me. There are two outputs because one's for a partial sum and one's the carry bits. But why must it be used to "compute the sum of three or more n-bit numbers" why can't it compute 2 n-bit numbers?

Also the example given under the basic concept (where the result is 21122120202022022122111011102212) confuses me more because that is just one output, not two?

\$\endgroup\$
2
\$\begingroup\$

But why must it be used to "compute the sum of three or more n-bit numbers" why can't it compute 2 n-bit numbers?

The carry save addition of 2 N-bit numbers results in two (N + 1)-bit numbers being produced, the virtual carry (VC) and the virtual sum (VS).But after getting VC and VS you still have to add the two values together with a convectional adder to get your final result, so only adding 2 numbers is pointless.Take this example, lets say one carry-save addition takes k*T ms, where k = number of N - bit numbers being added, and a convectional adder takes 5T ms to add 2 numbers (regardless of bit width), then if:

1) you added 2 numbers, then

$$ \text{Time(Carry-Save) = 2T + 5T = 7T} $$

$$ \text{Time(Convectional Adder) = 5T} $$

2) you added 3 numbers, then

$$ \text{Time(Carry-Save) = 3T + 5T = 8T} $$

$$ \text{*Time(Convectional Adder) = 5T + 5T = 10T} $$

So carry-save addition is only useful if you have at least 3 operands to add.

Also the example given under the basic concept (where the result is 21122120202022022122111011102212) confuses me more because that is just one output, not two?

In reality there are two outputs, the representation that has been used there is a redundant arithmetic type representation.The number "21122120202022022122111011102212" will actually be represented as two different numbers, the virtual carry (VC) and the virtual sum (VS)

So A = 21122120202022022122111011102212 will be represented as

VC = 100110101010110110110000000011010

VS = 011001000000000000100111011100010

in your carry save adder.The VC number is obtained by looking at each and digit of A in turn, starting from the LSB, if the digit in a particular bit position, say bit position m, is 2 then place a 1 in the m th bit position of VC, otherwise place a zero.VS is obtained by setting all digits that are non-one in A to zero.You could also convert a redundant number to two non-redundant numbers by using the alternative method below.

Say you have B = 22012

Re-Write B using just binary by using 2 bits per digit, ie B = 10,10,00,01,10

Extract the first bit of each digit to form VC and the extract the last bit of each digit to form VS, ie( VC = 11001, VS =00010 )

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.