In: Computer Science
Describe the types of logic gates which might be more efficient in defining carry lookahead logic?
Motivation behind Carry Look-Ahead Adder
:
In ripple carry adders, for each adder block, the two bits that are
to be added are available instantly. However, each adder block
waits for the carry to arrive from its previous block. So, it is
not possible to generate the sum and carry of any block until the
input carry is known. The 
 block waits for the 
 block to produce its carry. So
there will be a considerable time delay which is carry propagation
delay.

Consider the above 4-bit ripple carry adder. The sum 
 is produced by the corresponding
full adder as soon as the input signals are applied to it. But the
carry input 
 is not available on its final
steady state value until carry 
 is available at its steady state
value. Similarly 
 depends on 
 and 
 on 
. Therefore, though the carry
must propagate to all the stages in order that output 
 and carry 
 settle their final steady-state
value.
The propagation time is equal to the propagation delay of each
adder block, multiplied by the number of adder blocks in the
circuit. For example, if each full adder stage has a propagation
delay of 20 nanoseconds, then 
 will reach its final correct
value after 60 (20 × 3) nanoseconds. The situation gets worse, if
we extend the number of stages for adding more number of bits.
Carry Look-ahead Adder :
A carry look-ahead adder reduces the propagation delay by
introducing more complex hardware. In this design, the ripple carry
design is suitably transformed such that the carry logic over fixed
groups of bits of the adder is reduced to two-level logic. Let us
discuss the design in detail.

Consider the full adder circuit shown above with corresponding
truth table. We define two variables as ‘carry
generate’ 
 and ‘carry
propagate’ 
 then,

The sum output and carry output can be expressed in terms of
carry generate 
 and carry propagate 
 as

where 
 produces the carry when both
, 
 are 1 regardless of the input
carry. 
 is associated with the
propagation of carry from 
 to 
.
The carry output Boolean function of each stage in a 4 stage carry look-ahead adder can be expressed as

From the above Boolean equations we can observe that 
 does not have to wait for
 and 
 to propagate but actually
 is propagated at the same time
as 
 and 
. Since the Boolean expression
for each carry output is the sum of products so these can be
implemented with one level of AND gates followed by an OR gate.