GATE CSE 2004 | Question: 62

Question

A 4-bit carry look ahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using two-level AND-OR logic.

• A. 4 time units
• B. 6 time units
• C. 10 time units
• D. 12 time units

Comments

thanks for diagram

---

implemented using two-level AND-OR logic ??

What is the meaning of this line.

---

In 3rd step while Xor Pi with Ci. Ci and Pi is not in complemented form. I thing XOR operation should take 3 unit time. Than answer should 7 instead of 6

Answer 1

The answer is A) 4-time units.

Because even though we have Pi and Gi terms in carry,  these can be simplified into inputs so don't need to wait for 

'em to calculate the carry. For example -

C1 = G0 + P0C0

C1=A0B0 + (A0'B0+A0B0')C0

C1=A0B0 + A0'B0C0 + A0B0'C0

Similarly, we can write C2, C3, and C4 in terms of inputs so just 2-level AND-OR is enough to generate all the carries, therefore, 2-time units here.

Now for the sum, we have to wait for the carries and then sum will take 2-time units, therefore, total time units = 2+2 =4.

 

Answer 2

Let the input carry to the first adder be denoted by C1.

Now, to calculate C2 we need = P1C1 + G1 = 4 gate levels (P1 takes 2 gate levels)
to calculate S1 we need = P1 XOR C1 = 2 + 2 = 4 gate levels.

Since it is a Carry look ahead adder, computing C3 , S2 doesn’t have to wait for carry output C2 from the previous adder as C2, C3 etc will get computed at the same time.

Now,

S2 is computed as = P2 XOR C2 = P2.C2′ + P2′.C2
= P2 (P1.C1 + G1 )’ + P2′ (P1.C1 + G1) [ notice that we are not using the output carry from first adder C2 anywhere here ]
which can be implemented using 4 gate levels.

also C3 can be computed by using 4 gate levels and so on…
so the overall propagation delay is 4 gate level as the outputs at Si , Ci are available at the respective full adders after 4 gate levels = 4 time units.

To understand it with more clarity draw the carry look ahead adder circuit and then check it.

Comments

Dear Seniors,

how it is getting 4 or 6 or 8.

in carry lookahead generator only  3 AND delay and 3 OR delay required. as no of input is 4.

for input to carry generator , we need Pi and Gi. as complemented output is available, for XOR gate it should take 2 delay
( one for AND and one for OR) so 2 gate delays reuired here.

now after carry generated, for sum, again XOR is required. which again take 2  delay if complemented Pi and Ci available.
but only inputs are available in both complemented and non complemented form, so we should use one NOT gate for complement Pi and Ci.
 Thus, 3 gate delay required here.

In summary,

2 + ( 3 +3)  + 3 = 11

if we assume Pi and Ci isavailable in complemented form also thb it should take 10 Gate delays.


please tell me where i am wrong.


@Arjun Sir...please clear my doubt.


Thanks

Answer 3

First step: for all Gi and Pi , need to implement xor as input are available in both normal and complement form,

               so it can be implement with one and level then or level. so 2 level delay.

Step 2: Carry Network delay its 2 gate levels as given in question.

 

Step3 : Now to generate sum , we again need to do xor operation that can be done in 2 gate level[Using NAND & OR in first level then AND in Second level as X XOR Y = (X'+Y').(X+Y)]

 

So, Total 6 gate level delay.

Answer 4

Hope, this clears everyone's doubt.

Answer 5

Carry lookahead adder can be thought to be made in 3 levels as below

Level 1 : P & G Generator

$Gi=Ai.Bi$

$Pi=Ai⊕Bi$

$Gi$ uses AND gate which takes one unit time

$Pi$ uses EX-OR which can be implemented by AND-OR in two levels => it will take 2 unit time 

$Gi$ and $Pi$ work in parallel so they will take time = 2 units 

Level 2 : Carry Generator

$C1=G0+P0C0$

$C2=G1+P1G0+P1P0C0$

$C3=G2+P2G1+P2P1G0+P2P1P0C0$

$C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0$

This uses two levels of AND OR (see fig) so time =  2 units

Level 3 : Sum Generator

 

$Si=Pi⊕Ci$

it uses  EX-OR gate which can be implemented by AND OR so time= 2 units

Total time = 2 + 2 + 2 = 6 Units  

Option (B)

Answer 6

Option B : 6 units. 

Please note: i have considered one timeunit = 1 delta.