Carry Look Ahead Adders

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, Cg, and Carry propagate, Cp. Cg 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. Cp 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 Cg and Cp 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. Carry generation and carry propagation in terms of the input bits to a 4-bit adder is shown in the figure.

carry look ahead adders

We can now write expressions for the output carry Cout 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 Cin1, the Cg and Cp functions of that stage. Since Cg and Cp 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.