Quantcast

Carry Select Adder

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Carry Select Adder

cadet1620
Administrator
There have been several people investigating the Carry Look-ahead Adder, which is a speed optimization over the ripple carry adder that is built in this course. Designers have come up with many other adder optimizations as well.

Another interesting adder structure that trades hardware for speed is called the Carry Select Adder.

The basic idea is to add 2 bits using 3 1-bit full adders and a 2-bit multiplexer. One adder adds the least significant bit in the normal fashion. The other two add the most significant bit, one of them assuming that the carry in will be 0 and the other assuming that the carry in will be 1.  Then the multiplexer chooses the output from one of these adders based on the carry produced by the adder for the least significant bit.

2-bit Carry Select Adder
This adder gets its speed improvement because multiplexers are usually faster than adders. (CMOS multiplexers are made from transmission gates which are more like switches then logic gates and are very fast.)

CSAs can be cascaded, using longer ripple carry adders, matching the increasing length of the adders to the combined delay through the multiplexers.

16-bit Carry Select Adder
The best length sequence actually depends on the relative speeds of the adders and multiplexers.

It's also possible to combine multiple Carry Look-ahead Adders using CSA techniques.

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

ybakos
Oh my, this is awesome. Thanks for sharing!
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

cadet1620
Administrator
This post was updated on .
Another interesting adder is the Carry Bypass Adder. This is a combination of ripple carry and carry look-ahead adder. The 8-bit version would use two 4-bit ripple carry adders two 4-bit look-ahead generators that only need to supply the P (propagate) signal. Based on the P signal, a multiplexer selects whether to select the carry in or the carry out of the 4-bit adder to pass on to the next adder. Less hardware, but slower than a full Carry Look-ahead Adder.

8-bit Carry Bypass Adder
Multiple levels of carry bypass can be used in longer adders.

16-bit Carry Bypass Adder
--Mark

[Edited to correct schematics.]
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

Shjanzey
Thanks for posting these.  I never thought about using a MUX within an adder, but now I am really keen on the idea.  I think I may implement both of these to help further my understanding of the variations possible with adders.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

cadet1620
Administrator
If you have not already found it, you might want to get Logisim. It's a visual logic simulator that will let you see how the various adders work much easier than the TECS Hardware Simulator. The images in my posts are from Logisim.

The various techniques can be mixed to achieve various tradeoffs between speed and circuit size. Here's one using both look-ahead and select.
16-bit CLA CSA adder

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

Ashry
In reply to this post by cadet1620
Hi u have a great design but there is a mistake in ur design ,
u should use XOR gates instead of OR gates
Ex: try adding 12+15 (using or gates) u have wrong answer
try adding 12+15 (using xor gates ) u will have 27

best wishes ,
Abdallah Ashry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

cadet1620
Administrator
This post was updated on .
Thanks. You are indeed correct that those ORs in the Carry Bypass Adder should be XORs.

I screwed it up when I was cleaning up the circuit for posting. I'll get a corrected version up later today. FWIW, my original Logisim version tapped the XOR(a,b) from the Full Adders but that would have been harder to explain than showing them outside the adders.

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

VLSI_GIRL
In reply to this post by cadet1620
Hi,

Can you put up a truth table for the 8 bit Carry Bypass Adder?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

cadet1620
Administrator
VLSI_GIRL wrote
Can you put up a truth table for the 8 bit Carry Bypass Adder?
I don't understand what you are asking for. The truth table for a Carry Bypass Adder would be identical to the truth table for any other Adder.

Also, an 8-bit adder has 17 inputs so its truth table would have 131072 rows!

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

VLSI_GIRL
I know that, but is it possible for you to put up 8 odd cases, with any combination of the A and B bits. I just want to see the bypass action working for a given combinations.
Thanks.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

cadet1620
Administrator
I suggest that you get Logisim and poke at this circuit adder-carry-bypass-8.circ.

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

tungsten
Thanks for this post!

Is the Carry Select Adder faster than the CLA? What about the CLA/CSA hybrid you've shared, is it faster than the individual?

Was planning on swapping in the CLA to speed up my ALU, but I'm willing to use whatever is fastest.

If circuit size is no concern, what's the fastest adder one can use?
Also which one is the middle-ground(does best job of balancing circuit size and speed)?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

cadet1620
Administrator
tungsten wrote
Is the Carry Select Adder faster than the CLA? What about the CLA/CSA hybrid you've shared, is it faster than the individual?

If circuit size is no concern, what's the fastest adder one can use?
Also which one is the middle-ground(does best job of balancing circuit size and speed)?
Doing static worst case analysis by hand would be quite arduous.
I think that you'd need to code these in an industrial strength HDL (Verilog or VHDL) and run them on a real simulator to figure that out.
Was planning on swapping in the CLA to speed up my ALU, but I'm willing to use whatever is fastest.
Other than an intellectual exercise, this is moot. Because all of these adders involve many more gates, I expect that they will all run slower in the HardwareSimulator. In any case, there is very little correlation between simulator run time and circuit worst case timing.

[I never had to do any designs that needed fast adders. The few times I needed them I just used 4-bit adder parts with ripple carry between them. IIRC the longest one was 9 bits (3 4-bit parts) for a CRT display row counter.]

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

tungsten
Other than an intellectual exercise, this is moot. Because all of these adders involve many more gates, I expect that they will all run slower in the HardwareSimulator.
My problem with the ripple carry adder is that it is serial... Anything that can compute some parts, if not all, in parallel is ideal. I'm interested in performance in a general sense, outside the provided Hardware Simulator.
I think that you'd need to code these in an industrial strength HDL (Verilog or VHDL) and run them on a real simulator to figure that out.
I'll do so.

Do you by chance know the type of adders used in microcontrollers such as Atmega and PIC? I looked through the datasheets but this is not something they specify.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

cadet1620
Administrator
tungsten wrote
Do you by chance know the type of adders used in microcontrollers such as Atmega and PIC? I looked through the datasheets but this is not something they specify.
The manufacturers are very proprietary about there implementations. What's in the data sheets is generally all you can get.

I remember reading that Intel's first 8-bit processor, the 8008 released in the early 1970s, used Carry Lookahead in its ALU.

--Mark
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

ivant
Here is a nice article about the 8008's ALU: http://www.righto.com/2017/02/reverse-engineering-surprisingly.html
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Carry Select Adder

tungsten
Funny enough when Mark mentioned the 8008 I too immediately thought of Ken's site! He even has some adder specific articles:
http://www.righto.com/2013/11/the-z-80s-16-bit-incrementdecrement.html
http://www.righto.com/2016/01/counting-bits-in-hardware-reverse.html
Most of it is over my head atm, but very cool.
Loading...