Carry Look Ahead Adder – Circuit, Truth Table & Applications

Different types of Digital systems are constructed from very few types of basic network configurations such as AND gate, NAND gate, Or gate, etc…These elementary circuits are used over and over again in various topological combinations. In addition to performing logic, digital systems must also store binary numbers. For these memory cells, also known as FLIP-FLOP’s are designed. To perform some functions such as binary addition. Hence, to perform such functions, combinations of logic gates and FLIP-FLOPs are designed over a single-chip IC. These IC’s form the practical building blocks of the Digital systems. One of such building blocks used for binary addition is the Carry Look-ahead Adder.

What is a Carry Look-ahead Adder?

A digital computer must contain circuits which can perform arithmetic operations such as addition, subtraction, multiplication, and division. Among these, addition and subtraction are the basic operations whereas multiplication and division are the repeated addition and subtraction respectively.

To perform these operations ‘Adder circuits’ are implemented using basic logic gates. Adder circuits are evolved as Half-adder, Full-adder, Ripple-carry Adder, and Carry Look-ahead Adder.

Among these Carry Look-ahead Adder is the faster adder circuit. It reduces the propagation delay, which occurs during addition, by using more complex hardware circuitry. It is designed by transforming the ripple-carry Adder circuit such that the carry logic of the adder is changed into two-level logic.

4-Bit Carry Look-ahead Adder

In parallel adders, carry output of each full adder is given as a carry input to the next higher-order state. Hence, these adders it is not possible to produce carry and sum outputs of any state unless a carry input is available for that state.

So, for computation to occur, the circuit has to wait until the carry bit propagated to all states. This induces carry propagation delay in the circuit.

Consider the 4-bit ripple carry adder circuit above. Here the sum S3 can be produced as soon as the inputs A3 and B3 are given. But carry C3 cannot be computed until the carry bit C2 is applied whereas  C2 depends on C1. Therefore to produce final steady-state results, carry must propagate through all the states. This increases the carry propagation delay of the circuit.

The propagation delay of the adder is calculated as “the propagation delay of each gate times the number of stages in the circuit”. For the computation of a large number of bits, more stages have to be added, which makes the delay much worse. Hence, to solve this situation, Carry Look-ahead Adder was introduced.

To understand the functioning of a Carry Look-ahead Adder, a 4-bit Carry Look-ahead Adder is described below.

In this adder, the carry input at any stage of the adder is independent of the carry bits generated at the independent stages. Here the output of any stage is dependent only on the bits which are added in the previous stages and the carry input provided at the beginning stage. Hence, the circuit at any stage does not have to wait for the generation of carry-bit from the previous stage and carry bit can be evaluated at any instant of time.

Truth Table of Carry Look-ahead Adder

For deriving the truth table of this adder, two new terms are introduced – Carry generate and carry propagate. Carry generate Gi =1 whenever there is a carry Ci+1 generated. It depends on Ai and Bi inputs. Gi is 1 when both Ai and Bi are 1. Hence, Gi is calculated as Gi = Ai. Bi.

Carry propagated Pi is associated with the propagation of carry from Ci to Ci+1. It is calculated as Pi = Ai ⊕ Bi. The truth table of this adder can be derived from modifying the truth table of a full adder.

Using the Gi and Pi terms the Sum Si and Carry Ci+1 are given as below –

• Si = Pi ⊕ Gi.
• Ci+1 = Ci.Pi +Gi.

Therefore, the carry bits C1, C2, C3, and C4 can be calculated as

• C1 = C0.P0+G0.
• C2 = C1.P1+G1 = ( C0.P0+G0).P1+G1.
• C3 = C2.P2+G2 = (C1.P1+G1).P2+G2.
• C4 = C3.P3+G3 = C0.P0.P1.P2.P3 + P3.P2.P1.G0 + P3.P2.G1 + G2.P3 + G3.

It can be observed from the equations that carry Ci+1 only depends on the carry C0, not on the intermediate carry bits.

Circuit Diagram

The above equations are implemented using two-level combinational circuits along with AND, OR gates, where gates are assumed to have multiple inputs.

The Carry Look-ahead Adder circuit fro 4-bit is given below.

8-bit and 16-bit Carry Look-ahead Adder circuits can be designed by cascading the  4-bit adder circuit with carry logic.

Advantages of Carry Look-ahead Adder

In this adder, the propagation delay is reduced. The carry output at any stage is dependent only on the initial carry bit of the beginning stage. Using this adder it is possible to calculate the intermediate results. This adder is the fastest adder used for computation.

Applications

High-speed Carry Look-ahead Adders are used as implemented as IC’s. Hence, it is easy to embed the adder in circuits. By combining two or more adders calculations of higher bit boolean functions can be done easily. Here the increase in the number of gates is also moderate when used for higher bits.

For this Adder there is a tradeoff between area and speed. When used for higher bit calculations, it provides high speed but the complexity of the circuit is also increased thereby increasing the area occupied by the circuit. This adder is usually implemented as 4-bit modules which are cascaded together when used for higher calculations. This adder is costlier compared to other adders.

For boolean computation in computers, adders are being used regularly. Charles Babbage implemented a mechanism for anticipating the carry bit in computers, to reduce the delay caused by the ripple carry adders. While designing a system, the speed of computation is the highest deciding factor for a designer. In 1957, Gerald B. Rosenberger patented the modern Binary Carry Look-ahead Adder. Based on the analysis of gate delay and simulation, experiments are being conducted to modify the circuit of this adder to make it even faster. For an n-bit carry look-ahead adder, what is the propagation delay, when given a delay of each gate is 20?

Image Credit

Research Gate