Wednesday, November 16, 2011

Carry Look Ahead Adder


In ripple carry adders, the carry propagation time is the major speed limiting factor.


Most other arithmetic operations, e.g. multiplication and division are implemented using several add/subtract steps. Thus, improving the speed of addition will improve the speed of all other arithmetic operations.
Accordingly, reducing the carry propagation delay of adders is of great importance. Different logic design approaches have been employed to overcome the carry propagation problem.
One widely used approach employs the principle of carry look-ahead solves this problem by calculating the carry signals in advance, based on the input signals.
This type of adder circuit is called as carry look-ahead adder (CLA adder). It is based on the fact that a carry signal will be generated in two cases:
(1) when both bits Ai and Bi are 1, or
(2) when one of the two bits is 1 and the carry-in (carry of the previous stage) is 1.
To understand the carry propagation problem, let’s consider the case of adding two n-bit numbers A and B.




The Figure shows the full adder circuit used to add the operand bits in the ith column; namely Ai & Bi and the carry bit coming from the previous column (Ci ).


In this circuit, the 2 internal signals Pi and Gi are given by:

 The output sum and carry can be defined as :

Gi is known as the carry Generate signal since a carry (Ci+1) is generated whenever Gi =1, regardless of the input carry (Ci).
Pi is known as the carry propagate signal since whenever Pi =1, the input carry is propagated to the output carry, i.e., Ci+1. = Ci (note that whenever Pi =1, Gi =0).
Computing the values of Pi and Gi only depend on the input operand bits (Ai & Bi) as clear from the Figure and equations.
Thus, these signals settle to their steady-state value after the propagation through their respective gates.
Computed values of all the Pi’s are valid one XOR-gate delay after the operands A and B are made valid.
Computed values of all the Gi’s are valid one AND-gate delay after the operands A and B are made valid.
The Boolean expression of the carry outputs of various stages can be written as follows:
C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1 (G0 + P0C0)
  = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0
C4 = G3 + P3C3
  = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C0
In general, the ith carry output is expressed in the form Ci = Fi (P’s, G’s , C0).
In other words, each carry signal is expressed as a direct SOP function of C0 rather than its preceding carry signal.
Since the Boolean expression for each output carry is expressed in SOP form, it can be implemented in two-level circuits.
The 2-level implementation of the carry signals has a propagation delay of 2 gates, i.e., 2τ.
The 4-bit carry look-ahead (CLA) adder consists of 3 levels of logic:



First level: Generates all the P & G signals. Four sets of P & G logic (each consists of an XOR gate and an AND gate). Output signals of this level (P’s & G’s) will be valid after 1τ.
Second level: The Carry Look-Ahead (CLA) logic block which consists of four 2-level implementation logic circuits. It generates the carry signals (C1, C2, C3, and C4) as defined by the above expressions. Output signals of this level (C1, C2, C3, and C4) will be valid after 3τ.
Third level: Four XOR gates which generate the sum signals (Si) (Si = Pi Ci). Output signals of this level (S0, S1, S2, and S3) will be valid after 4τ.

Thus, the 4 Sum signals (S0, S1, S2 & S3) will all be valid after a total delay of 4τ compared to a delay of (2n+1)τ for Ripple Carry adders.
For a 4-bit adder (n = 4), the Ripple Carry adder delay is 9τ

The disadvantage of the CLA adders is that the carry expressions (and hence logic) become quite complex for more than 4 bits. 

Thus, CLA adders are usually implemented as 4-bit modules that are used to build larger size adders.

2 comments:

  1. This is really a good site with great information along with excellent post for all to view and comment on this site.The information present here is helpful for the readers.Overall wonderful site.

    ReplyDelete
  2. I think you’ve made some truly interesting points. Not too many people would actually think about this the way you just did. I am really impressed that there is so much information about this subject that have been uncovered and you did it so well, with so much class. Thanks.

    ReplyDelete