Carry Look Ahead Adders | Computer Organization And Architecture Tutorials

In a ripple carry adder, the carry from the previous stage should occur first to produce the sum and output carry of any stage. This causes a time delay in the addition process and is called propagation delay or ripple carry delay. The look-ahead carry addition is a method used to speed up the addition process by eliminating the propagation delay. The look-ahead carry adder anticipates the output carry of each stage.

We define two variables Carry generate, C_g, and Carry propagate, C_p.

C_g occurs when an output carry is generated internally by the full adder. A carry is generated only when both inputs are 1s. It is expressed as the AND function of the two inputs.

Carry propagation function specifies when a carry-in would be propagated. C_p may be propagated by the full-adder when either or both of the inputs are 1s. It is hence expressed as the OR function of the two input bits. We write

$C_g=AB$
$C_p=A+B$

The Output carry of a stage can be expressed in terms of C_g and C_p as

$C_{out}=C_g+C_p.C_{in}$

That is we get an output carry of 1 if it is generated by the full adder or if the adder propagates the input carry.

Circuit diagram for a full adder that produces Cg and Cp function is shown below

4 bit Carry Look Ahead Adder

Carry generation and carry propagation in terms of the input bits to a 4-bit adder is shown in the figure.

We can now write expressions for the output carry C_out of each full adder for the 4-bit example.

Full Adder 1

$C_{out1} = C_{g1}+C_{p1}C_{in1}$

Full Adder 2

$C_{in2} = C_{out1}$

$\begin{eqnarray*} C_{out2} &=& C_{g2} + C_{p2}C_{in2} \nonumber \\ &=&C_{g2}+C_{p2}C_{out1} \nonumber \\ &=& C_{g2}+C_{p2}(C_{g1}+C_{p1}C_{in1}) \nonumber \\ &=& C_{g2}+C_{p2}C_{g1}+C_{p2}C_{p1}C_{in1} \end{eqnarray*}$

Full Adder 3

$C_{in3} = C_{out2}$

$\begin{eqnarray*} C_{out3} &=& C_{g3} + C_{p3}C_{in3} \nonumber \\ &=& C_{g3}+C_{p3}C_{out2} \nonumber \\ &=&C_{g3}+C_{p3}(C_{g2}+C_{p2}C_{g1}+C_{p2}C_{p1}C_{in1}) \nonumber \\ &=& C_{g3}+C_{p3}C_{g2}+C_{p3}C_{p2}C_{g1}+C_{p3}C_{p2}C_{p1}C_{in1} \end{eqnarray*}$

Full Adder 4

$C_{in4} = C_{out3}$

$\begin{eqnarray*} C_{out4} &=& C_{g4} + C_{p4}C_{in4} \nonumber \\ &=& C_{g4}+C_{p4}C_{out3} \nonumber \\ &=&C_{g4}+C_{p4}(C_{g3}+C_{p3}C_{g2}+C_{p3}C_{p2}C_{g1}+C_{p2}C_{p1}C_{in1}) \nonumber \\ &=& C_{g4}+C_{p4}C_{g3}+C_{p4}C_{p3}C_{g2}+C_{p4}C_{p3}C_{p2}C_{g1}+C_{p4}C_{p3}C_{p2}C_{p1}C_{in1} \nonumber \\ \end{eqnarray*}$

Observe that the output-carry for each stage is dependent only on the initial input carry C_in1, the C_g and C_p functions of that stage. Since C_g and C_p can be expressed in terms of A and B inputs to the full adder, all the output carries are available immediately. So we don’t have to wait for a carry to ripple through all the stages and there will be no propagation delay.

4 bit Carry Look Ahead Adder

Further Reading