Computers. They are present in almost everything we use. From our phones to our washing machines, induction cookers to television sets, computers have taken over our lives everywhere. The diversity in the tasks they perform really marvels me sometimes.
To accommodate all the task requirements, computers perform a lot of arithmetic and logical operations. Some of these arithmetic operations are addition, subtraction, multiplication, and division.
If we trace back into our mathematical concepts and think, multiplication is nothing but repeated addition. Division is visibly subtraction carried out repeatedly. Exponential values again are just repeated addition.
Thus, the most powerful of operations need not have complex circuitry made for different operations. It can all come down to basic circuits made purely for addition and subtraction.
A variety of digital adder circuits are implemented using logic gates. These include half adders, full adders, carry-look ahead adders and ripple-carry adders. The carry-look ahead adder, amongst all these, is the fastest adder circuit. Undoubtedly, addition requires quite a time for the result to be generated. However, by using complex hardware circuitry, the propagation time is reduced, thus producing results much quicker than anticipated. Thus, these are also called fast adders.
What is a Carry Look Ahead Adder?
A carry look-ahead adder (CLA) is an electronic adder used in digital logic. Due to the quick additions performed, it is also known as a fast adder. The CLA logic uses the concepts of generating and propagating carries. We can say that the CLA adder is the successor of the Ripple Carry Adder.
Why do we use/need a Carry Look Ahead Adder?
In parallel adders, we can perform the addition operation when both values required to perform addition, i.e. the augend and the addend, are present at the same time. In parallel adder circuits, the carry output of one stage serves as the carry input of the succeeding stage, thus being called the ‘ripple’ carry adder.
‘Ripple’? Why called so?
What happens when we throw a stone in the water? The water around the stone-hit area flows ahead in the form of ripples. Similarly, in the Ripple Carry Adder, the Carry bit ‘ripples’ forward into the system.
To begin with, when we consider a 4-bit ripple carry adder, we see that the augend and the addend are readily available. All that is left for the full adder to begin working is the input carry. This carry is given as an input to the first full adder. But the remaining full adders require the carry-output of the previous adder to be an input in their systems. To put it in other words, it is not possible for a full adder to generate the sum and carry of the respective block unless the input carry is known.
Consider block 1, block 2, and so on. In general, let us represent these blocks with variables i, i+1, …..
If we analyze the system carefully, the (i+1)^{th }block waits for the i^{th }block to generate a carry. The sum S3 generated on the availability of input signals A3 and B3, but the Carry C4 does not get generated until the previous carry C3 is available, which in turn cannot be present without the presence of C2, which is again dependent on the previous carries C1 and Cin. As a result, the entire operation has a lot of delay within the system, which can be called as the carry propagation delay.
The total propagation time is equal to the sum of all the individual propagation delays of each Full Adder block present in the system. Undeniably, the propagation time of the system increases if the number of Full Adder blocks (i, in this case) increases, i.e. if we perform the addition of larger numbers (8-bit or 16-bit).
How can we overcome this issue? We have two solutions to this.
- Introduce faster gates in the system with smaller delays. But we cannot keep adding more and more gates in the circuit; this would increase the size of the overall prototype and in turn, cause more power dissipation and lead to faster damage of the system.
- Modify the circuit in such a way that, even though the complexity increases by a small degree, it performs the same function more efficiently and does not depend on the carry of the previous system.
Thus came the Carry Look Ahead Adder, which solved the problem faced by the Ripple Carry Adder’s dependency on the prior carry inputs.
Working of a Carry Look Ahead Adder
Truth Table
Let us consider a 4-bit CLA Adder. We have the inputs signals A, B, and Cin. If we consider the addition of these three variables in every possible case, we get a truth table like the one below.
On analyzing the truth table, we see that the Carry is 1 when
- (i) Either the value of A or B is one, as well as Cin, is 1, or;
- (ii) Both A and B have the value 1
Let us now consider two new variables, Carry Generate Gi and Carry Propagate Pi.
For case (i) , we see that an output carry is propagated, when we give an input carry. We will refer to this with Pi. So, the mathematical expression of Pi can we represented as :
Pi = Ai ⊕ Bi
While considering case (ii), we see that an output carry is generated when both inputs, A and B, are high, regardless of the value of the input carry. We will refer to this output carry as Gi. Thus, we can mathematically express Gi as :
G_{i} = A_{i }. B_{i}
Thus, we can express the Sum output and Carry output in terms of Carry Propagate Pi and Carry Generate Gi as :
Sum = Pi ⊕ Ci
Carry = Gi + Pi . Ci
The equations of Sum and Carry can be represented by a logic circuit given below.
4-bit Carry Look Ahead Adder
Consider the 4-bit Carry Look Ahead Adder system shown below.
We can calculate the output carry C1, C2, C3, and C4 using the above derived equations as:
C1 = (C_{in }. P0) + G0
C2 = ( C1 . P1 ) + G1 = ((( C_{in }. P0 ) + G0 ) . P1) + G1
= (C_{in }. P0 . P1) + ( G0 . P1 ) + G1
C3 = ( C2 . P2 ) + G2 = ((( C1 . P1 ) + G1 ) . P2 ) + G2
= G2 + ( P2 . G1 ) + ( P2 . P1 . G0 ) + (P2 . P1 . P0 . C_{in })
C4 = ( C3 . P3 ) + G3
= (C_{in }. P0 . P1 . P2 . P3) + ( P3 . P2 . P1 . G0 ) + ( P3 . P2 . G1 ) + ( G2 . P3 ) + G3
Circuit Diagram
The circuit for the above equations can be constructed as shown below.
We can see that there is no dependency on any intermediate Carry values in any of the equations. On solving the equations, we see that only the input Carry C_{in} is required to calculate all the Sum and Output Carry values. This resolves the issue faced by the Ripple Carry Adder’s dependency on the intermediate carry values.
Thus, the entire operation works faster for higher-order bits, when compared to the Ripple Carry Adder. This is the reason why the CLA Adder is also called as a Fast Adder.
Cascading Carry Look Ahead Adders
Cascading CLA Adders can make the addition of higher-order bits possible. To construct 8 bit, 16 bit and 32-bit parallel adders, we can cascade multiple 4-bit Carry Look Ahead Adders with the carry logic. A 16 bit CLA adder can be constructed by cascading four 4 bit adders with 2 extra gate delays, while a 32 bit CLA adder is formed when two 16 bit adders are cascaded to form one system.
Advantages of Carry Look Ahead Adders
- CLA Adders generate the carry-in for each full adder simultaneously, by using simplified equations involving Pi, Gi, and Cin.
- This system reduces the propagation delay. This is because the output carry at any stage is dependent only at the first Carry signal given at the input.
- It is the fastest adder when compared to other addition mechanisms.
Disadvantages of Carry Look Ahead Adders
- The CLA adder circuit gets more complicated as the number of variables increase.
- The circuit for a CLA is expensive as it involves more hardware.
- As the number of variables increases, the circuit implements more hardware. Thus, when the CLA is implemented as an IC, the area is bound to increase.
Uses of Carry Look Ahead Adders
Different bit-adder configurations of the fast-response CLA adders are manufactured on integrated circuitry nowadays. Apart from the circuits, there are also individual carry generator ICs that are manufactured, and we need to make the required connections to perform the quick addition function.
IC 74182
The IC 74182 is a look-ahead carry generator. This IC accepts up to four pairs of active low carry generate signals (G0’, G1’, G2’, G3’), four pairs of active low carry propagate signals (P0’, P1’, P2’, P3’) and active high carry input (C_{n}). This system then provides the active high carries (C_{n+x, }C_{n+y, }C_{n+z}). It also gives an active low Carry Generate (G’) and an active low Carry Propagate (P’) which may be used for other calculations.
Pin Diagram of the IC 74182 Look Ahead Carry Generator
The logic equations at the output of IC 74182 are :
C_{n+x = G0 + P0 . Cn}
C_{n+y }=G1 + P1 . G0 + P1 . P0 . Cn
C_{n+z }= G2 + P2 . G1 + P2 . P1 . G0
G’ = (G3 + P3 . G2 + P3 . P2 . G1 + P3 . P2 . P1 . G0 )’
P’ = (P3 . P2 . P1 . P0 )’
Since the IC supports variables such as P and G, we need the input variables A and B as well to calculate the P and G values. Hence, the complete 4-bit Carry Look Ahead Adder Circuit is as given below.
IC 74LS283
We have seen one type of IC previously, which has a circuitry revolving around the Carry Propagate, Carry generate and subsequent Carry values. We also have another system that consists of full adders assembled in the Carry Look Ahead Adder Circuitry. The most popular form is the IC 74LS83/74S283. It is a 4-bit parallel adder high-speed IC having four interconnected full adders with a CLA configuration. The 74LS83 and the 74LS283 are TTL circuits of Medium Scale Integration (MSI).
Given here is the functional symbol of the 74LS823 IC.
To make higher-order addition possible, cascade two or more parallel adder ICs.
Ripple Carry Adder vs. Carry Look Ahead Adder
Ripple Carry Adder |
Carry Look Ahead Adder |
The Carry bit passes through a long logic chain through the entire circuit. |
The Carry bit enters in the system only at the input. |
As the full adder blocks are dependent on their predecessor blocks’ carry value, the entire system works a little slow. |
Since the entire system depends on the first carry input, the computations are very quick, making it the fastest adder. |
It has a simple repetitive design. |
Has a slightly complicated design with many logic gates |
The system design is cheap to manufacture. |
The manufacturing process is expensive as compared to other systems. |
The ripple carry adder chips have a considerable size and area. |
The chip area increases, as there are many components in the circuit. |