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

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

But (A bar ) and (B bar) have NOT gate,  so which will have one more gate so the total gate is 3

 

---

thanks

---

question has specified that compelements are available .

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

first we have to wait for A ⊕ B to be calculated then we can use the look ahead carry (which takes 2 units)

 implement XOR we require 2 level and-or implementation so 2 unit time there and 2 unit for A ⊕ B ⊕ C

so 2+2+2=6

Wont we have to wait for A ⊕ B to use it in look ahead??

---

how  A_i⊕B_i⊕C_i   will require two gate delays??? 

---

express above expression in soop formate which takes 2 level AND - OR circuit.and 2 unit gate delay also .

---

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

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 :)

---

Why we adding sum compute time in carry propagation delay?

Definition of carry propagation delay is the time taken to produce all output carry bit.

And look ahead carry added calculate them at same time.

While Look ahead carry adder compute all the Carrie's in the after Pi and Gi is calculated.

Answer 4

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 5

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 6

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