GATE CSE 2015 | Set 2 | Question: 48

Question

A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is $1.2$ microseconds. A $4$-bit-ripple-carry binary adder is implemented by using four full adders. The total propagation time of this $4$-bit binary adder in microseconds is ______.

Comments

y not ans 33.6 *10^3 microsecond??????????????

y The first carry and sum will be available after 4.8 us   & how???????????

---

33.6??

---

here mention xor is twice of and/or so and/or is 1.2ms so xor is 2.4 ms & 1 hald adder is 1xor+1and so= 3.6

& a full adder is implemented wt 2 half adder +1 or gate = 2*3.6+1.2= 8.4

4full adder =4*8.4= 33.6

---

okay :) If everything is done one after the other or in a serial way. But, operations can be done in parallel- you can see the figure given below. As long as input to a gate is not dependent on the output from another gate, those two can be operated in parallel. 

---

Should not this be like since in the question we are given that a full adder is here implemented as 2 Half adders and an OR gate..

And we know that if we follow this constraint of circuitry then we use cascading half adders and then an OR gate..So delay should be added for each of the half adders and one OR gate for every full adder implementation.

So delay of a full adder should be : 2.4 * 2[For 2 half adders] + 1.2 [for OR gate]  

                                           =      6 ms

So delay of 4 bit ripple carry adder = 4 * 6 ms

                                                   =  24 ms

@Arjun Sir , please check this approach..

---

@Habibkhan see its not 6ms 

---

Thank u..Got it..

---

what will be the difference if i use ripple carry adder over Carry look ahead adder here?? what will be the chenge in aswer??

---

@ S Ram,

The question itself says,

"A 4-bit-ripple-carry binary adder is implemented by using four full adders"

I think it should be clear now.

---

Delay of carry look ahead adder:

https://gateoverflow.in/35865/total-propagation-delay-in-carry-look-ahead-adderin-a-4-b

---

In ripple carry adder, a full adder becomes active only when its carry in is made available by its adjacent less significant full adder.

so 19.2 is the right answer.

---

This link might be helpful : https://en.wikibooks.org/wiki/Digital_Circuits/Adders

---

@Lokesh .

your diagram is best .

---

In Ripple carry adder, a stage doesn’t wait for the “full output” of previous stage. It only waits for the previous stage’s carry to reach to itself. Now, carry generated by our current stage can be written in 2 ways:-           

  1)Carry generated= $xy + $ $(x$$\bigoplus$$y)C_{in}$                2)Carry generated=  $xy+yC_{in} +xC_{in}$       where $C_{in}$ is carry received by our current stage

Using 1st way, delay in carry generation would be 4.8$us$  and  by using 2nd way, delay in carry generation would be 2.4$us$. So, answer should be according to 2.4$us$ delay(better than 4.8$us$ delay).

So, total delay will be $(4-1)*2.4 + 4.8$ = $12us$

---

what will be the answer if it is carry look ahead adder?

---

@swami_9

I think it will be $4.8\mu s$ only, as there is no need to wait for the carry from the prev. adder.

---

someone please explain this thoroughly

---

Simple yet hard

---

Answer will be 12 microsecond only. If we have full adder implemented through half adder and XOR there's no pointing of starting next sum calculation from 0. The Carry1 from very first full adder will be avlbl in 4.8th microsecond, and till then one xor will already be computed and be in waiting for carry1. The further process will go on.

 

Case 2 : If we are not given that the full adder is implemented by Half Adder and OR, we would get 19.2 microsecond.

---

here we implement our ripple carry adder by using FA and not directly by basic gates like and,or
so keep in that mind
first make Full adder and find carry and sum
and then use our formula
Tp=n-1(Tcarry) +Max(Tsum,Tcarry)

if asked to implement using and,or xor use
Tp=n-1(Tand+ Tor) +Max(Tsum,Tcarry)
its a crux
but better to understand HA,FA,RIPPLE CARRY ADDER MECHANISM
because they ask variations in ISRO,and other exams lke barc

---

@Pranavpurkar, i think for the carry look ahead adder , the total propagation delay would be $7.2$$\mu s$ 

@ybairwa786 can you confrim this ?

---

One thing to understand before solving this question is that  :- In Ripple carry adder, a stage doesn’t wait for the “full output” of previous stage. It only waits for the previous stage’s carry to reach to itself. 

Delay of ExOR  = 2*(delay of AND/OR)

                          = 2*1.2 = 2.4ms

now, Full Adder is implemented using 2 HA(Half  Adder) and a OR gate

so,

delay of Sum (S) =  2* delay of ExOR .......(for sum o/p  in FA it uses two ExOR gates)                                   

                            = 4.8 ms

 delay of Carry (C) = 1Exor +1 AND + 1OR  ......(this is the critical path for the carry o/p in FA)

                              = 4.8ms

now, Ripple carry adder is implemented using 4 FA

At t= 4.8ms, both S0 and C1 are valid 

to get S1,C1 must be valid....(previos stage carry is needed to compute S)

       Delay of S1 = 4.8 + 2.4           (as S1 is dependent on C1..so Delay of C1 (4.8) + After                                                                                                   C1, one additional ExOR is needed for S1 (2.4))

                          = 7.2ms

 therefore S1 is valid at 7.2ms

now, C2 is valid after 7.2 ms becuz, C2 will need only AND and OR gate to be computed

          4.8+ 2.4  

therefore C2 is valid after 7.2ms

now,

To find S2 we'll be needing C2,  so,

     delay of S2 = Delay of C2 + delay of ExOR 

                        = 7.2+2.4

                        = 9.6ms

therefore S2 is vallid after 9.6ms

delay of C3 = delaay of C2 + Delay of AND and OR gate 

                   = 7.2+2.4

                   = 9.6ms

therefore C3 is valid after 9.6ms

 

similarly to find S3 we'll be needing C3; 

     S3 = delay of C3 + delay of ExOR

          = 9.6+2.4

          = 12ms

therefore S3 is valid after 12ms

 

final answer 12ms

 

---

@Arjun Sir

 

As it is mentioned in the question that a half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate but there are two possible implementations for FA with two HA's and one OR gate

Implementation 1 : 

In this case Delay of Sum(s) = 2 HA'S = 2 EXOR gates = 2*2.4 = 4.8 μs

                   Delay of carry(k) = 2 HA'S + 1 OR gate = 4.8+1.2 = 6.0 μs

The total delay of the 4 bit binary adder = 24 μs (if we assume all the inputs are not available intially)

The total delay of the 4 bit binary adder = 16.8 μs (if we assume all the inputs are available intially)

Implementation 2 : 

In this case Delay of Sum(s) = 2 EXOR gates = 2*2.4 = 4.8 μs

                   Delay of carry(k) = 1 EXOR gate + 1 AND gate + 1 OR gate = 2.4 + 1.2 + 1.2 = 4.8 μs

The total delay of the 4 bit binary adder = 19.2 μs (if we assume all the inputs are not available intially)

The total delay of the 4 bit binary adder = 12 μs (if we assume all the inputs are available intially)

Now what i'm asking is there are 4 different answers and each of them having proof what we have to conclude from this ?

I need your conclusion @Arjun sir.

Answer 1

$S1$ should wait for $C1$ to be ready. Delay for generating $C$ is $1$ EXOR $+ 1$ AND $+ 1$ OR $= 2.4 + 1.2 + 1.2 = 4.8\;\mu s$

Delay for sum is XOR + XOR $= 2.4 + 2.4 = 4.8\;\mu s$

But for the second adder, there the first EXOR can be done even before waiting for the previous output. So, we can get the sum in Another $2.4\;\mu s$ and carry in another $2.4\;\mu s$. In this way, $4\text{-bit}$ sum can be obtained after

$4.8\;\mu s + 3 \ast 2.4 \;\mu s = 12\; \mu s.$

But the question says we use ripple-carry adder. So, each adder must wait for the full output from the previous adder. This would make the total delay $= 4 \ast 4.8 = 19.2\;\mu s$ and this is the key given by GATE, so obviously they meant this. 

Comments

 Isn't the answer should be 12 micro sec here?  Rippling effect doesn't mean whole of the adder will become active after receiving the input from the previous adder,  as long as the second adder is dependent on the previous adder it is still considered to be rippling effect.  Correct me sir, maybe nobody challenged this question in 2015 and this is why gate authorities didn't change it to 12 micro sec that year.   @GO Classes 

---

@Ayush Upadhyaya Bhai crazyy you are. Learnt so much from your answers.

---

"But the question says we use ripple-carry adder. So, each adder must wait for the full output from the previous adder." is this correct statement? isn't ripple carry adder is another parallel adder only?

Answer 2

Ans is 12 ns
 

It took me a while but here's how it is :

The first carry and sum will be available after 4.8 ns. This should be straight forward.

However, for the subsequent stages, you need to keep in mind that the output of half adders is already there at 2.4 ns. So in a sense, it is already computed. The remaining half adder for each full adder is just waiting for the previous carry, which when available from the previous stage can be processed in 2.4 ns. So each next stage will take only 2.4 ns each.

The catch here is that half of the output in each next stage is already computed, only half needs to be processed.

Comments

https://electronics.stackexchange.com/questions/153650/delay-in-4-bit-ripple-carry-adder
I see what you did there :p
Oh and btw, your very first solution is the correct one, It's according to Gate's official answer key... 

---

"The remaining half adder for each full adder is just waiting for the previous carry, which when available from the previous stage can be processed in 2.4 ns. So each next stage will take only 2.4 ns each."

yes..but the previous carry will be available after another 2.4ns and then second XOR will happen which will take another 2.4ns. In total it will take 4.8ns
 

Answer 3

Seeing the circuit in this way is easy way to get to the answer.

Comments

This is wrong

Answer 4

 

This should be the right procedure to get the right answer for this question.

Simply putting the formula here won't work.

Therefore, the answer comes out to be 12 microseconds.

Comments

Finally is this the right answer?

---

Yes! This is the perfectly right answer.

---

Thanks bhaiya Really amazing answer .

---

Only right answer here, i personally feel.

Answer 5

Circuit diagram for the problem can be made as:

delay for XOR gate = 2*1.2 = 2.4 μs.

delay for AND/OR gate = 1.2 μs.

First XOR gate takes 2.4 μs. and meanwhile XY can be calculated in parallel. Similarly, Second XOR gate takes another 2.4 μs and in the meanwhile output of AND(1.2 μs) and OR(1.2 μs) can be calculated (Since, the output of first XOR and AND is available immediately). 

So, total time taken = 2.4 + 2.4 = 4.8 μs for 1-bit calculation.

Hence, gate delay for 4-bits = $4*4.8=19.2\ μs$.

Answer 6

Diagram shows flow of input to output along with delay at each level ; for understanding