Arithmetic - Signal Processing Systems - page 589

Tabl e 1 Cases for
carry-propagation in a full
adder cell

a i b i c i − 1 Case

0 0 0 No carry-propagation (kill)

0 1 c i Carry-propagation (propagate)

1 0 c i Carry-propagation (propagate)

1 1 1 Carry-generation (generate)

Fig. 9 Illustration of N -stage
carry-lookahead carry
propagation

group generate

c i −( N +1) group propagate

c i

Now, the carry output can be expressed as

c i − 1 = g i + p i c i . (12)

For the next stage the expression becomes

c i − 2 = g i − 1 + p i − 1 c i − 1 = g i − 1 + p i − 1 ( g i + p i c i )= g i − 1 + p i − 1 g i + p i − 1 p i c i . (13)

+

For N 1:thstagewehave

c i − ( N + 1 ) =

+

p i − N g i − ( N − 1 ) + p i − N p i − N − 1 g i − ( N − 2 ) + ··· +

... .

(14)

g i − N p i − N p i − 1 p i c i

The terms containing g k and possibly p k terms are called group generate, as they
together acts as a merged generate signal for all the bits i to i

− N . The subterm

p i − 1 p i is similarly called group propagate. Both the group generate and
group propagate signals are independent of any carry signal. Hence, ( 14 ) shows
that it is possible to have the carry propagate N stages with a maximum delay of one
AND-gate and one OR-gate as illustrated in Fig. 9 . However, the complexity and
delay of the precomputation network grows with N , and, hence, a careful design is
required to not make the precomputation the new critical path.
The carry-lookahead approach can be generalized using dot-operators. Adders
using dot-operators are often referred to as parallel prefix adders. The dot-operator
operates on a pair of generate and propagate signals and is defined as
g k
p k

p i − N ...

g i
p i

g j
p j

g i +

p i g j
p i p j

= • . (15)

l , can be denoted by G k : l
and similarly the group propagate as P k : l . These are then defined as
G k : l
P k : l

The group generate from position k to position l , k <

g k
p k

g k + 1
p k + 1

g l
p l

• •···• . (16)