8

I see carry-lookahead adders and ripple-carry adders terms being used often. I have no idea what either means (nor the type of architecture they describe).

Can someone please explain what each one is, why one may be faster than the other, and what each is used for?

Also, are there any external sources that may help with the matter?

Dave Tweed
  • 168,369
  • 17
  • 228
  • 393
Bob John
  • 237
  • 2
  • 5
  • 11

1 Answers1

7

A system of ripple-carry adders is a sequence of standard full adders that makes it possible to add numbers that contain more bits than that of a single full adder. Each full adder has a carryin (Cin) and a carryout (Cout) bit, and the adders are connected by connecting Cout on step k to Cin on step k+1 (Cin on step 0 is C0 in the picture, Cout on step 3 is C4 in the picture)

Ripple-carry adder - picture from Wikipedia

The challenge with ripple-carry adders, is the propagation delay of the carry bits. Assume that, in an instant the values of A and B change, such that

A1 = 0
B1 = 1
A0 = 1
B0 = 1

Since A0 and B0 are high, the first full adder will produce a carry, i. e. C1 = 1. However, it takes some time for the logic to settle down, so C1 doesn't change until a little after A1 and B1 changed. Thus, before C1 shows up, the second full adder does not produce a carry, but as C1 shows up, the second adder will recompute and produce a carry, i. e. C2 = 1. In the worst case, C4 is not correctly computed until 4*propagation delay, and Cn is not computed until n*propagation delay.

A carry-lookahead adder system solves this problem, by computing whether a carry will be generated before it actually computes the sum. There are multiple schemes of doing this, so there is no "one" circuit that constitutes a look-ahead adder. The idea is something like this:

Look-ahead carry adder

The calculation of C4 is no faster than in the the ripple-carry above, nor is PG and GG - the magic only happens when you put several of these blocks together to add even larger numbers.

The important to note part of the picture, is that the purple block is producing three values: C4, PG (Propagate) and GG (Generate). PG goes high if this block will propagate Cin to Cout, and GG goes high if the block will generate an overflow regardless of Cin. (Also, the block may neither propegate nor generate a carry, in which case both PG and GG are low, and Cout is 0.) PG and GG can be calculated in the purple block regardless of the value of C0 - thus, when C0 finally arrives, the purple block can simply consult its previously calculated result, and if the result is a "propagate," then C0 is propagated directly to C4; this is four times faster than propagating through all the four full adders.

The reason why the block has the outputs PG and GG is so that, in a hierarchal fashion, we can acquire even greater propagation speedups.

Also see: http://faculty.kfupm.edu.sa/COE/abouh/Lesson3_3.pdf

tor
  • 670
  • 4
  • 6
  • The one point worth adding to this excellent answer is that if you are deciding between adder architectures for an FPGA project, Xilinx and probably others use dedicated fast carry logic for the ripple carry adder, so that for most FPGA designs, the simpler ripple carry adder is practically as fast as the carry lookahead. –  Feb 17 '13 at 10:29
  • As for what each is used for, ripple carry uses less logic (area, dynamic and static power) so may be preferred when fast enough (Cortex-M0?). Fast adder speedup increases with bit count, so a wider adder makes such speedup techniques more attractive. As usual, wikipedia is a decent source: http://en.wikipedia.org/wiki/Carry-lookahead_adder –  Feb 17 '13 at 11:08