GATE CSE 2006 | Question: 39

Question

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}$. Which one of the following options correctly identifies the overflow condition?

• A. $ c_{out}\left( \overline{a_{n-1}\oplus b_{n-1}} \right)$
• B. $ a_{n-1}b_{n-1}\overline{c_{n-1}}+\overline{a_{n-1}}\overline{b_{n-1}}c_{n-1}$
• C. $ c_{out}\oplus c_{n-1}$
• D. $ a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$

Comments

thanks to point out ..i was stucked why option c is not correct

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

---

thanks i made the same mistake

Answer 1

Number representation in 2's complement representation:

• Positive numbers as they are
• Negative numbers in $2's$ complement form.

So, the overflow conditions are

1. When we add two positive numbers (sign bit $0$) and we get a sign bit $1$
2. When we add two negative numbers (sign bit $1$) and we get sign bit $0$
3. Overflow is relevant only for signed numbers and carry is used for unsigned numbers
4. When the carryout bit and the carryin to the most significant bit differs

PS: When we add one positive and one negative number we won't get a carry. Also points $1$ and $2$ are leading to point $4$.

Now the question is a bit tricky. It is actually asking the condition of overflow of signed numbers when we use an adder which is meant to work for unsigned numbers.

So, if we see the options, B is the correct one here as the first part takes care of case 2 (negative numbers) and the second part takes care of case 1 (positive numbers) - point 4.  We can see counterexamples for other options:

A - Let $n=4$ and we do $0111 + 0111 = 1110$. This overflows as in $2's$ complement representation we can store only up to $7$. But the overflow condition in A returns false as $c_{out} = 0$.

$C$ - This works for the above example. But fails for   $1001 + 0001 = 1010$ where there is no actual overflow $(-7+1 = -6)$, but the given condition gives an overflow as $c_{out} =0$ and $c_{n-1} = 1$.

D - This works for both the above examples, but fails for $1111 + 1111 = 1110$ $(-1 + -1 = -2)$ where there is no actual overflow but the given condition says so.

Reference: http://www.mhhe.com/engcs/electrical/hamacher/5e/graphics/ch02_025-102.pdf

Thanks, @Dilpreet for the link and correction.

Comments

1001+0001=1010

1+0=1

So, cn−1=1. obviously true

---

The sum is denoted by $c_{n−1}c-{n−2}…c_{0}$

actually the sum is denoted by $s_{n-1 }s_{n-2}....s_{0}$

 

that  is why c) wrong

refer https://gateoverflow.in/229829/%23number-system#c231333

---

perfecto

hehe

Answer 2

A'B'C+ABC'

Answer should be B. But I think there is a typo in B.

My answer:- A _N-1B _N-1C_N-1’ +  A _N-1’B _N-1’C_N-1

Comments

@krishn.jh

Please check Arjun Sir answer, he mentioned that

"Now the question is a bit tricky. It is actually asking the condition of overflow of signed numbers when we use an adder which is meant to work for unsigned numbers."

So we need to calculate the condition of overflow of signed numbers which I mentioned above.

---

@Kandula Tarun Reddy

Using Kmap. we need to draw a a Kmap for it.

	B'C'	B'C	BC	BC'
A'	0	1	0	0
A	0	0	0	1

---

@Kandula Tarun Reddy

Logic behind the truth table

0 = positive   1 = negative.

a n-1	b n-1	c n-1(result)	overflow(yes  = 1 or no = 0)
positive	positive	positive	no(2+1 = 3 = no overflow)
positive	positive	negative	yes
positive	negative	positive	no(e.g 5-4=1  = no overflow)
positive	negative	negative	no (4-5 = -1  = no overflow)
negative	positive	positive	no(-4+5 = 1 = no overflow)
negative	positive	negative	no(-5 +4 = -1 = no overflow)
negative	negative	positive	yes
negative	negative	negative	no(-3-2 = -5 = no overflow)

 

Answer 3

suppose i m taking two +ve no and two -ve no and we perform its addition in two's complement no 

+70		0	1	0	0	0	1	1	0
+80		0	1	0	1	0	0	0	0
add		1	0	0	1	0	1	1	0
	cout	msb	c(n-1)

_{here no carry is transfered to cout but c(n-1) is transfered to msb} 

-70		1	0	1	1	1	0	1	0
-80		1	0	1	1	0	0	0	0
add	1	0	1	1	0	1	0	1	0
	cout	msb	c(n-1)

here carry is transfered to cout and no c_{(n-1) is trasfered to msb}

_therefore,c_out' c_(n-1)+c_out c_(n-1)' =cout XOR C(n-1)

and another notable point is that there is no condition for overflow for +ve nd -ve no and also for -ve and +ve no

Answer 4

Option (c) is correct 

Answer 5

overflow in case of unsigned number

*overflow is case of unsigned number occurred if carry is produced. e.g(101+110=1011)

overflow in case of signed number

*overflow is occurred only if  M.S.B of two number is same and there result is different.

in case of two positive number M.S.B be one and M.S.B of there result is 0 if overflow occurred

which is written as  an-1 .bn-1.c'n-1

in case of two negative number M.S.B be 0 and M.S.B of there result is 1 if overflow occurred

which is written as a'n-1.b'n-1.cn-1 

in combined case of postive and negative number overflow occurred

Overflow Expression: a'n-1.b'n-1.cn-1 + an-1 .bn-1.c'n-1

 

Answer 6

It took me long to analyse but After reading Carl Hamacher, I understood that overflow is occured when we talk of signed numbers only. For unsigned numbers we have carry bit to take care of the stuff.

Example

     1011 (-5)

 +  1000 (-8)

1   0011

This example is for signed, but if you see if we neglect carry out Cout then also we see the sign of An-1 and Bn-1 and Cn-1

So clearly for the clarity whenever be it signed or unsigned, if sign of An-1 == sign of Bn-1 then overflow occurs if sign of Cn-1 is complement of An-1

 

C is correct