Critical path for Carry-Skip adder

Question

Can anybody explain why Carry-Skip adder has the same critical path as regular Carry-Ripple adder. My textbook says that critical path occurs when carry is generated in LSB and then propagating it through the remainder of the adder. The way I see it, critical path occurs when each stage has to either generate or kill carry, therefore every next stage has to wait for the ripple from previous stage to get the sums. All sites are saying that my textbook is correct, but none of them explaining why. I would appreciate any help.

BTW Carry-Skip adder is the same as Carry-Lookahead adder but it doesn't calculate group generate signal.

Answer 1

The worst case scenario for a Ripple-Carry Adder (RCA) is when the LSB generates a carry out, and the carry ripples through the entire adder from bit 0 to bit (N - 1). An example pattern would be 00000001 + 11111111. In adder terminology, bits 7-1 are "Propagators", and bit 0 is a "Generator". The critical path is from the carry-out of the LSB to the carry-out of the MSB, and every adder is in the critical path.

The idea behind a Carry-Skip Adder (CSA) is to reduce the length of this critical path by giving the carry path a shortcut if all bits in a block would propagate a carry. A block-wide propagate signal is fairly easy to compute, and each block can calculate its own propagate signal simultaneously. So the worst case is still the same scenario, but what happens looks a bit different.

Lets say we still have the same problem of 0000......001 + 0111.....111. The first block will calculate a carry in the first bit, and will propagate the carry through bits 1, 2, and 3. At this point, the first block carry-out signal is valid. The propagate select signals are already valid, since it is 2-3 gate delays and the carry signal is 4 gate delays. The carry-in multiplexer for bits 8-11 gets the carry signal from the carry-out of bit 3 since bits 4-7 would propagate a carry. Note that this takes 1 gate delay, while a normal RCA would take 4 gate delays. Each block will add 1 gate delay to the carry signal.

If the MSB killed carry propagation, then that would cause the last CSA block to ripple carry the input, which would take another 4 gate delays. This setup of a LSB generate and a MSB kill is the new worst case. The source of the critical path is the same between the RCA and CSA, but the critical path is different.

If an arbitrary block generated a carry by itself, the carry will always propagate to the next block. However, if the second block generates a carry itself, or kills the carry, than that is the end of the critical path. If the second block propagates the carry, then we see the advantage of the CSA architecture.

Also, when the term "critical path" is used, it generally implies that you are considering a set of inputs that will cause the worst-case delay. Your scenarios that you are providing give "ugly" cases that may have large delay, but it isn't the largest delay.

Answer 2

Let me answer it in this way.

Let's say it have 3 stages in this by-pass adder. And each stage has 4 bits.

If there is any bit generate or delete the carry, it will not need the carry from the 1st stage. In this case, it wouldn't need to wait the result of carry from the previous stage. So, the worse case happens when it should wait for the 1st stage carry.

And let me put it in another way. The worse case delay = setup time + the whole carry time in the 1st stage + 2*by-pass time + (4-1)*carry time for each bit

The carry from input in propagate from the 1st bit to the last bit in the 1st stage. At the same time, the second stage is whether waiting for the carry from 1st stage or start to generate or delete its own carry. And the worse case would be waiting. So, the worse case is the second stage decides to propagate the 1st stage's carry.

Hope this answers your doubts.

Answer 3

In a typical ripple-carry adder which combines e.g. X[3..0]+Y[3..0]+Cin to yield Z[3..0] and Cout, the signals X[0], Y[0], and Cin are all equivalent; all will have the same delay to Cout. If multiple adder stages are chained together, the overall carry propagation time will be the time from the first stage's X[0] and Y[0] to its Cout, plus the times from the subsequent stages' Cin to their Cout. If one chains together e.g. eight identical 4-bit sections, the time from X[0] or Y[0] to Cout will matter only 1/7 as much as the time from Cin to Cout.

Essentially, what happens is that if all inputs arrive simultaneously, a ripple-carry adder would have three equivalent critical paths from X[0], Y[0], and Cin to the carry output. If the carry input doesn't stabilize until long after all the other inputs have done so, then with any combinatorial adder it would be the critical path (nothing else could be critical path, since everything would be waiting on the carry input). A carry-skip adder seeks to minimize the time between when the carry input stabilizes and when its output will stabilize, assuming all other inputs have been stable for awhile, but if all inputs become stable simultaneously, the critical paths from X[0] and Y[0] to the carry output will remain the same.

Incidentally, an adder based upon cascaded carry-skip adders can provide O(sqrt(N)) propagation time with O(N) circuitry by having the higher-order stages be longer than the shorter-order ones. If an N-bit carry-skip stage has a propagation time of 2N+2 gate delays from its X and Y inputs, and 2 delays from its carry input, and an N-bit ripple-carry stage has a time of 2N delays from any input, then if one builds a 32 bit adder from a 4-bit ripple carry stage, and 4, 5, 6, 7, and 8-bit carry-skip stages, the carry from the first stage will stabilize 8 delays after X and Y. The second stage will stabilize 10 delays after X and Y, or 2 cycles after its carry input, whichever happens last (both will happen together). The third stage will stabilize 12 cycles after X and Y, or 2 cycles after its carry input, etc. This is not the fastest way to do addition, but is a good compromise between speed and circuitry. It's possible to reduce propagation time to O(lgN), but doing so requires O(NlgN circuitry).