Sums on Adder

Question

$1)$3-bit ripple adder, which adds two 3-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

______________________________________________________________________

$2)$3-bit carry look ahead adder, which adds two 3-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?

Comments

@Prateek Raghuvanshi @srestha In the image above, $C=C_{in}(a⊕b) + ab$ will require 3 levels not 2 as Prateek sir has mentioned!! Wouldn't that make your formula 2n-1 wrong?

---

If nothing is mentioned take fan-in for a logic gate = no. of inputs and never use half adder for the 1st stage of full adder computation unless they explicitly mention it because we try to generalize things we don't design the circuit for a particular problem.

---

@Shaik Masthan @Prateek Raghuvanshi

for ripple carry adder, can it not possible answer to be $4$?? Say 1st one full adder and 2nd and 3rd half adder??

Ref: https://gateoverflow.in/8250/gate2015-2-48

Answer 1

1) In Ripple Carry Adder, only carry is propagated. So, 3 Full Adder is sufficient to add two 3-bit numbers.

Now,  among these Gates EXOR has maximum propagation delay.

And 1 EXOR can be made of 2 time unit in AND-OR gates. 

If LSB is Half adder,

So, propagation delay will be 2n-1=5 time unit

(Here Carry is propagating with sum)

----------------------------------------------------------------------------------------------------------------------

 

2) I tried to put Carry Look Ahead  adder in a diagram.

Here All adder are parallel and carry is propagated

Acc to wiki

• calculation of  $P_{i}$and  $G_{i}$ is done at time 1,
• calculation of $C_{i}$ is done at time 3,
• calculation of the $PG$is done at time 2,
• calculation of the $GG$is done at time 3, 

https://en.wikipedia.org/wiki/Carry-lookahead_adder

Here for 3-bit addition $GG$ will be  2 time  unit and $PG$ will be 2 time unit and $C_{0}$ will be 1 time unit

So, $C_{3}=G_{2}+G_{1}.P_{2}+G_{0}.P_{1}.P_{2}+C_{0}.P_{0}.P_{1}.P_{2}$

here $2+2\times 1=4$ time unit

Ans-4

(In Carry Look Ahead Adder  carry and sum propagating differently . In Ripple Carry and in CLA both case we concentrate only on Carry, not on Sum , as carry propagated upto last both the case )

http://faculty.kfupm.edu.sa/COE/abouh/Lesson3_2.pdf

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

Comments

@ srestha mam,

there are three level in CLA adder . At 1st level  all $P_i$ and $G_i$ are calculating using x-or and AND gate  since x-or gate is not available so we have to implement x-or gate using basic gate so we can implement x-or gate using two level then only 2 time unit required  on first level .  In 2nd level  we know there is two level circuit in block using AND ,OR gate so here also two time unit is required and at third level we can see there are also X-OR gate so again 2 time unit required , so total 6 time unit required .2 time unit extra are there because X-OR gate is not available direct.

Answer 2

For ripple carry adder answer will be 8 time unit and for carry look ahead adder the answer will be 6 time unit.

In ripple carry adder(n bit adder):- Assuming fan-in atmost 2 and LSB's are computed using full adder.

Tpropagation =(n-1)* T.carry generation time by one full adder+ max(T.carry, T.sum)

   = 2*2  (2 because C=AB+BC+AC can be implemented in 2 levels of AND, OR gate) + max(4, 2)

T.sum=4 because A⊕B⊕C can be implemented using 4 levels of AND, OR gate only if variables are given in both complemented and uncomplemented form.

Tpropagation for ripple carry adder = 8

In carry look ahead adder(n bit adder):-

Carry look ahead adder works in three phases

The first level will take 2 time unit to generate all Pi, Gi terms using AND-OR gate in 2 levels only if variables are given in both complemented and uncomplemented form. similarly 2nd level will also take further 2 time unit for generating the all carry terms and after that to produce the sum terms it will take further 2 time unit. so total propagation delay is 6 time unit.

for more-https://www.gatevidyalay.com/delay-in-ripple-carry-adder/

Comments

Ripple Carry adder, it has direct formula , should be 5 unit. Check above answer plz.

---

well, let me recheck.

---

@Nitesh Singh 2

I think we can not use Half adder for 1st stage computation unless it is explicitly mentioned and a Full adder becomes active only when its carry-in is made available by its adjacent less significant Full adder. 

No, check here https://gateoverflow.in/1494/gate1999-2-16

last LSB can be half adder  for sure, but other bit should use full adder. So, it is not correct conclusion

right??

---

U can see here full adder implementation and can understand ,from  where that formula came? Still if u have doubt , u can ask

---

Yes, in theoretical concept LSB of addition need not any carry-in, so half adder is sufficient. But in practical approach or in generalization we only use full adder for the simplicity of design, even NPTEL video I have shared confirms that, so above gate question asked in 1999 has the correct answer but for a problem where we have to compute the propagation delay in a Ripple carry adder we should use full adder for LSB addition also. Even for ECE branch, they have the DIGITAL subject as well and one of the questions asked in 2014 clearly states that if nothing is mentioned use full adder for all binary addition in a ripple carry adder.

---

Let's test the authenticity of the Formula given =2n-1      {for n bit adder}

we are subtracting 1 in the formula because LSB addition will take 1-level lesser than remaining ckt using HALF adder which is correct. Let's move further, we are multiplying N by 2 times thinking that in remaining full adders carry will take 2 levels to be generated which is correct

C= A.B + B.C + A.C     {We can also use XOR gate instead of OR gate but that won't make huge difference}

Now, what about the SUM circuit? at the last stage of full adder(Nth full adder), either carry will take more time than sum to produce or SUM can take more time than carry to be produced but we are not considering this condition at all. why?

For example OR gate takes 5ns, AND gate takes 10ns, XOR gate takes 20ns. In the last stage, sum will take at least 20ns depending on fan-in for XOR gate but carry will take exactly 15ns. So my question is why we do not consider 20ns for the last stage of delay?

---

@Nitesh Singh 2

I think ur concept isnot clear.

Here sum and carry generating parallely. So, if we take larger delay, it already calculating sum bit.

---

U can compare it with this question too https://gateoverflow.in/8250/gate2015-2-48

ckeck now, what is coming??

---

So in your opinion 2 in the formula is for maximum 2-level delay whether it is due to sum or carry. but only carry propagates meanwhile sum will come and we always consider carry delay in any formula. Mam kindly read my doubt closely. What if in the last stage sum takes more time to be generated.

---

Yes, Answer is right for the above gate-2015 question but if you follow your formula or mine, the answer does not change. Even my method is giving the same answer because in this question sum & carry take 4.8ms to be generated.

---

Just do one last thing. Kindly solve this GATE-2014 ECE question using appropriate formula according to you.

---

@Nitesh Singh 2

In 2014 EC question, it is already told 16 FULL ADDER is taken, So, that is different thing. There we no need to think about circuit by our own. Right??

---

Ok here is my list of doubt. If you think it is incorrect kindly share some resource to make it correct as I have already shared some resource to make my point correct. But please read it carefully because I don't think you have read my earlier comments focused.

1) In ripple carry adder, 2nd full adder will only start working as long as carry from 1st full adder made available. It means sum=A⊕B⊕C . Here computation of A⊕B will not be done beforehand and only be done when input carry will be available from 1st full adder.

2) In ripple carry adder, only carry propagates, so total propagation delay for the addition of 2 binary number will take (n-1) times carry delay. It doesn't matter whether sum delay is greater than carry delay because the time at which carry gets produced next full adder will start working and meanwhile sum will be computed.

3) In ripple carry adder, although carry & sum are computed simultaneously but one can take more time than other to be computed. So the total propagation delay will include (n-1) carry delay and from last full adder the max. delay(carry, sum) whether it is carry or sum because computation is not over if both are not produced.

---

All three points are correct.

---

Ok my last query, If nothing is mentioned in the question about fan-in for a logical unit like AND,XOR in ripple carry adder then by default what should be the choice. 2 or n?

---

How far I know, in GATE question everything should be mentioned. If nothing mentioned we can assume anything.

---

@Nitesh Singh 2

Can u tell me one thing??

If carry look ahead adder will take 6 time unit, then what is it's difference from only a full adder??

A full adder also can take 6 unit time.

right??

also from where u took 4 levels??

 

using 4 levels of AND, OR gate only if variables are given in both complemented and uncomplemented form.

it is 3-bit ripple carry adder 

---

Propagation delay will increase in ripple carry adder if no. of bits to add are increased, but will take 6time unit to generate the same in carry look ahead adder.

---

If fanin=2, SUM=A⊕B⊕C=A'B'C+A'BC'+ABC+AB'C'  it will take 2levels of AND gate then 2levels of OR gate.

---

@Nitesh Singh 2

Can u relate this question with this question toohttps://gateoverflow.in/217413/adder

how taking $log n$ time??

---

It is taking log n because fan-in is atmost 2(although it is not mentioned but question asker assuming it). If it would have been fan-in=n then it would take 6 unit of time only. Although it is not true that we can design N input gate because of the fact that N input together will make the voltage level unstable or propagation delay will increase.

---

Kindly point out my mistake & correct it accordingly. So that I can understand better where I should focus on.

---

you r not wrong, but still  I was finding, why two answers giving different result. Concept same na??

---

Yeah! We both agree on the same concept, but the problem arises when question doesn't mention fan-in for gates and whether to take half adder or full adder for the LSB computation. But till now GATE questions have been given with proper information about these both, so no point in arguement for non-standard question. I took full adder for LSB computation because of the generalization purpose, so that we could use the same circuit for other computation also(This thing I infered from NPTEL lecture) and by solving more and more questions on "Adder" I am convinced that by default take fan-in= n whenever necessary.