Digital logic | Carry Look-Ahead Adder
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 ith block waits for the (i -1) th block to produce its carry. So there will be a considerable time delay which is carry propagation delay.
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 ith block waits for the (i -1) th 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 S4 is produced by the corresponding full adder as soon as the input
signals are applied to it. But the carry input C4 is not available on its final
steady state value until carry C3 is available at its steady state
value. Similarly C3 depends on C2 and C2 on C1.
Therefore, though the carry must propagate to all the stages in order that
output S3 and carry C4 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 S3 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.
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’ Gi and ‘carry propagate’ Pi then,
Pi = Ai ⊕ Bi
Gi = Ai Bi
The
sum output and carry output can be expressed in terms of carry generate Gi and
carry propagate Pi as
Si
= Pi Xor Ci
Ci+1
= Gi + PiCi
where
Gi produces the carry when both Ai Bi, are 1 regardless of the input
carry. Pi is associated with the propagation of carry from Ci to
Ci+1.
The
carry output Boolean function of each stage in a 4 stage carry look-ahead adder
can be expressed as
C1
= G0 + P0Cin
C2
= G1 + P1C1 = G1 + P1G0 + P1P0Cin
C3
= G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0Cin
C4
= G3 + P3C3 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0Cin
From the above Boolean equations we can observe that C4 does
not have to wait for C3 and C2 to propagate but actually C4 is
propagated at the same time as C3 and C2. 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.
The implementation of three Boolean functions for each
carry output (C2, C3 and C4) for a carry look-ahead carry
generator shown in below figure.
Time Complexity Analysis:
We could think of a carry look-ahead adder as made up of two “parts”
We could think of a carry look-ahead adder as made up of two “parts”
1.
The
part that computes the carry for each bit.
2.
The
part that adds the input bits and the carry for each bit position.
The log
(n) complexity arises from the part that generates the carry, not the
circuit that adds the bits.
Now, for the generation of the nth carry bit, we need to perform a AND between (n+1) inputs. The complexity of the adder comes down to how we perform this AND operation. If we have AND gates, each with a fan-in (number of inputs accepted) of k, then we can find the AND of all the bits in logk(n+1) time. This is represented in asymptotic notation as θ(logn).
Now, for the generation of the nth carry bit, we need to perform a AND between (n+1) inputs. The complexity of the adder comes down to how we perform this AND operation. If we have AND gates, each with a fan-in (number of inputs accepted) of k, then we can find the AND of all the bits in logk(n+1) time. This is represented in asymptotic notation as θ(logn).
Advantages and Disadvantages of
Carry Look-Ahead Adder :
Advantages –
Advantages –
·
The
propagation delay is reduced.
·
It
provides the fastest addition logic.
Disadvantages –
·
The
Carry Look-ahead adder circuit gets complicated as the number of variables
increase.
·
The
circuit is costlier as it involves more number of hardware.
No comments:
Post a Comment