GATE CSE 2004 | Question: 62

Question

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.

• A. 4 time units
• B. 6 time units
• C. 10 time units
• D. 12 time units

Comments

This is how it should look like, please let me know if there's anything wrong with the diagram.

---

Lets Break the question into three steps 

Observing   we need to calculate two things  that is sum and carry → Main Motive 

and  the respective sum of any bits  is dependent on the carry  let’s say we want to calculate 

sum s1 =(a1 xor b1 xor c1)  what it will be basically calculating is a1+b1+c1

now  for calculation of sum it is dependent on carry so we will calculate carry first before sum

Equations for generating carry

C1=G0+P0C0C1=G0+P0C0

C2=G1+P1G0+P1P0C0C2=G1+P1G0+P1P0C0

C3=G2+P2G1+P2P1G0+P2P1P0C0C3=G2+P2G1+P2P1G0+P2P1P0C0

C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0

observe these equations here the carry is generated and we can clearly observe carry is dependent on  G and P  so for to calculate carry we need to calculate G and P first 

now lets say G0 then G0 = A0 and b0

and P0 =(A0 xor B0)  

now first we need to calculate G and P  ,Using this G and P we will generate carry and finally by using carry and p we will generate the sum

Level 1 operations 

first generating G and P   
G can be generated directly using an AND operation that will take only --- 1 TIME UNIT
 

P needs xor of A and B and we don't have Xor gate directly so we will implement xor as two level operations of AND & OR gate  ,here we even have the complement of the respective variables   

it takes – 2 TIME UNITS

Maximum of this level is 2 units  so we will consider 2 units for this level

Level 2 operations 

Level 2 operations includes calculating carry here  we can observe all these are AND & OR operations   AND takes 1 time unit and OR takes 1 time unit 

C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0

this level as on a whole takes 2 time units 

Level 3

Level 3 operations takes 3 time units for calculating the sum as it is XOR of P and C  but here the complements are  not present for p and c as we need to calculate that takes 1 level and after that we apply xor that is AND-OR which will take 3 time units

 2nd way when we take  assume that complement of c and p is also available as it is given that all the complements of i/p's are also available then it will take  only 2 units 

Total 6 units/7 units both should be write depending on whether C and P  's complements are available or not

---

For those wondering why the last stage for computing sum $(S_i = P_i\oplus C_i = \overline{P_i}\cdot C_i + P_i\cdot \overline{C_i})$ only takes $2$ units when the complements of $P_i, C_i$ are not available to us and so think that this $XOR$ operation should take $3$ units of time:

Note that we have a $NAND$ gate available to us to design this circuit and that $XOR$ operation can be implemented using $\text{2-level NAND-OR-AND}$ circuit as follows:

$S_i = P_i\oplus C_i = (\overline{P_i} + \overline{C_i})(P_i + C_i) = (P_i \uparrow C_i)( P_i + C_i)$

Answer 1

Carry lookahead adder can be thought to be made in 3 levels as below

Level 1 : P & G Generator

$Gi=Ai.Bi$

$Pi=Ai⊕Bi$

$Gi$ uses AND gate which takes one unit time

$Pi$ uses EX-OR which can be implemented by AND-OR in two levels => it will take 2 unit time 

$Gi$ and $Pi$ work in parallel so they will take time = 2 units 

Level 2 : Carry Generator

$C1=G0+P0C0$

$C2=G1+P1G0+P1P0C0$

$C3=G2+P2G1+P2P1G0+P2P1P0C0$

$C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0$

This uses two levels of AND OR (see fig) so time =  2 units

Level 3 : Sum Generator

 

$Si=Pi⊕Ci$

it uses  EX-OR gate which can be implemented by AND OR so time= 2 units

Total time = 2 + 2 + 2 = 6 Units  

Option (B)

Answer 2

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.

Answer 3

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.

Answer 4

If nothing is mentioned take fan-in for a logic gate = 2 inputs and they will say in the question whether to take half adder or full adder for the 1st stage of LSB addition(ripple carry adder).

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

Carry look-ahead adder works in three phases:-

In carry look-ahead adder all Pi, Gi terms are computed simultaneously after that all carry terms are computed simultaneously and after that all sum terms are computed simultaneously.

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.

Note:- Any simple or complex logical function can be written in SUM OF PRODUCT form and can be realized using 2-levels of AND, OR gate only if both complemented and uncomplemented forms are given.
 

 

Now lets extend this question further for Ripple carry adder:-

In ripple carry adder(n bit adder):-              Assume Full adder is used for LSB computation, not half adder

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

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

T.sum=4,       because A⊕B can be implemented using 2 levels of AND, OR gate only if variables are given in both complemented and uncomplemented form as mentioned above. then further one more XOR with C. so total 4 level of AND, OR gate.

Tpropagation for ripple carry adder = 10

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