How to design a carry save adder circuit?

Status
Not open for further replies.
M

mahaju

Full Member level 2
Joined
Mar 17, 2007
Messages
125
Helped
7
Reputation
14
Reaction score
2
Trophy points
1,298
Visit site
Activity points
2,252
Code: 
Carry-save accumulators

Supposing that we have two bits of storage per digit, we can store the values 0, 1, 2, or 3 in each digit position. It is therefore obvious that one more binary number can be added to our carry-save result without overflowing our storage capacity: but then what?

The key to success is that at the moment of each partial addition we add three bits:

    * 0 or 1, from the number we are adding.
    * 0 if the digit in our store is 0 or 2, or 1 if it is 1 or 3.
    * 0 if the digit to its right is 0 or 1, or 1 if it is 2 or 3.

To put it another way, we are taking a carry digit from the position on our right, and passing a carry digit to the left, just as in conventional addition; but the carry digit we pass to the left is the result of the previous calculation and not the current one. In each clock cycle, carries only have to move one step along, and not n steps as in conventional addition.

Because signals don't have to move as far, the clock can tick much faster.

There is still a need to convert the result to binary at the end of a calculation, which effectively just means letting the carries travel all the way through the number just as in a conventional adder. But if we have done 512 additions in the process of performing a 512-bit multiplication, the cost of that final conversion is effectively split across those 512 additions, so each addition bears 1/512 of the cost of that final "conventional" addition.

This is from the wikipedia entry
CSA Wikipedia Carry-save adder - Wikipedia, the free encyclopedia

what I don't understand is how do I use a carry save adder in practice. Suppose I need to build a 4 bit adder circuit, but using Carry Save adders instead of the conventional propagation type. What should I do?

And about the carry save accumulator paragraph quoted above, is there a detailed step by step tutorial on how to implement that? I don't understand what it means in the 2nd bullet: 0 if the digit in our store is 0 or 2, or 1 if it is 1 or 3

Please help me here.
Thanks
 

Does the core generator in your tool of choice have an option to generate this carry save adder? If yes, you could generate the core for say a 4 or 8 bit adder, and then take a look at the generated code. That might give you an idea what would be optimal for whatever device you are targeting...
 

actually I need to implement it myself if possible
I have implemented carry propagation adders but I am thinking I may b e able to reduce the addition time by using CSA, but after reading about CSA I stioll have no idea about how to implement it
 

Hi,
Carry Save Adders have many types. Some of them are called as (3:2) CSAs, sum of them compressors(which are (5:3) CSAs). Idea is not to allow carry to ripple, keep carries and sums in vectors. Lets think of three binary vectors you want to add x=(1010), y=(1011), z=(1001). If we want to add them using a carry save adder then

x 1010
y 1011
z 1001
----------
s 1000
c 10110

c(0)=0
(c(1), s(0))=x(0)+y(0)+z(0)
(c(2), s(1))=x(1)+y(1)+z(1)
...
Here s signifies sum, c signifies carry.

CSAs are mostly used in multiplier circuits. Because without waiting for carries you can add 3 or more operands at once. But finally, you have to perform an addition of s(sum) and c(carry). You can use Carry Lookahead Adders or simple ripple carry adders for it.

You have a look at computer arithmetic books for details. Hope this will be useful for you...
 

Do you know where I can find a detail step by step explained numerical?
 

When I was studyign I had found Computer Arithmetic Algorithms(Israel Koren) helpful. You can construct your carry save adder using full adder cells. Decide what type of carry save adder you need.
 
Reactions: mahaju

    M

    mahaju

    Points: 2
    Helpful Answer Positive Rating
and about that z variable in your post, I thought it represented a vector of carry outs from a previous addition
So if I need to add two numbers, I need to have the possible carry outs in each bit precomputed?
 

You can use different types of csa for different needs. For ex if you want to add just one number at each time, then you can use (3:2) csa as:
X
S
C
----
S
C

Then adding another number lets say Y to this sum and carry

Y
S
C
--
S
C

If you have to add 2 numbers at each time, then you can use (5:3) CSA
X
Y
S
C
--
S
C

Then adding another two numbers to this sum and carry,
A
B
S
C
--
S
C
 

Hello again
This is a small explanation of of the theory behind CSA
The book calls this Redundant Number Representation but in effect is a carry save adder
it is adding 001001, 011110, 011101, 001011, four 6-bit binary numbers
If I add these numbers normally we would get 1001111 as result.
According to this numerical example, 1 2 1 1 1 1 is the result of adding the four numbers in the CSA form (Sum digits in [0,2] just means that the digits of this final answer, ie, 1,2,1,1,1 and 1 are each represented by two bits)
How does this result relate with the normal result (ie, 1001111 ) ?
This is from the book Computer Arithmetic: Algorithms and Hardware design by Behrooz Parhami
 

121111 needs to be represented in binary.

the number is:
101111
+ 100000 (the 2 form the above word)
This equals 1001111
 
Reactions: mahaju

    M

    mahaju

    Points: 2
    Helpful Answer Positive Rating
Oh thank you Very much
I would like to verify this with other numericals
are there any available on the Internet that you know of?

---------- Post added at 11:12 ---------- Previous post was at 10:07 ----------

ok Found and verified
Thanks a lot
 

Status
Not open for further replies.

Similar threads

Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…