# Machine Organization & Assembly Language

## CSE 378, Spring Quarter 2000

# Carry-Lookahead Adders

Ripple carry adders are slow because they perform sequential addition of
bits.
The key to fast adders is to perform operations in parallel.

Suppose `c`*i* is the carry in for bit *i* of an adder
and `a`*i* and `b`*i* are bit *i* of the
numbers `a` and `b`.

`
c`*i+1* = (a*i* . b*i*) + (a*i* . c*i*) +
(b*i* . c*i*)

We are interested in determining carry bits quickly, so factor out
`c`*i* in the above equation:

`
c`*i+1* = (a*i* . b*i*) +
(a*i* + b*i*) . c*i*

Consider `c`*2*:

`
c`*2* = (a*1* . b*1*) +
(a*1* + b*1*) . c*1*

Substituting for `c`*1* gives us:

`
c`*2* = (a*1* . b*1*) +
(a*1* + b*1*) . ((a*0* . b*0*) +
(a*0* + b*0*) . c*0*)

Notice that `(a`*i* . b*i*) and
`(a`*i* + b*i*) are repeated expressions. They are called
*generate* (`g`*i*) and *propagate*
(`p`*i*):

`
g`*i* = (a*i* . b*i*)

p*i* = (a*i* + b*i*)

We *generate* a carry `c`*i* if `a`*i* and
`b`*i* are both 1s. `c`*i* will be a 1 regardless of
the carry-in `c`*i-1*.

We *propagate* a carry `c`*i* if either
`a`*i* or `b`*i* (or both) is a 1.
`c`*i* will be a 1 if the carry-in `c`*i-1* is a 1.
It may be a 1 even if `c`*i-1* is a 0 - when?

Plumbing analogy taken from the textbook
Using *generate* and *propagate* values, we can write the two-bit
adder equations as:

`
c`*1* = g*0* + (p*0* . c*0*)

c*2* = g*1* + (p*1* . g*0*) +
(p*1* . p*0* . c*0*)

The *propagate* values cause carries to "ripple" through the
adder. However we can calculate the *generate* and *propagate*
values at the beginning of the addition operation in **parallel** and the
value of `c`*i* does not depend upon the value of
`c`*i-1*.

The equations get excessively complex and thus slow when implemented in
hardware, for carry-lookahead adders of size 16. We can therefore group
carry-lookahead adders into smaller units (say 4 bits) and use the same
trick of determining *generate* and *propagate* values for
these 4 bit adders.

Main Page
Section Notes Page