EVOLUTION OF ADDER CIRCUITS
Half Adder:
The half adder is an example of a simple, functional digital circuit built from two logic gates. The half adder adds to one-bit binary numbers (AB). The output is the sum of the two bits (S) and the carry (C). Note how the same two inputs are directed to two different gates. The inputs to the XOR gate are also the inputs to the AND gate. The input "wires" to the XOR gate are tied to the input wires of the AND gate; thus, when voltage is applied to the A input of the XOR gate, the A input to the AND gate receives the same voltage.
Full Adder:
The full-adder circuit adds three one-bit binary numbers (C A B) and outputs two one-bit binary numbers, a sum (S) and a carry (C1). The full-adder is usually a component in a cascade of adders, which add 8, 16, 32, etc. binary numbers. The carry input for the full-adder circuit is from the carry output from the circuit "above" itself in the cascade. The carry output from the full adder is fed to another full adder "below" itself in the cascade. If you look closely, you'll see the full adder is simply two half adders joined by an OR.
Half subtractor
The half-subtractor is a combinational circuit which is used to perform subtraction of two bits. It has two inputs, X (minuend) and Y (subtrahend) and two outputs D (difference) and B (borrow).
Full subtractor
As in the case of the addition using logic gates, a full subtractor is made by combining two half-subtractors and an additional OR-gate. A full subtractor has the borrow in capability (denoted as BORIN in the diagram below) and so allowscascading which results in the possibility of multi-bit subtraction. The circuit diagram for a full subtractor is given below.
Design of Ripple Carry Adders :
Arithmetic operations like addition, subtraction, multiplication, division are basic operations to be implemented in digital computers using basic gates likr AND, OR, NOR, NAND etc. Among all the arithmetic operations if we can implement addition then it is easy to perform multiplication (by repeated addition), subtraction (by negating one operand) or division (repeated subtraction).
Half Adders can be used to add two one bit binary numbers. It is also possible to create a logical circuit using multiple full adders to add N-bit binary numbers.Each full adder inputs a Cin, which is the Cout of the previous adder. This kind of adder is a Ripple Carry Adder, since each carry bit "ripples" to the next full adder. The first (and only the first) full adder may be replaced by a half adder.The block diagram of 4-bit Ripple Carry Adder is shown here below -
Design Issues :
The corresponding boolean expressions are given here to construct a ripple carry adder. In the half adder circuit the sum and carry bits are defined assum = A ⊕ B
carry = AB
In the full adder circuit the the Sum and Carry outpur is defined by inputs A, B and Carryin as
Sum=ABC + ABC + ABC + ABC
Carry=ABC + ABC + ABC + ABC
Having these we could design the circuit.But,we first check to see if there are any logically equivalent statements that would lead to a more structured equivalent circuit.
With a little algebraic manipulation,one can see that
Sum= ABC + ABC + ABC + ABC= (AB + AB) C + (AB + AB) C
= (A ⊕ B) C + (A ⊕ B) C
=A ⊕ B ⊕ C
Carry= ABC + ABC + ABC + ABC
= AB + (AB + AB) C
= AB + (A ⊕ B) C
part1
part2
Drawbacks of Ripple carry Adder
- The layout of ripple carry adder is simple, which allows for fast design time.
- However, the ripple carry adder is relatively slow, since each full adder must wait for the carry bit to be calculated from the previous full adder.
- The gate delay can easily be calculated by inspection of the full adder circuit.
- Each full adder requires three levels of logic.In a 32-bit [ripple carry] adder, there are 32 full adders, so the critical path (worst case) delay is 31 * 2(for carry propagation) + 3(for sum) = 65 gate delays.
***********************************************************************************
Design of Carry Lookahead Adders :
To reduce the computation time, there are faster ways to add two binary numbers by using carry lookahead adders. They work by creating two signals P and G known to be Carry Propagator and Carry Generator. The carry propagator is propagated to the next level whereas the carry generator is used to generate the output carry ,regardless of input carry. The block diagram of a 4-bit Carry Lookahead Adder is shown here below -
The number of gate levels for the carry propagation can be found from the circuit of full adder. The signal from input carry Cin to output carry Cout requires an AND gate and an OR gate, which constitutes two gate levels. So if there are four full adders in the parallel adder, the output carry C5 would have 2 X 4 = 8 gate levels from C1 to C5. For an n-bit parallel adder, there are 2n gate levels to propagate through.
Design Issues :
The corresponding boolean expressions are given here to construct a carry lookahead adder. In the carry-lookahead circuit we ned to generate the two signals carry propagator(P) and carry generator(G),
Pi = Ai ⊕ Bi
Gi = Ai · Bi
The output sum and carry can be expressed as
Sumi = Pi ⊕ Ci
Ci+1 = Gi + ( Pi · Ci)
Having these we could design the circuit. We can now write the Boolean function for the carry output of each stage and substitute for each Ci its value from the previous equations:
C1 = G0 + P0 · C0
C2 = G1 + P1 · C1 = G1 + P1 · G0 + P1 · P0 · C0
C3 = G2 + P2 · C2 = G2 P2 · G1 + P2 · P1 · G0 + P2 · P1 · P0 · C0
C4 = G3 + P3 · C3 = G3 P3 · G2 P3 · P2 · G1 + P3 · P2 · P1 · G0 + P3 · P2 · P1 · P0 · C0
CARRY SAVE ADDER
http://en.wikipedia.org/wiki/Carry-save_adder
KOGGE STONE ADDER
Introduction
In normal 8 bit Ripple carry Adder, as you know that every full adder takes time to calculate sum and carry. Every Full adder has to wait till previous full adder calculates the carry. Therefore to get 8 bit sum, it takes 8 full adders delay. Therefore the addition process is very slow.
Can you assume what happens, if all the full adders in 8 bit addition gets carry at the same time.....????????????????
Hmm...
You will get the 8 bit sum in only 1 full adder delay, because all adders are getting the carry at the same time.
The Kogge–Stone adder concept was developed by Peter M. Kogge and Harold S. Stone, which they published in 1973 in a seminal paper titled A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations.
8 Bit KOGGE STONE Adder Architecture
Fig: A 8 bit Kogge Stone Adder
COMMON TERMS IN KOGGE STONE ADDER
* G : Generate (Generates Carry)
* P : Propagate (Propagates Sum)
* SQUARE BOX : Initial stage , where we calculate G and P values
* BIG CIRCLE: Calculate G and P values stage by stage
* SMALL CIRCLE: Final Carrys(G)
* BUFFER: Final Sum
STEPS:
1) First Calculate all G and P 's in initial stage (for 8 bit calculate G and P 's from G0 to G7 and P0 to P7) using the formula shown in above figure for BLACK BOX.
Did you get a doubt Why we use that particular Formula in this stage............????????
Ex:-//Initial Stage Generate
assign g7 = a[7] & b[7];
assign g6 = a[6] & b[6];
assign g5 = a[5] & b[5];
assign g4 = a[4] & b[4];
assign g3 = a[3] & b[3];
assign g2 = a[2] & b[2];
assign g1 = a[1] & b[1];
assign g0 = a[0] & b[0];
//Initial stage propagate
assign p7 = a[7] ^ b[7];
assign p6 = a[6] ^ b[6];
assign p5 = a[5] ^ b[5];
assign p4 = a[4] ^ b[4];
assign p3 = a[3] ^ b[3];
assign p2 = a[2] ^ b[2];
assign p1 = a[1] ^ b[1];
assign p0 = a[0] ^ b[0];
2) Now we are in first stage of Kogge stone adder. (STAGE = 1)
From now there are 2 things
1) No of Block Skips (2 power n - 1)
2)No of Carry skip to take previous carry ( 2 power (n-1) - 1)
FIRST STAGE
-------------------
n = 1
*No of blocks skip(Big circle) = 2 power 1 - 1 = 1
Therefore if you observe the architecture of the kogge stone adder , in the first stage one Big circle is missed.
*No of carry skip(Big circle) = 2 power (1-1) - 1 = 0
i.e, you need to take the previous carry (G prev) from its immediate prev block, without skipping any block in between.
Now calculate all the G and P 's based on the formulas given for this Big Circle , for this complete stage.
Ex:
//First stage generate
assign g76 = g7 | (p7 & g6);
assign g65 = g6 | (p6 & g5);
assign g54 = g5 | (p5 & g4);
assign g43 = g4 | (p4 & g3);
assign g32 = g3 | (p3 & g2);
assign g21 = g2 | (p2 & g1);
assign g10 = g1 | (p1 & g0); (g10 is just a name of the g for that particular block)
//First stage propagate
assign p76 = p7 & p6;
assign p65 = p6 & p5;
assign p54 = p5 & p4;
assign p43 = p4 & p3;
assign p32 = p3 & p2;
assign p21 = p2 & p1;
assign p10 = p1 & p0;
Similarly......
For the next following stages the Block skipping and the carry skipping continues........
Exercise
Calculate the No of Block skipping and the Carry skipping in the following stages and compare it with the above architecture.
3) After Processing all the Big circles, now we should calculate the final carry's using the small circles.
G calculated at the small circles are the final carry's.
Note: Same carry skipping concept holds here based on the step we are in......
Ex:
assign c0 = g0 | (p0 & cin);
assign c1 = g10 | (p10 & cin);
assign c2 = g21 | (p21 & c0);
assign c3 = g321 | (p321 & cin);
assign c4 = g432 | (p432 & c0);
assign c5 = g543 | (p543 & c1);
assign c6 = g654 | (p654 & c2);
assign c7 = g7653 | (p7653 & cin);
4)Now all the carry's c0 to c7 are availabe at the same time at small circles.
5)Now calculate the sum's s0 to s7 using the buffers
Ex:
assign s[0] = p0 ^ cin;
assign s[1] = p1 ^ c0;
assign s[2] = p2 ^ c1;
assign s[3] = p3 ^ c2;
assign s[4] = p4 ^ c3;
assign s[5] = p5 ^ c4;
assign s[6] = p6 ^ c5;
assign s[7] = p7 ^ c6;
assign cout = c7;
Since all the carry's are available at the same time , kogge stone adder is Very Fast. It is Fastest Ever adder.
Click here to view the complete code
Fig: 16 bit Kogge stone adder
Can you observe that in all the generate and propagate equation calculations, we used and, or, xor operators. When the code is synthesized, each operator get translated into dedicated hardware gates.
Therefore for addition of bits greater than 8 bit, we require large number of gates(hardware), this increases the area occupied by the area on the chip and there by more power consumption.
These disadvantages of Kogge Stone Adder drives us to go for Sparse kogge stone adder.
Sparse Kogge Stone Adder.
Fig : 16 bit Sparse kogge stone adder
- We have 4 4-bit Ripple Carry Adders to perform 16 bit additon.
- If we cascade all the 4 Ripple Carry Adders it becomes 16 bit Ripple Carry Adder.
- The disadvantage with Such architecture is to get sum, it takes 16 Full adder delays.
- What if i provide c3 for RC1, c7 for RC2 and c11 for RC3 at the same time..........?????
- All the 4 bit Ripple carry adders are getting carry inputs at the same time.Therefore we get the 16 bit sum in only 4 Full adder delay.
- df
- df
- Now we need only c3, c7 and c11, so now go back to kogge stone carry tree structure and eliminate all the hardware that are not required to calculate c3, c7 and c11.
- After doing that you will be able to get the Sparse kogge stone carry tree structure as shown above.
- The thing that you can observe that , the number of gates required has reduced drastically.
Wow........
Now we are able to acheive area optimization for fastest additon and thereby power consumption in compared to kogge stone adder.
FROM THIS PAGE WILL BE ABLE TO DESIGN
KOGGE STONE ADDER (FOR UPTO 8 BITS) &
SPARSE KOGGE STONE ADDER(FOR MORE THAN 8 BITS.)
***********************************************************************************
Fig: 32 bit Sparse Kogge Stone Adder
QUESTIONS
-----------------
Q]What is a Ripple Carry Adder?
Q]What is a carry Save Adder?
Q]Disadvantages of Ripple carry adder?
Q]What is Kogge Stone adder?
Q]What is the need to go for Sparse Kogge Stone Adder?
Q] Construction of 8 bit Kogge stone adder?
Q]Applications of Kogge Stone Adder and Sparse Kogge Stone Adder
Can U Please Provide me Verilog code for Sparse Kogge Stone Adder
ReplyDeleteHey Sure Pawan. Can you Please give your Mail ID.
DeleteThanks Sameer :)
ReplyDelete