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

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.

Instead of any number of inputs if it was given as only 2 inputs to any gate allowed. What would have been the answer?

---

1)all Pi and Gi are available for the carry generator circuit

 2)the AND and OR gates can have any number of inputs.

We have to find the number of AND gates and OR gates needed to implement the look-ahead carry generator ?

just write equation in simple term and calculate AND  & OR

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

kiioo this is carry look ahead adder so if we don’t expand it and simply write like this

C3=G2+P2C2
C4=G3+P3C3

then it will be like ripple adder ,since you are  giving carry to next stage.

And regarding -For finding the no. of OR gates, we are not expanding the terms?

We are expanding terms for finding OR  (as well as AND).Just that AND and OR gates can have any number of inputs.so one OR gate is enough  taking all terms as input for finding Ci .

But to find Ci we need i And gates since there are i terms required to And

eg- c2 = g1 + p1g0(1^st And) + p1p0c0(2^nd And) But only one OR.

                        

 

---

What if asked for adder circuit??

---

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.

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