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

This is how it should look like, please let me know if there's anything wrong with the diagram.

---

Lets Break the question into three steps 

Observing   we need to calculate two things  that is sum and carry → Main Motive 

and  the respective sum of any bits  is dependent on the carry  let’s say we want to calculate 

sum s1 =(a1 xor b1 xor c1)  what it will be basically calculating is a1+b1+c1

now  for calculation of sum it is dependent on carry so we will calculate carry first before sum

Equations for generating carry

C1=G0+P0C0C1=G0+P0C0

C2=G1+P1G0+P1P0C0C2=G1+P1G0+P1P0C0

C3=G2+P2G1+P2P1G0+P2P1P0C0C3=G2+P2G1+P2P1G0+P2P1P0C0

C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0

observe these equations here the carry is generated and we can clearly observe carry is dependent on  G and P  so for to calculate carry we need to calculate G and P first 

now lets say G0 then G0 = A0 and b0

and P0 =(A0 xor B0)  

now first we need to calculate G and P  ,Using this G and P we will generate carry and finally by using carry and p we will generate the sum

Level 1 operations 

first generating G and P   
G can be generated directly using an AND operation that will take only --- 1 TIME UNIT
 

P needs xor of A and B and we don't have Xor gate directly so we will implement xor as two level operations of AND & OR gate  ,here we even have the complement of the respective variables   

it takes – 2 TIME UNITS

Maximum of this level is 2 units  so we will consider 2 units for this level

Level 2 operations 

Level 2 operations includes calculating carry here  we can observe all these are AND & OR operations   AND takes 1 time unit and OR takes 1 time unit 

C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0

this level as on a whole takes 2 time units 

Level 3

Level 3 operations takes 3 time units for calculating the sum as it is XOR of P and C  but here the complements are  not present for p and c as we need to calculate that takes 1 level and after that we apply xor that is AND-OR which will take 3 time units

 2nd way when we take  assume that complement of c and p is also available as it is given that all the complements of i/p's are also available then it will take  only 2 units 

Total 6 units/7 units both should be write depending on whether C and P  's complements are available or not

---

For those wondering why the last stage for computing sum $(S_i = P_i\oplus C_i = \overline{P_i}\cdot C_i + P_i\cdot \overline{C_i})$ only takes $2$ units when the complements of $P_i, C_i$ are not available to us and so think that this $XOR$ operation should take $3$ units of time:

Note that we have a $NAND$ gate available to us to design this circuit and that $XOR$ operation can be implemented using $\text{2-level NAND-OR-AND}$ circuit as follows:

$S_i = P_i\oplus C_i = (\overline{P_i} + \overline{C_i})(P_i + C_i) = (P_i \uparrow C_i)( P_i + C_i)$

Answer 1

The answer varies with the way we implement the gates. IF anyone has the official GATE key they must share it.
Answer is (b) 6 time units if we necessarily implement the Gi & Pi terms (which is no where mentioned in the question as mandatory).
Answer is (a) 4 time units if we write the carry terms directly and without separately implementing Gi & Pi terms

Heres the explanation of answer (a). Credits : GeeksForGeeks https://www.geeksforgeeks.org/gate-gate-cs-2004-question-62/

Explanation: 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.

Answer 2

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 3

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 4

In addition to the Best answer for this question , i am adding diagramatical representation for Ripple carry Adder for ease of understanding.

We know that:

Gi=AiBi,

Pi=Ai⊕Bi and 

Si=Pi⊕Ci

Also 

C1=G0+P0C0

C2=G1+P1G0+P1P0C0

C3=G2+P2G1+P2P1G0+P2P1P0C0

C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0

XOR can be implemented in 2 levels; level-1 ANDs and Level-2 OR.

Fig 1:

Hence it would take 2 time units to calculate Pi and Si

The 4-bit addition will be calculated in 3 stages:

Fig 2:

1. (2 time units) In 2 time units we can compute Gi and Pi in parallel. 2 time units for  Pi since its an XOR operation and 1 time unit for Gi since its an AND operation.(Refer Fig 2)

2. (2 time units) Once Gi and Pi are available, we can calculate the caries, Ci, in 2 time units.(Refer Fig 3)

Fig 3:

Level-1 we compute all the conjunctions (AND). Example P3G2,P3P2G1,P3P2P1G0P3G2,P3P2G1,P3P2P1G0 and P3P2P1P0C0P3P2P1P0C0 which are required for C4.

Level-2 we get the carries by computing the disjunction (OR).

3. (2 time units) Finally we compute the Sum in 2 time units, as its an XOR operation.(Refer Fig 2)

Hence, the total  propagation delay is 2 + 2 + 2 = 6 time units.

Comments

Best answer . Thanks :)