in Digital Logic edited by
18,347 views
54 votes
54 votes

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?

  1. $ c_{out}\left ( \overline{a_{n-1}\oplus b_{n-1}} \right )$
  2. $ a_{n-1}b_{n-1}\overline{c_{n-1}}+\overline{a_{n-1}}\overline{b_{n-1}}c_{n-1}$
  3. $ c_{out}\oplus c_{n-1}$
  4. $ a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$
in Digital Logic edited by
18.3k views

4 Comments

$a_{n-1}, b_{n-1}$ represent the sign bits of first number and second number, $c_{n-1}$ represents the sign bit of the Sum of both numbers,
Case 1:
If two positive numbers(with sign bit 0) are added and the sign bit of sum is 1(-ve), then there is an overflow.

Case 2:
If two negative numbers(with sign bit 1) are added and the sign bit of sum is 0(+ve), then there is an overflow.

$Overflow : Case 1 + case 2 = a_{n-1}*b_{n-1}*c_{n-1}' + a_{n-1}'*b_{n-1}'*c_{n-1} $

Hence, option (B) is correct.

 

 

17
17

Overflow condition can be written in any of the three ways – 

  1. $C_{n} \oplus C_{n-1}=1$ which says that either 1st MSB or 2nd MSB should give carry but not both.
  2. $A_{n}B_{n}\bar{C_{n-1}} + \bar{A_{n}}\bar{B_{n}}C_{n-1}=1$ where $A_n$ and $B_n$ are the MSB (which are sign bits) and $C_{n-1}$ is the carry from the 2nd MSB.
  3. $A_{n}B_{n}\bar{R_{n}} + \bar{A_{n}}\bar{B_{n}}R_{n}=1$ where $R_{n}$ is the MSB (sign bit) of result of the addition.

From the third condition above, we can see that overflow will happen when:

 1. $A_n,B_n$ is 0 (which means positive numbers) and $R_n$ is 1 (which means a negative number).

2. $A_n,B_n$ is 1 (which means both are negative numbers) and $R_n$ 0 (which means a positive number).

Conclusion: For overflow to happen, two positive numbers are added and the result is negative OR two negative numbers are added and the result is positive.

PS: 2nd result can be derived from 1st result by replacing the value of $C_n$ with $A_nB_n + C_{n-1}(A_n \oplus B_n)$ and 3rd result can be derived from the 2nd result by thinking a bit. Let me know if you find it difficult to derive it.

3
3

6 Answers

64 votes
64 votes
Best answer

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.

edited by

4 Comments

1001+0001=1010

1+0=1

So, cn−1=1. obviously true

0
0

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

7
7
perfecto

hehe
0
0
27 votes
27 votes
A'B'C+ABC'

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

My answer:- A N-1B N-1CN-1’ +  A N-1’B N-1’CN-1

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

0
0

@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
0
0

@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)
       

 

0
0
6 votes
6 votes

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,cout' c(n-1)+cout 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

edited by
2 votes
2 votes

Option (c) is correct 

Answer:

Related questions