Can we do better? Can we make addition faster? Clearly, the answer is yes, otherwise, we wouldn't have this discussion.

Row | x |
y |
c _{in} |
c _{out} |
s |

0 | 0 | 0 | 0 | 0 |
0 |

1 | 0 | 0 | 1 | 0 |
1 |

2 | 0 | 1 | 0 | 0 |
1 |

3 | 0 | 1 | 1 | 1 |
0 |

4 | 1 | 0 | 0 | 0 |
1 |

5 | 1 | 0 | 1 | 1 |
0 |

6 | 1 | 1 | 0 | 1 |
0 |

7 | 1 | 1 | 1 | 1 |
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 we discuss how to write it, let's define a few terms
first. Recall that we are adding two n-bit numbers:
x_{n-1}...x_{0} to
y_{n-1}...y_{0} which results in
z_{n-1}...z_{0}. In a ripple carry adder, we
assign a full adder (call it adder *i*) to add **x _{i}**
to

Adder *i* also has a carry in. We'll call that
**c _{i}**. It generates a carry out, which
we'll call

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

cThis Boolean expression has the same truth table as above. It even makes intuitive sense. There's a carry out when any two of the three bits (i.e.,_{i+1}= x_{i}y_{i}+ x_{i}c_{i}+ y_{i}c_{i}

We use the distributive property to rewrite the carry out as:

cLet's define two terms:_{i+1}= x_{i}y_{i}+ c_{i}(x_{i}+ y_{i})

gThen, we can rewrite c_{i}= x_{i}y_{i}p_{i}= x_{i}+ y_{i}

c_{i+1}= g_{i}+ p_{i}c_{i}

**p _{i}** is called the

This is called *propagate* for the following reason.
If exactly one of **x _{i}** or

To propagate, in this case, means to assist. For example, suppose you are standing in a line. Some one says to hand something forward, say, a piece of paper. Even though you did not bring the piece of paper, you can help move it along (i.e., help propagate it) by passing 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're not that
concerned about propagating 0's. That's why we AND
**p _{i}** to

This is how we do it. First, let's write the **c _{1}**
which is the carry out for the adding bit 0 of

cNow, we write it for_{1}= g_{0}+ p_{0}c_{0}

cAt this point, we've used c_{2}= g_{1}+ p_{1}c_{1}

Let's plug that in:

cNotice that we no longer have_{2}= g_{1}+ p_{1}(g_{0}+ p_{0}c_{0}) = g_{1}+ p_{1}g_{0}+ p_{1}p_{0}c_{0}

Let's go one more step further:

cAgain, we would prefer to avoid using_{3}= g_{2}+ p_{2}c_{2}

cAlready, you should be able to detect a pattern. By following the same pattern, you'd expect:_{3}= g_{2}+ p_{2}c_{2}= g_{2}+ p_{2}(g_{1}+ p_{1}g_{0}+ p_{1}p_{0}c_{0}) = g_{2}+ p_{2}g_{1}+ p_{2}p_{1}g_{0}+ p_{2}p_{1}p_{0}c_{0}

c_{4}= g_{3}+ p_{3}g_{2}+ p_{3}p_{2}g_{1}+ p_{3}p_{2}p_{1}g_{0}+ p_{3}p_{2}p_{1}p_{0}c_{0}

You might wonder, why? Why are we computing carries, if the idea is to avoid using carries?

The idea is to construct a circuit for **c _{i}** that
can be fed into the input of adder

The following is an approximate circuit.

The diagram is incomplete. It's missing the wires from
**x _{i}** and

What should you understand from this diagram? The key point to
observe is the carry out of the full adder is *not* attached to
the carry in of the next adder. Instead, there is logic (as defined
by the Boolean expressions from the previous section) that has inputs
from **x _{i}**'s,

Still, it's not quite **O(1)**. Why not? Look at the
formula, for say, **c _{4}**.

c_{4}= g_{3}+ p_{3}g_{2}+ p_{3}p_{2}g_{1}+ p_{3}p_{2}p_{1}g_{0}+ p_{3}p_{2}p_{1}p_{0}c_{0}

Given **c _{i}**, there are

If you build everything out of 2-input AND gates or 2-input OR gates,
then the best you can do is about **O(lg N)** where **N** is
the number of bits in the addition. Still, that's far more efficient
than **O(N)**.

This is one lesson in hardware. Often, you can build faster circuits if you're willing to use more gates (of course, that has its limitations too---more hardware can also mean slower hardware, because it uses up a lot of space, however, the savings in computations usually wins out).