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

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.

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

plz help me out .I`m confused . I understand what is the procedure of yours .

but in the official site they have given answer 19.2 ( 4.8*4 )

see question no. 65  : http://gate.iitk.ac.in/GATE2015/AnsKey2015/CS_S06.pdf 

---

I have seen it, This one and one another question regarding frame size GATE gave really "bull shit" key. Many others are debatable ones, but this is the first time really blunder ones come in GATE key.

---

 Delay for generating C is 1 AND + 1 OR =  1.2 + 1.2 = 2.4 ms y 1 and here ??? shd 2 and  3 * delay for carry  this 3 due to 4 bit binary adder ryt ???

---

@Pranay Sorry. There was a catch here - ripple-adder. Answer must be 19.6 only.

@Shimpy Is it clear now?

---

Thanks . now its cleared . Just a small correction 4.8*4=19.2 .

I compare this with the movie Race 2 . "twist k ander twist " :D  .peace

---

plz tell me y this  1 OR = 2.4 + 1.2 + 1.2 = 4.8 ms ?? need of this OR ???

---

See the diagram- there is an OR gate.

---

sir .if it were given as PARALLEL BINARy  ADDER  instead of ripple ,than it will take total time as 4.8msec.??

---

A 16-bit ripple carry adder is realized using 16 identical full adders (FA) as shown in the figure. The carry-propagation delay of each FA is 12 ns and the sum-propagation delay of each FA is 15 ns. The worst case delay (in ns) of this 16-bit adder will be _____.  (The question was asked in 2014 ECE (SET-4) question no-41 .But the answer given by iit kgp (ANS-195)  does not use ripple carry adder concept!! whats the concept actually?)

---

Sir for calculating the delay for c why you are not adding 2 AND gates?

---

Hello Arjun Sir, one thing i didn't understand.... they said one full adder was implemented with 2 half adder and one OR gate.... so for 1 full adder delay will be 1st XOR delay (from 1st half adder) +2nd XOR delay(from 2nd half adder)+ 1 OR gate means 2.4+2.4+1.2= 6ms????? please clarify...

---

@arjun sir..how will we infer that in a question we have to calculate using n*(gate delay of 1 full adder) ,like 19.2 here or the other method which gave 12??which method to follow for what kind of adder??please explain as every year propagation delay type qustions come and they are very confusing.!!

---

what will happen if the carry and the sum generated different values of propagation delay. Then what will be the final answer ??

---

Unable to get this question clearly.

What I understood : when we calculate the sum and carry of first half adder ie, $AB$ and $A\oplus B$, we calculate the delay for this as max(delay for $AB$,delay for $A\oplus B$ ) = $2.4$ in this question.

After this is done we can use this result to calculate the result of 2^nd half adder i.e., $A\oplus B\oplus C$ and $C( A\oplus B ) + AB$ and again delay for this step is maximum of these two = $max(1.2+1.2,2.4) = 2.4$

Total delay for 1 full adder $= 2.4 + 2.4 = 4.8$

Delay for 4 full adders used in ripple carry adder = $4.8 * 4 = 19.2$

Correct me if Iam Wrong ?

---

Arjun Sir,

carry in is 0 for the first 1 bit adder, so we can use only 1 half adder there. and after that as you said "operations can be done in parallel-As long as input to a gate is not dependent on the output from another gate, those two can be operated in parallel." so total 2.4 x 4=9.6 .. why not 9.6 then?

---

Ans is 19.2 ms

Delay for generating C is 1 EXOR + 1 AND + 1 OR = 2.4 + 1.2 + 1.2 = 4.8

 Delay for sum is XOR + XOR = 2.4 + 2.4 = 4.8 ms

And for a Ripple Carry adder

T = (n-1) Tc + Ts

=    3* 4.8 + 4.8 = 19.2ms

---

this same question was asked in one of the made easy tests and they solved it differently and their answer is 12ns. Dont know why.. According to me 19.2 is the best one. which appoach to follow in gate??

---

" Delay for generating C is 1 EXOR + 1 AND + 1 OR = 2.4 + 1.2 + 1.2 = 4.8 ms "

Sir here 2nd XOR depend on first XOR and one AND depend on 1st XOR.

Among these two, XOR has maximum delay

So, we should take 2 XOR and 1 OR gate. rt?

Cannot understand why AND gate delay is taking?

Rather 2nd level XOR gate delay should take. as it's delay is more.

Plz explain where I am doing mistake.

---

For Carry, we don't need the output of second XOR rt?

---

Only after getting the carry from the previous stage we can and it with the first xor output of that stage that's why and gate delay is taken right?

Also how to know whether we have to consider the first xor outputs produced paralelly or not? We can't know what the key will have. How to know in examination?

---

@sushmita I'm no expert in digital but if I write GATE and this question comes I'll give 12 as answer :)

---

Yes, 12 seems right.

---

what was the key answer 12 or 19.2   ? :(

---

it was 19.2

---

arjun sir, so which approach should we follow??? :(

---

only carry is rippled through various stages, not sum, thats why named as ripple carry adder. so parallel execution of sum is possible. so , surely answer will be 12.

---

Sir, please change the units in the answer to microseconds

---

Sum=A⊕B⊕Cin

Carry Output= Cin.[A⊕B] + AB

These are the equations which can be realized for full adder as per the description is given by the question.

XOR gate delay=2.4 microseconds and AND/OR gate delay= 1.2 microseconds.

So this way, Sum delay of 1 Full Adder= 2.4+2.4=4.8 micro-seconds.

Carry Delay= First we have to wait for the output of A⊕B, which will be available to us after 2.4 micro seconds, and then 1 AND operation + 1 OR operation. So total= 2.4+1.2+1.2=4.8 micro seconds.

The question is asking for total propagation time of 4 bit binary adder implemented using described 4 one bit full adders.

The total propagation time means when would the last Full adder give the output of Sum.

The last Full Adder can only produce sum output only when carry input from previous Full adders are available.

So, the fourth Full Adder will wait (3*4.8 microseconds) for carry from previous 3 Full adders,

and produce the sum in next 4.8 microseconds after this.

So, total delay= 3*4.8 +4.8 = 19.2 micro seconds.

---

But the carry is added with the sum right ?

so without carry how can sum be calculated

it cannot happen in parallel in case of ripple carry na?

---

@srestha

if we look at the diagram provided by arjun SIR

1 XOR , 2 AND and 1 OR gate is involved for carry right?

why only one AND gate is considered

---

Do u know, how to access parallely?

For carry generation there are 2 AND gate, that is true

But for parallel access in 2 AND gates we have to take max(gate1,gate2)

So, for calculation purpose 1 AND gate is sufficient

---

@srestha yeah got it :)

---

@srestha

if the question said that the ripple adder could use only half adders provided

then what will be the answer

---

Answer should be 12 and not 19.2, just because it's given in the key we should not change our understanding of the concepts.

---

i don't understand mean of total delay?

if its (carry delay+sum delay) then answer will be different???

---

Arjun sir ...In Morris Mano book it is given that the total propagation time in the adder would be the time in one half adder plus 2n gate levels for n bit parallel adder

---

@ayush i attempted this question in test and i marked the option with same approach that you followed but they described the solution same as Arjun sir said -

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μs and carry in another

2.4μs. In this way, 4-bit sum can be obtained after

4.8μs+3∗2.4μs=12μs.

So finally what approach should we followed? i seen it's time complexity also which theta(n*FA) means 19.2 should be right .

---

@Prince-Arjun's sir approach is correct if we want the minimum time to compute the sum using 4 full adders,sir has use concept of parallelism.But, as sir said and in my approach, we have assumed the hardware as given to be "ripple carry adder" means once the previous output is available then only the next computation starts.

However, it would be good if you post your question here on GO and comment it's link here so that we can see where the difference lies.

---

@Ayush Upadhyaya

The total propagation time means when would the last Full adder give the output of Sum.

It should be "When last Full added gives output of sum and output carry as well right ..at ouput we want both sum and carry ??

So it should be (N-1)Tsum + MAX(Tsum ,Tcarry)

Here it so happened that Tsum = Tcarry

---

@Jatin-No. See why we shifted from ripple carry adder to carry lookahead adder? What was the change? The carry network was implemented independently and then the adders don't have to wait for the carry to get ready from the previous adder.

We are worried about the propagation time of carry in ripple carry adder, because say if carry had no effect on the result, then why would have we bothered about designing carry look ahead adder.

Here it is very clear they are asking what is the total delay occurred in producing the carry, means when would last carry be produced.

---

So what is total propagation delay of this adder considering ripple carry adder

Time we get carry from last full adder ??

What IF for full adder Tsum we got 4.8 and Tcarry 5.2 ??

---

For this question, time we get carry from last full adder is $4*4.8=19.2\mu s$

You are asking what is total propagation delay for a 4-bit ripple carry binary adder whose sum is produced in $4.8 \mu s$ and carry in $5.2 \mu s?$

Carry to the last full adder would come after $3*5.2 \mu s$ and then output carry would be produced in another $5.2 \mu s$ and hence total propagation delay=$4*5.2 \mu s$

---

If delay for Sum output of adder is asked , then we should consider 3*5.2 + 4.8 right ?? 

---

@Jatin-Yes that's correct.

---

@Arjun sir,

if they ask for how much time is going to take for generating sum then writing direct 4*4.8 doesn't make good sense it should be written like [3*4.8(carry)+4.8(sum by last FA)]. which leads to definately 19.2.

---

@Arjun Sir,
The answer considered for evaluation is $12$ but as explained above it's $19.2$ please update.

---

What update you want? Official GATE key was 19.2

---

@Arjun Sir but the answer key mentioned here is 12.

---

oh. Not sure who changed it. I have corrected now. Anyway will get a better explanation for this.

---

@Arjun sir 

@Bikram sir 

I don't know why one should go with 19.2 as answer... It's clear that the answer must be 12... What to choose when the same type of question comes in gate ? 

---

@Devendra Thakur

This would make the total delay =4∗4.8=19.2μs and this is the key given by GATE,

so obviously they meant this.....

---

Thanks sir for clarification...

---

@Arjun Sir

Please correct this answer.

The best way to analyse this answer is by drawing a detailed representation of the "gates."

Earlier the answer given by gate authority is 19.2 but later on after evaluation they changed it to 12.

---

@`JEET, could you please share the link to the updated key?

Thanks.

---

@Veenit

Just check out my answer below. You will understand it very well as I have drawn it very neat and clean.

In the mean time I will provide you the updated key.

This is the wrong answer and I wonder how it can be the best answer considering the excellent quality of all other questions on the gateoverflow.

I am just waiting for the Arjun Sir to take a note of this question or to have a conversation.

Hopefully this will get correct soon.

---

@Veenit

Just check out my answer below. You will understand it very well as I have drawn it very neat and clean.

In the mean time I will provide you the updated key.

This is the wrong answer and I wonder how it can be the best answer considering the excellent quality of all other questions on the gateoverflow.

I am just waiting for the Arjun Sir to take a note of this question or to have a conversation.

Hopefully this will be corrected soon.

---

Yes. I too, am unconvinced by the 19.2 micro seconds answer.

---

@Arjun Sir,

What if we can get the Carry before SUM? Can we use this Carry for next Adder? 

---

@Arjun sir which method should we go for if it is asked in exam? Isn't the formula for ripple carry adder total propagation time

(n-1)xTc + Ts ? So according to that we get 19.2 micro seconds. But according to the diagram it is clear that 12 micro seconds should be the answer. I am really confused.

---

This doesn't work all the time.

You need to have the proper analysis of such a question.

Nevertheless asking such questions is very rare.

---

okay,thanks!

---

Another fastest way for answering this question is to find Tsum and Tcarry.Once u find them just apply this formula

Total Time Required =(n-1)Tcarry+maximum(Tsum,Tcarry).

Here, in one FA sum delay =XOR+XOR = 2.4+2 4 =4.8

Carry delay=XOR+OR+AND= 2.4+1.2+1.2=4.8

So apply formula,n=4(given in question)

(4-1)(4.8)+maximum(4.8,4.8)

=3×4.8+4.8

=14.4+4.8

=19.2microseconds.

---

@Chelsi

This is wrong answer.

Correct answer is $\mathbf{12}$

---

@Ayush Upadhyaya, @Arjun sir I think there is no problem in applying the concept of parallelism and answer can be 12. Please tell me weather I am correct or wrong

Source:- https://youtu.be/YBY0k5mIQy0

​​​​

​​​

---

Archive of reference link provided in answer:

https://web.archive.org/web/20161230075031/http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/adder.html

---

 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 

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.

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 .