8.7k views

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.

1. 4 time units
2. 6 time units
3. 10 time units
4. 12 time units
| 8.7k views
+3

if carry network is implemented using only two inputs AND-OR gates  then total time will be 9 units.

0

@renna_kandari

How ?

I am getting 8,

2(Pi,Gi)+2+2(To implement 2ip AND gate delay=logN=2 &To implement 2ip OR gate delay=logN=2) +2(sum generate)

+1

@reena_kandari They are saying whole carry network is implemented in two level AND-OR logic not to use two input AND-OR gates.
@VS  do you have implementation of this logic using 2 input AND OR gates?

+1
I said "IF" it is implemented as two input AND-OR logic.
0
@reena_kandari can you share implementation using 2 input and or gates?
0

shivangi5  how?

0
C4=C0P0P1P2P3 +GoP1P2P3 +G1P2P3+G2P3+G3 .

Now if the fan input allowed is 2 than total time taken would be (log 5+log5)=6  for carry part

For sum part it would take 2 .

Total 8.

Only in condition when 2 input and  or logic is used
0
8 if 2 input AND - OR  logic is used
+1
It will be 10 if fan in of AND/OR gate is 2

2(Pi , Gi) + 6(carry) + 2(sum) = 10
+6
for carry network..if we use only two input gates

$t=0$ ,  $G3$, $G2P3$,$P3P2$,$P1G0$, $P1P0$

$t=1$,   $G3+G2P3$,$P3P2G1$,$P3P2P1G0$,$P1P0P3P2$

$t=2$,   $G3+G2P3+P3P2G1$, $P1P0P3P2C0$

$t=3$,  $G3+G2P3+P3P2G1+P3P2P1P0C0$

$t=4$,  $G3+G2P3+P3P2G1+P3P2P1P0C0+P3P2P1G0$

total gates $2+5+2$ =$9$ gates
0
i think ans is 4 time units....
+2

Thank You @reena_kandari ji, For posting this variation.

$C4 = G3+G2P3+P3P2G1+P3P2P1G0+P3P2P1P0C0$ Here only 5 unit of delay will happen.

Refer ->

https://gateoverflow.in/39688/gate-2016-1-33

0
here dont think about FAN IN as it was not mentioned anywhere asume that FAN IN is NOT restricted to 2
0
final sum to be calculated can be visualised in sop form of initial inputs...then can't we do the same in just 2 units of time?
plz clear my doubt asap
0

Can you please check this ?

All calculation is right till carry generation 2+9

But for last phase we have Sum of Full adder which is Pi XOR Ci

We have only 2 input gates ..you considered Time delay for Sum is 2 units .(AND Level + OR level)

How can you take Pi both in complemented and True form ..we have only True form of it ..

And it is given all inputs are available in True and Complemented form But not Pi and Gi

0
some answer saying it is 6 and some is saying it is 4 time unit

what is right one ??
0
@Gurdeep 6 is the correct answer only. Always follow BEST answer. They are chosen best due to some reason. and you can clearly see when everyone is saying 4 is the correct answer, only best answer says it is 6
0
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.

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.

by Active (3.6k points)
edited
+1
Hi Ryan ,

Is it that ,we need to use two input AND/OR gates ?
+7
XOR operation is defined as

$A \oplus B = (\bar{A}\cdot B) + (A \cdot \bar{B})$

Irrespective of 2,3 or n input AND , OR gates, We first need to computer all the AND outputs (which are fed to the OR gate as input), followed by the OR output.

Hence its a 2 stage operation.
+2

If Pi is calculated as Pi = Ai + Bi , then the first stage can be completed in 1 time unit, right?? Then why it is calculated as Pi = Ai B ?

+2

I hope your doubts will be clear from this..

+3

But in the question it is not mentioned which definition of Pto be used (i.e, Pi = Ai + Bi or Pi = Ai B ). Then why is the XOR definition used instead of the simpler OR verison?

+2

Plz see in the link that I have mentioned :

0

but  could u plz tell me how for Pi

Pi is XOR , which takes 3 level of AND gate. isnot it?

0
XOR is two level implementation of AND gates followed by OR gates..
+11

@ 101010 , U can use any definition of $P_i$, but if you use OR definition, then answer would be 5 and there is no option matching so we should use another definition.
See this they have realized $P_i$ using OR.
Any function, no matter how complex it is, Can be written in terms of POS. And every POS form can be realized using 2 levels of AND-OR.
Therefore, EVERY function can be realized using 2 levels of AND-OR. ( Provided inputs are available in both complemented and uncomplemented forms )

+1

Why sum and carry can't go parallel like you said in 1st point. ?

here 4 is given as key.

http://www.ankurgupta.net/gate-solutions/gate2004cs/

+2

For finding [ Pi = ai EXOR bi ], we can use 2-level AND-OR logic because [ a EXOR b = ab' + a'b ] and in question it is given that all inputs are available in TRUE form and complemented form.

BUT for finding [ Si = Pi EXOR Ci ] , how can we use 2-level AND-OR logic ?? because both Pi and Ci are available only in True form and we dont have complemented form (i.e) Pi' , ci'.

0
Yea. The answer should be 7 time units since we have to complement Ci during the XOR operation in 3rd step.
+3

Are we not considering fan in?

Can we calculate P3P2P1G0 at once?

+1

This should be 4 units instead of 6. Reason is as follows: Since, S = P xor C Given that, C can be implemented with 2 levels => 2 units. P is xor, which can be done in 2 levels with and or realization =>2 units. The calculation of P and could be done in parallel with that  of P. Therefore, effectively we'd need 2 time units for above two operations. Now, the final xor for getting S could be done with 2 levels with and or realization => 2 units. So, 2+2 = 4 time units we need.

0

For more clear understanding , we can refer to this : https://gateoverflow.in/29551/carry-lookahead-adder

+1
+1
can anyone explain through diagram.
0

@Ryan why u are not considering the NOT gate as level just we have firstly complement the bits and then we have to fed up to the and logic and then we are suppose to do oring finally so it should be 3 level if we consider the NOT gate also One level.

+2

This is the only correct answer. Carry look-ahead adder works in 3 levels. Everyone is missing the 3rd level.

0

whats the use of  calculating here level 1, as we can simply put the p(i) and g(i) formula in c(i) amd can get the sop form so total time will be 4 only .

0
The question mentions "All inputs are

available in both complemented and

uncomplemented forms"...  So we can take

^a and ^b values without using a NOT gate.

However for getting the sum S = P XOR C...

P and C are not in the initial inputs. So don't

we need to have NOT gates as well , in

addition to AND and OR gates for the final

sum?  In that case the delay would be

2+2+3=7

To get Si  = Ai⊕Bi⊕Ci it requires two level AND-OR implementation

To generate Ci = function of (A0,B0,C0, A1,B1,C1, Ai-1,Bi-1, Ci-1) it also require two level AND-OR implementation.

so a total delay of 4 level, which is equivalent to 4 unit delay.

by Boss (13.5k points)
+4
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??
0

how  Ai⊕Bi⊕Ci   will require two gate delays???

0
express above expression in soop formate which takes 2 level AND - OR circuit.and 2 unit gate delay also .
+1
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
+1

by Active (2.6k points)
+1
in the above link they are using xor gate at fiest level and 3rd level which is not allow according to question.
+1
answer in this link is 4 units because there XOR gate is given but here,XOR gtae is not given
->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.
by Active (2.2k points)
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.
by Loyal (9.9k points)
0
Dear Seniors,

how it is getting 4 or 6 or 8.

in carry lookahead generator only  3 AND delay and 3 OR delay required. as no of input is 4.

for input to carry generator , we need Pi and Gi. as complemented output is available, for XOR gate it should take 2 delay
( one for AND and one for OR) so 2 gate delays reuired here.

now after carry generated, for sum, again XOR is required. which again take 2  delay if complemented Pi and Ci available.
but only inputs are available in both complemented and non complemented form, so we should use one NOT gate for complement Pi and Ci.
Thus, 3 gate delay required here.

In summary,

2 + ( 3 +3)  + 3 = 11

if we assume Pi and Ci isavailable in complemented form also thb it should take 10 Gate delays.

please tell me where i am wrong.

Thanks

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.

by (209 points)
First step: for all Gi and Pi , need to implement xor as input are available in both normal and complement form,

so it can be implement with one and level then or level. so 2 level delay.

Step 2: Carry Network delay its 2 gate levels as given in question.

Step3 : Now to generate sum , we again need to do xor operation that can be done in 2 gate level[Using NAND & OR in first level then AND in Second level as X XOR Y = (X'+Y').(X+Y)]

So, Total 6 gate level delay.
by (401 points)
edited by
the only thing we have to notice here is that FAN IN is not given in question ,so we can take as we want. and then all the carry will be generated in equal amount of delay(C0,C1,C2,C3). therefore maximum delay will be because of S3 that is last sum ,s3=p3xor c3.
by (149 points)