The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+27 votes

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.

- 4 time units
- 6 time units
- 10 time units
- 12 time units

0

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

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

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

+5

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

$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

+1

Thank You @reena_kandari ji, For posting this variation.

Dear readers notice -->

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

Refer ->

+51 votes

Best answer

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

0

Hi Ryan ,

Can you please help me know what is meant by two level AND OR Logic ?

Is it that ,we need to use two input AND/OR gates ?

Can you please help me know what is meant by two level AND OR Logic ?

Is it that ,we need to use two input AND/OR gates ?

+2

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.

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

0

If *P*_{i }is calculated as *P _{i }= A_{i} + B_{i} , *then the first stage can be completed in 1 time unit, right?? Then why it is calculated as

0

Please consult the part : "Carry lookahead method" of the link :

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

I hope your doubts will be clear from this..

+1

But in the question it is not mentioned which definition of *P** _{i }*to be used (i.e,

+1

Plz see in the link that I have mentioned :

However, for a multiple-level carry lookahead adder, it is simpler to use XOR instead of OR..

+4

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

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

0

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

+10 votes

To get S_{i} = A_{i}⊕B_{i}⊕C_{i} it requires two level AND-OR implementation

To generate C_{i} = function of (A_{0},B_{0},C_{0}, A_{1},B_{1},C_{1}, A_{i-1},B_{i-1}, C_{i-1}) it also require two level AND-OR implementation.

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

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

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

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

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 vote

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.

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.

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.

@Arjun Sir...please clear my doubt.

Thanks

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.

@Arjun Sir...please clear my doubt.

Thanks

+1 vote

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

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 496
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,111 questions

44,694 answers

127,237 comments

43,753 users