Carry Select Adder

[cadet1620]

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.


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.


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

[ybakos]

Oh my, this is awesome. Thanks for sharing!

[cadet1620]

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.


Multiple levels of carry bypass can be used in longer adders.


--Mark

[Edited to correct schematics.]

[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.

[cadet1620]

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.


--Mark

[Ashry]

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

[cadet1620]

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

[VLSI_GIRL]

Hi,

Can you put up a truth table for the 8 bit Carry Bypass Adder?

[cadet1620]

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

[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.

[cadet1620]

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

--Mark

[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)?

[cadet1620]

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

[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.

[cadet1620]

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

[ivant]

Here is a nice article about the 8008's ALU: http://www.righto.com/2017/02/reverse-engineering-surprisingly.html

[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.

[YoungFear620]

Awesome scheme, thanks! I'll try it.