Design of Fast Adder - Prof. Mahesh PDF

Preview

Summary

Prof. Mahesh...

Description

Sub Subject ject ject:: Computer Organization

Ari Arithm thm thmetic etic etic:: Design of Fast Adder

3.1.5 DES DESIGN IGN OF FA FAST ST AD ADDE DE DER R If an n-bit ripple-carry adder is used in the addition/subtraction circuit of Figure 9.3, it may have too much delay in developing its outputs, s0 through sn−1 and Cn. An n-bit adder Delay:  Cn−1 is available in 2(n−1) gate delays and Sn−1 is correct one XOR gate delay later.  The final carry-out, Cn, is available after 2n gate delays.  Using the implementation Cn ⊕ Cn−1 for overflow, this indicator is available after 2n + 2 gate delays. Two approaches can be taken to reduce delay in adders. To use 1. The fastest possible electronic technology. 2. A logic gate network called a carry-look-ahead network. CAR CARRY RY LO LOOK OK AHE AHEAD AD AD ADD DER (CL (CLA) A) In this, a technique is defined which speeds up the generation of Carry. We have Si = ( Ai XOR Bi XOR Ci ) ---------------------------------------------------------------------------------(1) Ci+1 = (Ai.Bi) +( AiCi) + (BiCi) ------------------------------------------------------------------------- (2) Ci+1 = (Ai.Bi) + Ci (Ai + Bi) ----------------------------------------------------------------------------- (3) Equation (3) can be expresses as Ci+1 = Gi + Ci.Pi ---------------------------------------------------------------------------------------------(4) Where Gi is generate term Gi = ( Ai.Bi ) & Pi is Propagate term pi = ( Ai + Bi ) This indicates that, For ith stage  If generate term Gi=1 ; Ci+ Ci+1 1 ==1 1 – This is independent of the Carry input Ci ; This is when Ai=Bi=1  If Pi= Pi=1 1 ; It means that an Ci will propagate to Ci+1 when either Ai is 1 or Bi is 1. It means (Ai XOR Bi) =1 . Therefore Pi is also defined as (Ai XOR Bi ) The truth table with generate and propagate term can be defined as shown in the following table From the table also we can analyze the generate and propagate conditions Tab Table le 3. 3.1: 1: Truth table of Full Adder with generator and Propagate terms

Sub Subject ject ject:: Computer Organization

Arithm Arithm thmetic etic etic:: Design of Fast Adder

All Gi and Pi functions can be formed independently and in parallel in one logic-gate delay after the A and B operands are applied to the inputs of an n-bit adder. By Expanding Ci in terms of (i – 1) subscripted variables and substituting into the Ci+1 expression, we obtain CI+1 = Gi + PiGi-1 + PiPi-1Gi-2+…………………..+ PiPi-1Pi-2Pi-3……. PoCo --(5) By substituting i=1,2,3 and 4 we get C1,C2,C3 and C4 as below i=0 C1 = g0 + C0.P0 i=1 C2 = g1 + C1.P1 ------------------------------- (6) i=2 C3 = g2 + C2.P2 i=3 C4 = g3 + C3.P3 Now by Substituting Ci in Ci+1 , the Carry terms of equation (2) becomes i=0 C1 = g0 + C0.P0 i=1 C2 = g1 + P1 (g0 + C0.P0) = g1+g0.P1+CoP0P1 i=2 C3 = g2 + P2(g1+g0.P1+CoP0P1) = g2 + g1P2+g0.P1P2+CoP0P1P2 -----------(7) i=3 C4 = g3 + P3(g2 + g1P2+g0.P1P2+CoP0P1P2 ) = G3+ P3 G2 + P3 P2 G1 + P3 P2 P1G0 +P3 P2 P1 P0Co Equation (7) clearly indicates that C1,C2,C3 and C4 does not depend on previous carry out. All these Carry terms depend only on Gi, Pi and C0 and All these can be realized using 3 level circuits. Lev Level1: el1: Logic circuit for Gi and Pi, which are basically AND gate and XOR gate ( Level1 of Sum Si) Lev Level2: el2: AND gates to generate the product terms in respective Carry Lev Level3: el3: OR gate to add the respective product terms to get Ci+1 Therefore by using these Gi and Pi terms the C1, C2, C3 and C4 can be generated simulteniously using a 3 level circuit. The block diagram of a 4 bit Carry Look Ahed Adder is as shown in Figure 3.9

Figur Figure e 3.9 3.9:: Four bit Carry Look Ahead Adder Del Delay: ay: In a 4 bit CLA , C1-C4 are available with a 3 gate delay and S3 with addition XOR gate delay

Sub Subject ject ject:: Computer Organization

Arithm Arithm thmetic etic etic:: Design of Fast Adder

Can we exp expan an and d the CL CLA A for lon longe ge gerr op ope eran rands ds in th the e sam same e mann anner? er? If we extend the CLA for longer operands, we run into Fan in constraints. If we lo look ok int into o Ci+ Ci+1 1–W We e see tha thatt llast ast AND & OR re requ qu quire ire a ffan an in of (i+ (i+2) 2) in ggen en ener er eratin atin atingg C Ci+1 i+1 For i=3, Ci+1= C4, we require a Fan in of (i+2)=(3+2) =5 and practically Fan in equal to 5 is the limit for gates. Therefore CLA logic of Fast addition cannot be extended directly for longer operand size. However cascading of 4 bit adders can be done to build longer adders . 3.1. DESI CLA Add 3.1.6 6 DESI ESIGN GN of LON LONGE GE GER R OPE OPERA RA RAND ND SIZE CLA Adder er erss a) C O 4 bi CL T B L A CASC ASC ASCAD AD ADING ING OFF bitt CLA A TO O BUIL UIL UILD D LON ON ONGE GE GER R ADD DD DDERS ERS Cascading of 4 bit CLA is done using the approach used in kn bit RCA in order to build longer size adder. Let us consider 32 bit adder designing using cascading of 8, 4 bit CLA adders as shown below. There are 8 blocks as CLA_Adder_0 to CLA_Adder_0 cascaded as shown, the C4 goes as Cin to CLA_Adder_1, C8 output of as CLA_Adder_1 goes as Cin to CLA_Adder_2 so on Finally C28 output of CLA_Adder_6 goes as Cin to CLA_Adder_7.

Figur Figure e 33.10 .10 .10:: 32 bit Cascaded adder using 4 bit CLA blocks Now from the cascading shown it is clear that Carry is rippling from block to block leading to propagation delay. The delay in generating S31, S30, S29, S28 and C32 in higher order 4 bit adder (CLA_Adder_7) in the cascade are calculated as follows • C4 by CLA_Adder_0 is available with 3 gate delay after input Ai, Bi and C0 are applied 32 bit adders. • In all the adder blocks, Level1 of producing Gi and Pi is done simultaneously after input Ai, Bi and C0 are applied 32 bit adders. Therefore successive adders form CLA_Adder_1 to 7 take only 2 gate delays each to make C8,C12,C16…..C28,C32 to be available. Therefore C8 is available at the output of CLA_Adder_1 after further 2 gate delay, C12 is available after a further 2 gate delay so on • Therefor C28 is available after a total of (6x2 + 3) =15 gates C32 and ALL the carries inside CLA_ADDER_7 are available after further 2 gate delay. Therefore C32 is available after (15+2) =17 gate delay. • S31, S30, S29, S28 take additional gate delay, Therefore the Total del delay ay = 15+ 15+2+1 2+1 =18 gate del delay ay tto op prod rod roduce uce Su Sum m ter terms ms ms..

Sub Subject ject ject:: Computer Organization

Arithm Arithm thmetic etic etic:: Design of Fast Adder

In the 32-bit adder just discussed, the carries c4, c8, c12 . . . ripple through the 4-bit adder blocks with two gate delays per block, analogous to the way that individual carries ripple through each bit stage in a ripple-carry adder. An 32-bit cascaded 4 bit RCA Delay:  Cn−1 is available in 2(32−1) gate delays = 62 gate delay and Sn−1 is correct one XOR gate delay later, Therefore 63 gate delay.  The final carry-out, Cn, is available after 2(32)=64 gate delays. From this it is clear that a delay of 32 bit adder obtained using 4 bit CLA is better than 32 bit adder designed using 4 bit RCA. An Improved cascade structure can lead to further reduction in adder delay. b) HIGH LE LEVE VE VELL G GEN EN ENER ER ERAT AT ATE E AN AND D PPRP RP RPAG AG AGATE ATE FFUN UN UNCTI CTI CTION ON The Carry-Look-Ahead 4-bit adder can also be used in a higher-level circuit by making each CLA logic to produce a new group generate (GIk ) and group propagate (PIk )signal to a higher-level CLA logic. K=1,2,….. for block 1,2,… n/4 CLA blocks. Now for block 0 k=0 and the block generate and propagate signal is expressed as shown below in equation (8) and (9) and the block diagram for 4 bit CLA with block generate and propagate is as shown in Figure 3.11 PI0 = P3P2P1P0 ---------------------------------------------------------------------------------------------------------------------------------------------------------(8) (8) I G 0 = G3 + P3G2 + P3P2G1 + P3P2P1G0 ----------------------------------------------------------------- (9) They can then be used to create a carry-out for that particular 4-bit group, It can be seen that C4 can be expressed in terms of block generate GI0 and propagate PI0. C4

= G3+ P3 G2 + P3 P2 G1 + P3 P2 P1G0 +P P3 P2 P1 P0Co I I = G 0 + P 0 Co ----------------------------------------------------------------------------------------------------------------------------------(10) -(10)

This clearly indicates that C4 output of Block0 can be produced by using block generate GI0 and propagate PI0.

Figur Figures es 3.1 3.11 1: 4 bit CLA with additional output PI0 and GI0

Sub Subject ject ject:: Computer Organization

Arithm Arithm thmetic etic etic:: Design of Fast Adder

Symbolically the 4 bit CLA adder is as shown in Figure 3.12 with additional Group Propagate and generate signal

Figur Figure e 3.12 3.12:: Block Level representation of 4 bit CLA with additional output PI0 and GI0 In the ith stage - the Gi and Pi functions produced indicate whether ith stage generates or propagates a carry. The second-level GIk and PI k functions determine whether block k generates or propagates a carry. Now, A 32-bit adder using 4 bit CLA with block generate and propagate is as shown below.

Figur Figure e 3.12 3.12:: A 16-bit carry-look-ahead adder built from 4-bit adders With these new functions available, there is no need to wait for carries to ripple through the 4bit blocks. Carry C16 is formed by one of the carry-look ahead circuits in Figure 3.12 as C16 = GI3 + PI3 GI2 + PI3 PI2 GI1+ PI3PI2PI1GI0+PI3PI2PI1PI0C0 ---------------------------------- (11 (11))

Sub Subject ject ject:: Computer Organization

Arithm Arithm thmetic etic etic:: Design of Fast Adder

It can be seen that equation (11) is similar to equation (7), therefore expressions for C16, C12, C8, and C4, will be identical in form to the expressions for C4, C3, C2, and C1 of equation (7), respectively, implemented in the carry-look-ahead circuits. Only the variable names are different. As a result the 16 bit CLA block diagram shown in Figure 3.12 looks similar to 4 bit CLA of Figure 3.10. However, the carries C4, C8, C12, and C16, generated internally by the 4-bit adder blocks, are not as they are generated by the higher-level carry-look-ahead circuits [1]. Now let us check the delay aspect of 16 bit adder designed using 4 bit CLA blocks with block generate and propagate signals. Let us look into C4 delay using block generate and propagate Signal as shown below. It clearly indicates that it takes 5 gate delay.

Therefore , Each 4 bit CLA block takes 3 gate delay to produce group generate and Propagate Signals GIk and PIk and Carry Look Ahead logic takes additional 2 gate delay to generate C4,C8,C12 and C16 using block GIk and PIk. Therefore, all carries produced by the carry-lookahead circuits are available 5 gate delays after A,B , and C0 are applied as inputs[1]. But the carry C15 is generated internally inside the high-order 4-bit CLA adder block3, this takes two gate delays after C12 goes as input, Therefore C15 is available after 7 gate delay followed by S15 in one further gate delay. Therefore, S15 is available after (5+2+1)=8 gate delays. Therefore using the configuration the delay in producing C16 and S15 is 5 and 8 gate delays respectively. Comparison of delay of 16 bit adder designed using RCA, Cascaded 4 bit CLA and Using block level generate and propagate signal are Parameter C16 S15

RCA 2n=2x16=32 gate delay 2(n-1)+1=31 gate delay

Cascaded 4 bit CLA (3x2)+3 = 9 gate delay 9+1 = 10 gate delay

High Level Gi and Pi 5 gate delay 8 gate delay...