2.9k 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

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

@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)

@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?

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

shivangi5  how?

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
8 if 2 input AND - OR  logic is used

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.

selected by

but  could u plz tell me how for Pi

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

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

@ 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 )

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/

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'.

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.

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??

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

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

in the above link they are using xor gate at fiest level and 3rd level which is not allow according to question.
answer in this link is 4 units because there XOR gate is given but here,XOR gtae is not given