32,183 views
80 votes
80 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.

  1. 4 time units
  2. 6 time units
  3. 10 time units
  4. 12 time units

17 Answers

Best answer
159 votes
159 votes

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.

edited by
23 votes
23 votes

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.

6 votes
6 votes

answer is 4 time units.

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

5 votes
5 votes
->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.
Answer:

Related questions

44 votes
44 votes
5 answers
1
Kathleen asked Sep 18, 2014
18,991 views
Consider the partial implementation of a $2-bit$ counter using $T$ flip-flops following the sequence $0-2-3-1-0,$ as shown below.To complete the circuit, the input $X$ sh...
24 votes
24 votes
2 answers
2
29 votes
29 votes
2 answers
3
Kathleen asked Sep 18, 2014
10,112 views
Which are the essential prime implicants of the following Boolean function?$f(a, b, c)= a' c+ ac'+b' c$$a' c$ and $ac'$$a' c$ and $b' c$$a' c$ only.$ac'$ and $bc'$