# GATE2006-36

6.7k views

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:

1. $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}$
2. $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}$
3. $a_{2}+b_{2}+(a_{2}\oplus b_{2}) ( a_{1}+b_{1}+(a_{1}\oplus b_{1})+(a_{0}+b_{0}))$
4. $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}$

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

edited
5

please give it a look ,

c1=a0b0

c2= a1b1 + ( a1$\oplus$ b1) c1

c3= a2b2+ ( a2$\oplus$ b2) c

now replace caccordingly .

1
That's also correct. You are getting which option?
1
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 ) ?
1
Yes, because we just need a boolean function- if carry is there we need a 1, otherwise we need a 0.
0

@arjun sir

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

24

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$

3
My bad. Didn't even try to solve the terms :-)
0
How to get a1b1+a1'b1c1+a1b1'c1 ==a1b1+b1c1+a1c1  ?

Please expalin it.i am not able to get it?
0
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..
3
@ahul , solve using kmap
0
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$
0
i dont understand why they neglected C0 here i think it forms the basis of carry look ahead generator
1

C0  will be zero in case of addition.

(a0 ⨁ b0)C= 0.

0

WHY PREVIOUS CARRY IS NOT CONSIDERED?

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

(A) is correct option!

5

That simplification is bit tricky, instead we could also take

Ci = aibi + (ai + bi)ci-1

Here both + and ⊕ will work!

0

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

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

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=a0b0

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 a0 and b0 are =1

so C=a1b1 + (a1+b1)a0b0

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 a1 and b1 both are 1.

c) MSB of one of the digit is 1 and other MSB=0 and one of a1 , b1 is 1 and other 0 but LSB of both digit must be 1

so C= a2b2 + (a2+b2)a1b1 + (a2+b2)(a1+b1)a0b0

Check reason

–2
i learned the formula
C(i)=G(i)+P(i)C(i-1)
–1
cn ny talk about thiz reference

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.

1 vote

Option (a) is correct

## Related questions

1
8.3k views
Consider numbers represented in 4-bit Gray code. Let $h_{3}h_{2}h_{1}h_{0}$ be the Gray code representation of a number $n$ and let $g_{3}g_{2}g_{1}g_{0}$ be the Gray code of $(n+1)(modulo 16)$ ... $g_{3}(h_{3}h_{2}h_{1}h_{0})=\sum (0,1,6,7,10,11,12,13)$
We consider the addition of two $2's$ complement numbers $b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out by $c_{out}$ ... $c_{out}\oplus c_{n-1}$ $a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$
Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$ $x\bar{z}+xy+\bar{y}z$ $x\bar{z}+xy+\overline{yz}$ $xz+xy+\overline{yz}$ $xz+x\bar{y}+\bar{y}z$
You are given a free running clock with a duty cycle of $50\%$ and a digital waveform $f$ which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of $f$ by $180°$?