Tag: 4 bit carry look ahead adder

Carry Look Ahead Adder

Carry Look Ahead Adder-

 

  • In Ripple Carry Adder, each full adder has to wait for its carry-in from its previous stage full adder to start its operation which causes an unnecessary delay.
  • Carry Look Ahead Adder is an improved version of the ripple carry adder which generates the carry-in of each full adder simultaneously without causing any delay.

 

Logic Diagram for Carry Look Ahead Adder-

 

 

Working of Carry Look Ahead Adder-

 

  • The working of carry look ahead adder is based on the principle that the carry-in of any stage full adder is independent of the carry bits generated during intermediate stages and is only dependent of the following two parameters-

 

  1. Bits being added in the previous stages
  2. Carry provided in the beginning

 

  • Since, the above two parameters are always known, the carry-in of any stage full adder can be evaluated at any instant of time. Thus, a full adder need not wait until its carry-in is generated by its previous stage full adder.

 

Example-

 

Suppose we want to add two 4-bit binary numbers A3A2A1A0 and B3B2B1B0

They will be added as-

 

 

From here, we have-

C1 = C0 (A0 ⊕ B0) + A0B0

C2 = C1 (A1 ⊕ B1) + A1B1

C3 = C2 (A2 ⊕ B2) + A2B2

C4 = C3 (A3 ⊕ B3) + A3B3

 

For simplicity, Let-

  • Gi = AiBi where G is called carry generator
  • Pi = Ai ⊕ Bi where P is called carry propagator

 

Then, re-writing the equations, we have-

C1 = C0P0 + G………….. (1)

C2 = C1P1 + G1 ………….. (2)

C3 = C2P2 + G2 ………….. (3)

C4 = C3P3 + G3 ………….. (4)

 

Now, let us remove C1, C2 and C3 from RHS of every equation as these are intermediate carry bits.

Substituting (1) in (2), we will get C2 in terms of C0 and then substituting (2) in (3), we will get C3 in terms of C0 and so on.

Finally, we will have the following equations showing that the carry in of any stage depends only on the bits being added in previous stages and the carry bit which was provided in the beginning-

 

  • C1 = C0P0 + G
  • C2 = C0P0P1 + G0P1 + G1
  • C3 = C0P0P1P2 + G0P1P2 + G1P2 + G2
  • C4 =C0P0P1P2P3 + G0P1P2P3 + G1P2P3 + G2P3 + G3

 

Trick to memorize the above equations-

 

Consider any above equation. Let us consider the equation for generating carry bit C2.

Now, if we consider the carry bit C2, then there are three possible reasons for its generation as shown in the following picture-

 

 

In the similar manner, we can write other equations as well very easily.

 

Implementation of the carry generator circuits-

 

The above carry generator circuits are usually implemented as two level combinational circuits using AND and OR gates where gates are assumed to have any number of inputs.

 

Implementation of C1

 

C1 = C0P0 + G

 

Implementation of C1 requires 1 AND gate and 1 OR gate.

 

Implementation of C2

 

C2 = C0P0P1 + G0P1 + G1

 

Implementation of C2 requires 2 AND gates and 1 OR gate.

 

Implementation of C3 and C4

 

Similarly, we can implement C3 and C4.

  • Implementation of C3 will require 3 AND gates and 1 OR gate.
  • Implementation of Cwill require 4 AND gates and 1 OR gate.

 

Thus, total number of gates required for implementing carry generators (provided carry propagators Pi and carry generators Gi) are-

Total number of AND gates required for addition of 4-bit numbers = 1 + 2 + 3 + 4 = 10

Total number of OR gates required for addition of 4-bit numbers = 1 + 1 + 1 + 1 = 4

 

General formula-

 

For a n-bit carry look ahead adder to evaluate all the carry bits, we require-

  • Number of AND gates = n(n+1) / 2
  • Number of OR gates = n

 

Need of Carry Look Ahead Adder-

 

  • In ripple carry adder, we have a cascade of n full adders and each full adder has to wait for its carry-in from its previous stage full adder to continue its operation.
  • Thus, nth full adder has to wait until all (n-1) full adders have completed their operations which causes a delay and makes ripple carry adder extremely slow.
  • The situation becomes worst when the value of n becomes very large.
  • To overcome this delay, we use carry look ahead adder in which carry for each full adder is generated simultaneously without any delay.

 

Advantage of Carry Look Ahead Adder-

 

  • The advantage of carry look ahead adder is that it reduces propagation delay.

 

Disadvantage of Carry Look Ahead Adder-

 

  • The disadvantage of carry look ahead adder is that it involves complex hardware.
  • Because it involves complex hardware, it is costlier and it gets complicated as the number of bits increases.

 

Time Complexity-

 

Time complexity of Carry Look Ahead Adder = Θ (logn)

 

Get more notes and other study material of Digital Electronics.

Watch video lectures by visiting our YouTube channel LearnVidFun.