GATE CSE 2006 | Question: 36

Question

Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ the carry in, the function that represents the carry generate function when these two numbers are added is: 

• A. $a_{2}b_{2}+a_{2}a_{1}b_{1}+a_{2}a_{1}a_{0}b_{0}+a_{2}a_{0}b_{1}b_{0}+a_{1}b_{2}b_{1}+a_{1}a_{0}b_{2}b_{0}+a_{0}b_{2}b_{1}b_{0}$
• B. $a_{2}b_{2}+a_{2}b_{1}b_{0}+a_{2}a_{1}b_{1}b_{0}+a_{1}a_{0}b_{2}b_{1}+a_{1}a_{0}b_{2}+a_{1}a_{0}b_{2}b_{0}+a_{2}a_{0}b_{1}b_{0}$
• C. $a_{2}+b_{2}+(a_{2}\oplus b_{2}) ( a_{1}+b_{1}+(a_{1}\oplus b_{1})+(a_{0}+b_{0}))$
• D. $a_{2}b_{2}+\overline{a_{2}}a_{1}b_{1}+\overline{a_{2}a_{1}}a_{0}b_{0}+\overline{a_{2}}a_{0}\overline{b_{1}}b_{0}+a_{1}\overline{b_{2}}b_{1}+\overline{a_{1}}a_{0}\overline{b_{2}}b_{0}+a_{0}\overline{b_{2}b_{1}}b_{0}$

Comments

Remark:

$C_i=a_{i-1}b_{i-1} + \left(a_{i-1} \oplus b_{i-1} \right) C_{i-1}$ $,$  $i\geqslant1$  is equivalent to

$C_i=a_{i-1}b_{i-1} + \left(a_{i-1} + b_{i-1} \right) C_{i-1}$

---

To prove above equation, let’s take an example

For simplicity assume $C_1 = c_1$

Let $f(a_1,b_1,c_ 1)=a_1b_1 + \left(a_1 \oplus b_1 \right) c_ 1$

$\Rightarrow$ $f(a_1,b_1,c_ 1)=a_1b_1 + \overline {a_1}b_1c_1 + a_1\overline{b_1}c_1\\$

$\Rightarrow$ $f(a_1,b_1,c_ 1)=a_1b_1\overline{c_1} + a_1b_1c_1 + \overline {a_1}b_1c_1 + a_1\overline{b_1}c_1\\$

$\Rightarrow f(a_1,b_1,c_ 1)= \sum (3,5,6,7)$

After solving using K-Map you get $f=a_1b_1 + b_1c_1 + a_1c_1$

Answer 1

: For carry look ahead adder we know carry generate function—

Where

As we are having two 3 bits number to add so final carry out will be C3-

Putting value of Pi,Gi in 3

C3=(A2.B2)+(A1.B1)(A2+B2)+(A0.B0)(A1+B1)(A2+B2)                       (TAKING C0=0)

C3=A2.B2 +A1A2B1+A1B2B1+(A0B0)(A1A2+A1B2+B1A2+B1B2)

C3=A2B2+A1A2B1+A1B2B1+A0A1A2B0+A0A1B0B2+A0A2B1B0+A0B0B1B2

SO ANS IS (A) PART.

Comments

According to Carry look-ahead adder’s equation:

Pi = Ai $\bigoplus$ Bi

Gi = Ai.Bi

Can you explain how is, Pi = Ai + Bi?

Answer 2

Option (a) is correct