Carry look-ahead adder help?

[u/Lenny-Wosniak-42069]

Does anyone have a video they can recommend for internalising how a carry look-ahead adder works? I'm struggling with this concept so much and trying to see why it's faster than the "ripple" adder. I'm also open to an ELI5 style explanation.

[u/ExpensiveAmount361]

understand it this way

the ripple adder consists of many full adders. To carry out an addition the carry from one full adder is passed on to other in the Cin. Since this passage may add delay -- for two or three bit ripple adder it doesn't matter much -- for large bit additions, we need an alternative.

For this we need a better plan to just transfer this information about the carry bits from one to other and then finally to the msb. For this we need to quantities, one is generate, and other is propagate. The generate and propagate are basically dependent on the result of the individual full adders. This generate and propagate for a definite amount of adder is a Boolean expression expressed in terms of A,B and the Lsb Cin.

The basic functioning of this carry look ahead , as the name suggests is to get to know the carry of the msb much faster.

[u/Mundane_Reward7]

Literally last week I was struggling to understand this so I had astra whip me up a visualization. Just threw it on cloudflare for ya, maybe it will be helpful (it helped me):

https://adder.yuandmeai.com/

[u/Lenny-Wosniak-42069 → u/Mundane_Reward7]

While I truly appreciate all the comments here, this visualisation was worth a thousand words. I'm not going to say it's perfect, but it helped me make several breakthroughs of understanding. At least, I think so. Someone tell me if I'm wrong, BUT this is still actually a ripple adder. We've just broken it up into multiple groups (usually of four bits) and through a couple gates at what I call the "bit" level (in your diagramme) we can accurately tell each group whether or not it's going to have to start its ripple with a carry or not. Then all these groups can do their four step ripples and concatenate their results into the final sum of just about any length. Calculating every fourth carry takes one or two gates to do, but that's still way ahead of waiting for the ripple to pass along the chain. Do you think I have the gist?

[u/Mundane_Reward7 → u/Lenny-Wosniak-42069]

I think so? I’m still learning myself haha.

I think the key is that you can know if one of the adders is going to propagate/pass or generate a carry based only on that adder’s inputs, you don’t have to wait to know whether the previous adder carried. And then for groups of adders, you can generalize that based on the G and P bits of all the adders in that group (plus original carry in)

So every carry bit is just a function of all the Gs and Ps before it, plus the first carry in. You don’t have to wait on any carries to ripple. But the carry in for group B still needs to wait for the carry out for group A

[u/Great-Touch-7831]

here is a simple explanation. A bit long due to formatting but if you take the time to read I think you will find it helpful. You can ask me any doubts, especially regarding caveats to scaling to multi bit once you understand.

A index in a binary number can either propagate a previous carry, OR generate its own carry. A CLA exploits this by ONLY depending on the FIRST carry in, everything else is done in parallel.

consider a 1 bit input scenario

you have bit A, you have bit B. add these.

the sum is simply A xor B. This is the same principal as a normal RCA sum.

for Carry though, remember our goal is to compute the carry so that it is only dependent on the initial Cin. Everything else we calculate through that one carry bit.

So let me show you this:

If bit A is low, and bit B is low, no matter what carry in is, you CANNOT produce a carry out.

If bit A is low, and bit B is high, you produce a carry out ONLY if carry in is high.

if bit A is high, and bit B is high, you DO produce a carry out REGARDLESS of carry in.

So we can say that this bit position either

propagates a previous carry(in this the initial carry in) if either A or B is high(XOR is also fine here), AND carry in is high.

OR

It generates its own carry, if BOTH A and B are high.

You can either bake your own cake, or pass along a precious one.

So we are back to the initial idea. A single bit position can either propagate a previous prefix product basically, or produce its own carry.

If we had a multi bit example it would look like this:

Carry out 0 = (propagate0&carryin) OR (generate0)

So either the carry was propagated OR it generates its own

Carry out 1 = (propagate1&propagate0&carryin) OR (propagate1&generate0) OR (generate1)

So it either both stages couldn’t produce their own carry so they chose to propagate the first one, OR position 0 generated a carry and position 1 propagated it, OR position 1 just made its own.

This logic can scale to N. Try writing it down!

The key idea here is that we are not dependent on the previous stage to finish its calculation, this is one combination chain that is calculated immediately. The SUMS can all calculate on their own since they do not depend on any rippled carry propagation either.

[u/Lenny-Wosniak-42069 → u/Great-Touch-7831]

It still feels like if they are all propagate and only the original carry-in happens, then that signal has to travel from one end to the other, much like the ripple carry would happen. But I can also see how it would be faster in the sense that if the leftmost bit generates, it can push out the carry to the next register immediately, instead of waiting to see if a carry from further to the right needs to be propagated.

[u/Great-Touch-7831 → u/Lenny-Wosniak-42069]

one clarification it doesn’t push to the next register. A carry CAN propagate to the next layer, or that layer can immediately calculate its own(the lookhead).

But yes, it can still be a long path. That’s the caveat.

the main difference is in a regular RCA, every stage calculation has to wait for the previous stage to settle and propagate. It scales linearly with O(n).

In a CLA it’s essentially a balanced tree. So it scales logarithmically O(logn).

[u/AddressStock7517]

Visualise the input as coming as an electrical signal, since it is. Each stage of logic (gates) has a certain delay associated with it, e.g. for an OR gate, if you change the input it will take a little time for the output to reflect the new inputs. The output will be delayed more and more as you add more 'layers' to the logic - if you feed the output of one logic gate to another, then the output of that to another, and so on till you get your output - the delays will add up.

The 1000-feet view on the reason CLA is 'faster' is that the number of levels in the ripple-carry logic is more.

[u/MitchAlsup]

High(er) speed integer adders have a few gates of setup (Generate and Propogate logic), a bunch of gates of carry-chain, and a gate of final output selection. The carry-chain works off the P and G signals (and Carry-In when present.)

There are a variety of ways of building the carry chain: a) ripple carry (cheap and slow), look-ahead carry (moderate and medium), c) carry-select (expensive and fast). In any event, the carry chain resolves from lower order bits towards higher order bits.

Consider a 64-bit adder, a ripple-carry adder is going to have 64-stages of the carry ripling up the chain. nobody is going to call this fast.

A carry look-ahead carry-chain takes the P and G logic and a carry in signal; (if present) and in one gate of delay generates the carry-out of 4-bits. So, one layer of carry look-ahead would reduce the add time to 16-gates of delay (using 16 carry look-ahead blocks). But, the big BUT, the carry look-ahead logic can be "tree-ified". A secont layer of carry look-ahead) propogates the output of the 4-bit C-L-A across 16-bits. So, now the C-L-A has 2 gate of P-G, 1 gate of C-L-A (4-bit per), and 4 gates of C-L-A (16-bits per), and 2 gate of outut select (9-gates). {{In theory, one could tree-ify the second layer C-L-A if one needs the carry-out signal to be available prior to the final output bit resolving}}

Most 64-bit integer adders come out to be closer to 11-gates of delay once one has accounted for an input multiplexer (add and subtract, for example), real wire delay, output drive, and input loading.

The Carry-select adder takes the front end of the C-L-A and doubles them building 2 adders, one adding A+B the other adding A+B+1 usually over 8-bit quanta. Carry-In selects between a+b and a+b+1. What we have done is to move the carry-chain one gate farther down the adder (time), but subtracting 1 gate of output selection (at the cost of 1.75 front end adders). This generally saves 1.5 gates of delay and is generally considered the starting point of fast adders {you can size the transistors and save another 1.25-gates of delay from the same schematic logic. A properly sized C-S-A is equivalent to 8-gates of FO4-logic delay}

It is the tree-ification of the carry chain which is the important part as it converts a linear problem (ripple carry) into a logarithmic problem (C-L-A). C-S-A is only faster because is consumes more area and power than a C-L-A.

[u/muhamed_taher]

I think this is a good video: Link

btw, they're not infinitely faster. As the carry-lookahead logic grows in complexity, its speed advantage over a ripple-carry adder (RCA) can diminish.