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

@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