GATE CSE 2007 | Question: 35

Question

In a look-ahead carry generator, the carry generate function $G_i$ and the carry propagate function $P_i$ for inputs $A_i$ and $B_i$ are given by:

$$P_i = A_i \oplus B_i \text{ and }G_i = A_iB_i$$

The expressions for the sum bit $S_i$ and the carry bit $C_{i+1}$ of the look ahead carry adder are given by:

$$S_i = P_i \oplus C_i \text{ and } C_{i+1} = G_i + P_iC_i, \text{ where }C_0 \text{ is the input carry}.$$

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all $P_i$ and $G_i$ are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a $4$-bit adder with $S_3, S_2, S_1, S_0$ and $C_4$ as  its outputs are respectively:

• A. $6, 3$
• B. $10, 4$
• C. $6, 4$
• D. $10, 5$

Comments

that's the case which is explained well in this comment -> https://gateoverflow.in/1233/gate-cse-2007-question-35?show=353199#c353199

---

The whole point of Carry Look ahead generator is parallel carry and sum generation
At t = 0 we have a0a1a2a3, b0b1b2b3 , c0
then we calculate Pi and Gi parallely
then we calculate c4 c3 c2 c1 also parallely only after above is done
then we do sums
Hence the delay also is dependent only on what we take delay for each basic gates initially . for which it will be 8 times that for final sum generation

 

---

The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 44-bit adder with S3,S2,S1,S0S3​,S2​,S1​,S0​ and C4C4​ as  its outputs are respectively: i do not understand these . here what is c4 please explain me

 

Answer 1

$C1 = G0 + C0.P0$

$C2 = G1 + G0.P1 + C0.P0.P1$

$C3 = G2 + G1.P2 + G0.P1.P2 + C0.P0.P1.P2$

$C4 = G3 + G2.P3 + G1.P2.P3 + G0.P1.P2.P3 + C0.P0.P1.P2.P3$  // read $C4$ as:

Carry is generated in $3^{rd}$ stage OR

Carry is generated in $2^{nd}$ stage AND propagated through $3^{rd}$ stage OR

Carry is generated in $1^{st}$ stage AND propagated through $2^{nd}$, $3^{rd}$ stage OR

Carry is generated in $0^{th}$ stage AND propagated through $1^{st}, 2^{nd}, 3^{rd}$stage OR

Initial carry $C_{0}$ is propagated through $0^{th}, 1^{st}, 2^{nd}, 3^{rd}$stage.

 

• $1$ AND & $1$ OR gate for $C1$
• $2$ AND & $1$ OR gate for $C2$
• $3$ AND & $1$ OR gate for $C3$
• $4$ AND & $1$ OR gate for $C4$

 To implement the look-ahead carry generator, $10 \text{ AND & } 4 \text{ OR}$ gates are required.

Correct Answer: B.

Comments

If fan in of AND and OR gate is 2 then question will be more trickier and answer is 20 AND Gates, 10 OR Gates. Let’s see

For C1, one OR gate; For C2, two OR gates; For C3, three OR gates; For C4, four OR gates; So total 10 OR GATES. Now let’s look at AND Gates For 2 element product term, 1 AND gate; For 3 element product term, 2 AND gates; For 4 element product term, 3 AND gates; For 5 element product term, 4 AND gates; So including all C1, C2, C3, C4 we required 20 AND GATES.

---

why no one is checking s0,s1,s2,s3 AND, OR gates?? why only c1 to c4 gates are checked..

---

Because it's only asking about look-ahead carry(C4).

Answer 2

let the carry input be c0

Now,

c1 = g0 + p0c0 = 1 AND, 1 OR
c2 = g1 + p1g0 + p1p0c0
   = 2 AND, 1 OR

c3 = g2 + p2g1 + p2p1go + p2p1p0c0
   = 3 AND, 1 OR
c4 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0
   = 4 AND, 1 OR

So, total AND gates = 1+2+3+4 = 10 , OR gates = 1+1+1+1 = 4

So as a general formula we can observe that we need a total of ” n(n+1)/2 ” AND gates and “n” OR gates for a n-bit carry look ahead circuit used for addition of two binary numbers.

Comments

Why not 4 and gates be used here as every equation has only 1 and operation and 1 or operation ,

C1=g0+c0p0, 1 and gate

C2=g1+c1p1, 1 and gate as c1 is already available

Same way for other gates also

---

The question says that it is a 2 level implementation.

Also, in Look Ahead Carry Adder, all the carries are generated simultaneously. If we believe that C2 = G1 + C1.P1 & it requires 1 AND, 1 OR gate only, how did you get C1 ? For Ci+1 only Gi & Pi are available, not Ci ( otherwise it would be just same as Ripple adder ).

Answer 3

In a carry look ahead adder if we ignore input size of a gate, then to add two n bit numbers using CLA the total no of AND and OR gate required are as follows:

for C1= 1 OR + 1 AND; AS C1=C0*P0+G0

for C2=1 OR + 2 AND ; AS C2=C1*P1+G1=C0*P0*P1+G0*P1+G2

for C3=1 OR + 3AND;

.......

for Cn=1 OR + n AND

so total no of OR gates reduired is = n

and total no of AND gates required is = 1+2+3+....+n=n(n+1)/2

Answer 4

I have written down every detail of what the question is trying to tell, and how we are approaching it.

final answer: $B$

p.s.- A different variation of this would be if the gates had a limited fan-in

Answer 5

"Instead of any number of inputs if it was given as only 2 inputs to any gate allowed. " 

For 4 bit adder and when all Pi and Gi are available then 

Number of OR gates will be 10 

Number of AND gates will be 20 

Answer 6

For n bit carry look ahead adder, if there is no restriction on fan in of "and" and "or" gate then

Total number of "And" gate in carry generator block is : n( n+1)/2.

Total number of "OR" gate in carry generator block is : n

For this question, total number of AND gate req is (4*5)/2 = 10

Total number of OR gate req is 4.