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

$c_1=a_0 b_0$

$c_2 = a_1b_1 + a_1c_1 + b_1c_1$

$c_3=a_2b_2 + a_2c_2 + b_2c_2$
$\quad=a_2b_2 + a_2a_1b_1 + a_2a_1c_1 +a_2b_1c_1 + b_2a_1b_1 +b_2a_1c_1 + b_2b_1c_1$
$\quad= a_2b_2 + a_2a_1b_1 +a_2a_1a_0b_0 + a_2b_1a_0b_0 + b_2a_1b_1 + b_2a_1a_0b_0 +b_2b_1a_0b_0$

Option is A.

Considering the carry in function $c$, $c_1 = a_0b_0 + a_0c + b_0c$, but $c$ is missing in all options and hence ignored.

Comments

please give it a look , 

c₁=a₀b₀

c₂= a₁b₁ + ( a₁$\oplus$ b₁) c₁

c₃= a₂b₂+ ( a₂$\oplus$ b₂) c₂ 

now replace c₂ accordingly .

---

That's also correct. You are getting which option?

---

at first I also did what you did but the problem with it that you get C=11 or 1 but in 2nd one if the carry C will be 1 . Is it okay to have carry 11 ( 1st one will be neglected in that case ) ?

---

Yes, because we just need a boolean function- if carry is there we need a 1, otherwise we need a 0.

---

@arjun sir

why pi is taken as (ai + bi) , as it should be taken as (ai ⊕ bi)

---

It is ai ⊕ bi. But 

$a_1b_1 + \left(a_1 \oplus b_1 \right) c_ 1 = a_1b_1 + \overline {a_1}b_1c_1 + a_1\overline{b_1}c_1\\=a_1b_1 + b_1c_1 + a_1c_1$

---

My bad. Didn't even try to solve the terms :-)

---

How to get a1b1+a1'b1c1+a1b1'c1 ==a1b1+b1c1+a1c1  ?

Please expalin it.i am not able to get it?

---

Just seeing a normal adder and how carry term is formed from lowest position on ward.

xyz + abc- we get carry if z and c are 1, and so on..

---

@ahul , solve using kmap

---

Is there any well known boolean rule to directly reduce

$a_1b_1 + \overline {a_1}b_1c_1 + a_1\overline{b_1}c_1\\=a_1b_1 + b_1c_1 + a_1c_1$

---

i dont understand why they neglected C0 here i think it forms the basis of carry look ahead generator

---

C₀  will be zero in case of addition.

(a0 ⨁ b0)C₀  = 0.

---

WHY PREVIOUS CARRY IS NOT CONSIDERED?

 

---

how c1 = a0b0 ...rather  it should be c1 = G0 + P0C0

---

$a_1b_1 + \left(a_1 \oplus b_1 \right) c_ 1$

$= a_1b_1 + \overline {a_1}b_1c_1 + a_1\overline{b_1}c_1\\$

$=a_1b_1 + b_1c_1 + a_1c_1$

To solve above boolean expression use K-Map method.

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 you get $f=a_1b_1 + b_1c_1 + a_1c_1$

---

It is not the case that: Co is missing in all options and hence ignored. Co=0 that’s why it’s not written.

Answer 2

(A) is correct option!

Comments

That simplification is bit tricky, instead we could also take

C_i = a_ib_i + (a_i + b_i)c_i-1

Here both + and ⊕ will work!

---

How did you simplify c3 = a2b2+ (a2 xor b2)c2 TO c3 = a2b2 + a2c2 + b2c2 ?

 

---

He has shown the steps in c2. Use similar pattern.

---

@vishal

$C_i=a_ib_i + \left(a_i + b_i \right) C_{i-1}$

I think above equation is wrong.

Correct one is

$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}$

Answer 3

First we have to know how carry can be generated.

1) If we add 2-bits carry can only be generated if both digits are 1.

so c=a₀b₀

---

2) If we add two 2-bit numbers then carry can be generated in two cases ,

a)MSB of both number is 1 

b)One MSB is 0 and Other one is 1 and both a₀ and b₀ are =1

so C=a₁b₁ + (a₁+b₁)a₀b₀

---

3) If we add two 3-bit numbers then carry can be generated in 3 cases ,

a) MSB of both numbers is = 1

b) MSB of one of the digit is 1 and a₁ and b₁ both are 1.

c) MSB of one of the digit is 1 and other MSB=0 and one of a₁ , b₁ is 1 and other 0 but LSB of both digit must be 1

so C= a₂b₂ + (a₂+b₂)a₁b₁ + (a₂+b₂)(a₁+b₁)a₀b₀  

Answer 4

Check reason

Comments

i learned the formula
C(i)=G(i)+P(i)C(i-1)

---

cn ny talk about thiz reference

---

@Wanted

it should be , $C_{i+1} = G_{i} + P_{i}C_{i}$

 $Gi = AiBi$  and  $Pi = Ai \bigotimes Bi$ ,  substitute.