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

It would take $6$ time units.

We know that:

$G_i = A_iB_i,$

$P_i = A_i\oplus B_i$ and 

$S_i = P_i\oplus C_i$

Also 

$C_1 = G_0 + P_0C_0$

$C_2 = G_1 + P_1G_0 + P_1P_0C_0$

$C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$

$C_4 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$

XOR can be implemented in 2 levels; level-1 ANDs and Level-2 OR. Hence it would take 2 time units to calculate $P_i$ and $S_i$

The 4-bit addition will be calculated in 3 stages

1. (2 time units) In 2 time units we can compute $G_i$ and $P_i$ in parallel. 2 time units for  $P_i$ since its an XOR operation and 1 time unit for $G_i$ since its an AND operation.

2. (2 time units) Once $G_i$ and $P_i$ are available, we can calculate the caries, $C_i$, in 2 time units.

Level-1 we compute all the conjunctions (AND). Example $P_3G_2, P_3P_2G_1, P_3P_2P_1G_0$ and $P_3P_2P_1P_0C_0$ which are required for $C_4$.

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.

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

Comments

Why are we not considering the delay for the not gate in the 3^rd stage when we compute Pi XOR Ci to get the sum? We need 3 levels of gates for the 3^rd stage, right? 1st level for not, 2^nd level for AND and the 3^rd level for OR. Now, since both Pi and Ci are not inputs, we have to consider the NOT gate delay for the 3^rd stage

---

Considering this, answer should be 3 + 2($\left \lceil log(n)) \right \rceil$)

here n is 4 base is also 4

answer should be 3+2(2) = 7 time units

---

pi = ai XOR bi, so pi XOR ci is nothing but (ai XOR bi XOR ci) & they also mention that complemented forms are already given , so you can implement this in two level only so here time required is 2 units.  

Answer 2

To get S_i  = A_i⊕B_i⊕C_i it requires two level AND-OR implementation

To generate C_i = function of (A₀,B₀,C₀, A₁,B₁,C₁, A_i-1,B_i-1, C_i-1) it also require two level AND-OR implementation.

so a total delay of 4 level, which is equivalent to 4 unit delay.

Comments

here we are not given xor gate to calculate Pi..if they would have given xor gate then

for first level - 1 time unit(to calculate all Pi AND gi)

2nd level -2 time unit(to compute all Ci as it contains 2 gate level)

3rd level - 1 time unit(to compute Si ) which adds upto 4

but

here we are not given xor gate,so we can make xor by AND &OR gates,Xor is also a 2 level AND -OR ,so

for first level - 2 time unit(to compute all Pi and Gi as Gi can be calculated in 1 time unit but Pi require 2 time units because xor need 2 level AND-0R logic)

for 2 nd level - 2 time unit to compute all Ci

for 3rd level -2 time unit(to compute all Si as Xor needs 2 level AND - OR logic) which adds upto 6 units

---

I think 4 is in the key.

http://www.ankurgupta.net/gate-solutions/gate2004cs/

---

This is how I understood. Instead of calculating generators and propagators, we are directly applying them as input in the carry generation stage to a 2level AND-OR circuit which has a delay of 2 units, and for generating sum we need a xor gate which can be realized using 2-level NAND gates. Hence, total of 4 units of delay.

Answer 3

answer is 4 time units.

Refer to http://faculty.kfupm.edu.sa/COE/abouh/Lesson3_3.pdf

Comments

in the above link they are using xor gate at fiest level and 3rd level which is not allow according to question.

---

answer in this link is 4 units because there XOR gate is given but here,XOR gtae is not given

Answer 4

->Going by the given data:
    1. Circuit is designed using AND, OR, NOT, NAND, NOR gates only.
    2. All the "inputs" are available in both complemented and un-complemented forms.
    3. Carry network has been implemented using two-level AND-OR logic.
    
->We know, Gi = AiBi, Pi = Ai XOR Bi and Si = Pi XOR 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 AND and Level-2 OR.
->The 4-bit addition will be calculated in 3 stages as follows:
    1. (2 time units) 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.
    2. (2 time units) Compute caries i.e. Ci. Since it is given that, "Assume that the carry network has been implemented using two-level AND-OR logic."
    3. (3 time units) Finally we compute the sum. Sum being an XOR operation, would require 2 time units, but complemented inputs for sum are not available. Hence we use one level for getting complemented inputs for sum & 2 levels for AND-OR logic of sum, which amounts to 3 time units.
->Hence the total is 2 + 2 + 3 = 7 time units. But 7 is not in options.
->Instead of going by the definition of Pi as Ai XOR Bi, If we use Pi as Ai + Bi, we can save 1 time unit required for AND-OR operation of XOR. The time now required for stage 1 is reduced to 1 time unit.
->The total time required would be 1 + 2 + 3 = 6 time units which is option B.