Overflow Detection for AddersOverflow in UB additionOverflow in 2C additionA Simpler Formula for OverflowCase 1: 0 carried in, and 1 carried outCase 1: 1 carried in, and 0 carried outThe CircuitMisconceptions about OverflowOVERFLOWWhen adding numbers together using the 2's complement notation: Add the numbers together in the usual way as if they are just normal binary numbers. Whendealing with 2's complement, any bit pattern that has a sign bit of zero in other words, a positivenumber) is just the same as a normal binary number (you don't need to convert it back out of 2'scomplement in any way, just convert it straight into decimal as you would convert a normal binarynumber).If, on the other hand, the sign bit is 1, this means that the corresponding decimal numberis negative, and the bit pattern needs to be converted out of 2's complement before you canconvert it from binary into decimal.Look at the 2's complement tables below; notice how allnumbers from zero upwards are exactly the same as the usual binary representation for eachvalue. Only the negative values (i.e. all those bit patterns starting with a 1) do not correspond tothe usual binary representation, so they have to be converted from 2's complement notation intonormal binary before we can then convert them from binary to decimal. Two's complementusing patterns of length 3 and 4 are:Bit pattern Value represented0111 70110 60101 50100 40011 30010 20001 10000 01111 -11110 -21101 -31100 -41011 -51010 -61001 -71000 -8Bit pattern Value represented011 3010 2001 1000 0111 -1110 -2101 -3100 -4 -3 1101 -6 1010+______ +______ -9 10111 = +7 +5 0101 +6 0110+______ +______ +11 1011 = -5 -8 1000 -8 1000+______ +______ -16 10000 = +0 +7 0111 +7 0111+______ +______ +14 1110 = -2If an addition operation produces a result thatexceeds the range of the number system,overflow is said to occur. In the modularcounting representation shown above, overflowoccurs during the addition of positive numberswhen we count past +7. Addition of twonumbers with different signs can neverproduce overflow, but addition of two numbersof like sign can, as shown by the followingexamplesFortunately, there is a simple rule for detecting overflow in addition: an addition overflows if the signs of the addends are the same and the sign of the sum is different from the addend’s sign. The overflow rule is sometimes state in terms of carries generated during the addition operation: an addition overflows if the carry bits cin into and cout of the sign position are different. Overflow Detection for Adders In our discussion of ripple-carry adders, we said that the same adder that adds two k-bit UB bitstrings also adds two k-bit 2C bitstrings. That was one advantage of using 2C for signed int representation. However, detecting overflow is different for the two representations. We look adding additional logic to the ripple carry adder, which can detect overflow for UB addition and for 2C addition. Overflow in UB addition When adding two k-bit bitstrings using UB, you are adding two non-negative numbers. Let's call these numbers x and y. Since they are non-negative, then x + y >= x and x + y >= y. That is, adding two non-negative numbers either keeps the value the same, or increases it. Assuming both x and y are valid 2C bitstrings, then their sum overflows only if the result is larger than the largest positive integer. For k bits, the maximum value is 2k - 1. If a sum is larger than that, it overflows. When a sum is larger than 2k - 1, it takes k + 1 bits to represent the result. So, you can tell overflow just by checking if the carry out of the leftmost adder (which adds the most significant bits and the carry in) is 1. Here's how the circuit looks: The letter "V" is often used to represent the overflow bit. Presumably "O" is not used because it looks too much like the numeral 0. Overflow in 2C addition The condition for overflow is different if the bitstring representation is 2C. In particular, x + y >= x and x + y >= y are no longer necessarily true.Here are some facts about overflow in 2C. - If x and y have opposite signs (one is negative, the other is non-negative), then the sum will never overflow. Just try it out. The result will either be x or y or somewhere in between. - Thus, overflow can only occur when x and y have the same sign. - One way to detect overflow is to check the sign bit of the sum. If the sign bit of the sum does not match the sign bit of x and y, then there's overflow. This only makes sense. - Suppose x and y both have sign bits with value 1. That means, both representations represent negative numbers. If the sum has sign bit 0, then the result of adding two negative numbers has resulted in a non-negative result, which is clearly wrong. Overflow has occurred. - Suppose x and y both have sign bits with value 0. That means, both representations represent non-negative numbers. If the sum has sign bit 1, then theresult of adding two non-negative numbers has resulted in a negative result, whichis clearly wrong. Overflow has occurred. So that would suggest that one way to detect overflow is to look at the sign bits of the two most signicant bits and compare it to the sum. Let's derive a formula for this. Let's say we want to add two k bit numbers: xk-1...x0 and yk-1...y0. The sum is sk-1...s0. Thus, one formula for detecting overflow is: V = xk-1yk-1\sk-1 + \xk-1\yk-1sk-1 This formula basically says that overflow has occurred if the sign bit x and y are 1, and the sign bit of the sum is 0, or if the sign bit of x and y are 0, and the sign bit of the sum is 1. A Simpler Formula for Overflow However, there is an easier formula, though one that is more obscure. Let the carry out of the full adder adding the least significant bit be called c0. Then, the carry out of the full adder adding the next least significant bit is c1. Thus, the carry out of the full adder adding the most significant bits is ck - 1. This assumes that we are adding two k bit numbers. We can write the formula as: V = ck-1 XOR ck-2This is effectively XORing the carry-in and the carry-out of the leftmost