ISI-PCB-2015-C8-a

Question

Let $a_{n−1}a_{n−2}...a_0$ and $b_{n−1}b_{n−2}...b_0$ denote the $2’s$ complement representation of two integers $A$ and $B$ respectively. Addition of $A$ and $B$ yields a sum $S=s_{n−1}s_{n−2}...s_0.$ The outgoing carry generated at the most significant bit position, if any, is ignored. Show that an overflow (incorrect addition result) will occur only if the following Boolean condition holds:

$\overline{s}_{n-1}\oplus \; (a_{n-1}s_{n-1})\;=\;b_{n-1}(s_{n-1}\oplus a_{n-1})$

where $\oplus$ denotes the Boolean XOR operation. You may use the Boolean identity: $X+Y=X⊕Y⊕(XY)$ to prove your result.

Comments

Sorry. I have written 'c' by mistake. It is not carry. It represents sum. So, It should be $a_{n-1}b_{n-1}\overline{s_{n-1}}+\overline{a_{n-1}}*\overline{b_{n-1}}*s_{n-1}$

Well, I got the answer of this question.

Overflow occurs when 2 +ve integers are added and result is negative or  when 2 -ve integers are added and result is positive.

So, we make a truth table for $a_{n-1},b_{n-1},s_{n-1}$ and check when

1) $a_{n-1}=0,b_{n-1}=0,s_{n-1}=1$ then LHS=RHS or not for the given condition which is mentioned in the question.

2) $a_{n-1}=1,b_{n-1}=1,s_{n-1}=0$ then LHS=RHS or not for the given condition which is mentioned in the question.

Here LHS=RHS in both 2 cases, So given condition is correct for overflow. Though it is not formal way to prove it but it is one of the way to get the answer :P

---

$\overline{s}_{n-1}\oplus \; (a_{n-1}s_{n-1})\;=\;b_{n-1}(s_{n-1}\oplus a_{n-1})$

Now,

say $\overline{s}_{n-1}=b_{n-1}$

$b\oplus a.s=b\left ( s\oplus a \right )$

$\Rightarrow \left ( b\oplus a \right ).\left ( b\oplus s \right )=b.s\oplus b.a$

$\Rightarrow \left ( b\oplus a \right ).\left ( s'\oplus s \right )=s'.s\oplus b.a$

$\Rightarrow \left ( b\oplus a \right ).1=0\oplus b.a$

$\Rightarrow b'a'+ba=ba$

it is only possible when $b'a'=0$

---

@ankitgupta.1729
You're right.
Let

$\begin{align}\mathrm{L}&=\overline{s}_{n-1}\oplus \; (a_{n-1}s_{n-1})\\ \mathrm{R}&=b_{n-1}(s_{n-1}\oplus a_{n-1})\end{align}$

Now from the truth table of a full adder, we obtain

Row Serial #	$a_{n-1}$	$b_{n-1}$	$c_{n-1}$	$s_{n-1}$	$c_n$	$\mathrm{L}$	$\mathrm{R}$
1	0	0	0	0	0	1	0
2	0	0	1	1	0	0	0
3	0	1	0	1	0	0	1
4	0	1	1	0	1	1	0
5	1	0	0	1	0	1	0
6	1	0	1	0	1	1	0
7	1	1	0	0	1	1	1
8	1	1	1	1	1	1	0

 

Here, $\mathrm{L}=\mathrm{R}$ in the row #2 and the row #7 in which the overflow (error) occurs. It's because the sum is negative if $s_{n-1}=1$ and positive if $s_{n-1}=0$ even though $a_{n-1}=0,b_{n-1}=0$ (meaning positive sum) and $a_{n-1}=1,b_{n-1}=1$ (meaning negative sum) respectively.