Question

Q. Compare and contrast Ripple-Carry Adder and Carry-Look ahead Adder

1) In a 4-bit ripple-carry adder as shown in Figure 5.2, assume that each full-adder is implemented using the design as shown in Figure 3.11 (a) and each single logic gate (e.g., AND, OR, XOR, etc.) has a propagation delay of 10 ns. What is the earliest time this 4-bit ripple-carry adder can be sure of having a valid summation output? Explain how you reached your answer and how you did your calculations.

Answer 1

Carry-look ahead adder or fast adder is a type of adder used in digital logic. Carry-look ahead adder enhances speed by reducing the amount of time required to determine carry bits. This can be contrasted with the simpler, but usually slower, ripple carry adder for which the carry bit is calculated alongside the sum bit, and each bit must wait until the previous carry has been calculated to begin calculating its own result and carry bit. The carry-look ahead adder calculates one or more carry bits before the sum, which reduces the wait time to calculate the result of the larger value bits. The Kogge-Stone adder is an example of this type.

Suppose that the propagation delays for the and or gates are 0.1 ns each, while that for the xor’s is 0.2 ns. (XOR requires a more complex circuit). Then the delay from A or B to Count is max(0.1 + 0.1 ns, 0.2 + 0.1 + 0.1 ns) = max (0.2, 0.4 ns) = 0.4 ns.

Suppose a CPU is designed to run at 2 GHz. Then the
worst-case propagetion delay down any path must be less than
1 / (2 GHz) = 1 / (2 x 109 sec-1) = 0.5 x 10-9 sec = 0.5 ns

In 4 bit Carry Look ahead method

In case of binary addition, A + B generate if and only if both A and B are 1. If we wrote G(A,B) to represent the binary predicate that is true if and only if A + B generates, we have:
G(A,B) = A.B
It was based on
the fact that carry signal will be generated in two cases:
(1) when both bits Ai and Bi are 1, or
(2) when one of the two bits is 1 and the carry-in (carry of the previous stage) is 1

We can write the carry-out of this adder using sum of products. However, there is an alternate way of writing the carry out.

Before discussing how to write it, let's define a few terms first. Recall that we are adding 2 n-bit numbers: xn-1...x0 to yn-1...y0 which results in zn-1...z0. In a ripple carry adder, we assign a full adder (call it adder i) to add xi to yi. We'll use the ripple carry adders which only uses full adders.

Adder i also has a carry in. We'll call that ci. It generates a carry out, which we'll call ci + 1. When we add the least significant bits c0 = 0. However, we'll simply leave it as c0.

We can write the Boolean expression for the carry-out in an alternating way:

ci+1 = xiyi + xici + yici
This Boolean expression has the same truth table as above. Even it makes intuitive sense. There's a carry out when any 2 of the 3 bits (i.e., xi, yi, or ci) have a value of 1. Thus, xiyi is 1 only when both xi and yi are 1. And since this is inclusive OR, all 3 bits could be 1.
We use the distributive property to rewrite the carry out as:

ci+1 = xiyi + ci(xi + yi)
Let's define 2 terms:
gi = xiyi
pi = xi + yi
Then, we can rewrite ci + 1 using these two terms, as:
ci+1 = gi + pici
gi is called the generate term. This always generates a carry out. gi = xiyi, which is 1 only when xi and yi are both 1. Clearly, if two bits are 1, there's a carry.
pi is called the propagete term. pi = xi + yi. This could create a carry, but it may not. We know that at least one of xi or yi must be 1 if pi = 1.

This is called propagate for the below reason. If exactly one of xi or yi is 1, then the carry-in determine whether there is a carry-out of 1 or not. Thus, if ci is 1, there is a carry-in of 1, which will cause a carry-out of 1. If ci is 0, then the carry-out is 0.

To propagate, in this case, means to assist. For example, suppose you are standing in a line. Some one say’s to hand something forward, say, a piece of paper. Though you did not bring the piece of paper, you can help move it along (i.e., help propagate it) by forwarding it to the next person. Similarly, propagating a carry means to move the carry from the previous adder to the next adder.

Mostly, we only care about propagating a 1. We are not that concerned about propagating 0's. That's why we AND pi to ci. By itself, pi may not cause a carry. Though, it can propagate a carry-in of 1, by causing a carry-out of 1, if pi is 1.