Visualizza wikitesto di No more secrets Part 8: More or Less? A trick to process signed numbers

At a first sight our row of adders seems to be able to perform the sum
operation only on natural numbers (or more precisely a finite initial
subset of the naturals including zero, as naturals are infinite).
I mean, how can we process negative numbers? Do we need a specific circuit?

The answer is "almost not". The same circuit is able to process positive
and negative numbers. Here the trick is build in mathematics rather than
electronics. Only a small specific circuit will be needed to compute
whether the computation generates an overflow or not.

We will consider half of the numbers as positive (or zero) and half as
negative. If we consider a suitable sorting sequence of the binary
configurations, the row of chained adders is already able to manage both
positive and negative numbers.

The 'suitable sequence' id the following one.

* all the numbers whose most significant bit (MBS) is zero are positive or zero and have the same encoding of the natural numbers, so a number whose MSB is zero and all the other bits are one is the maximum positive number
allowed in this encoding.

* all the numbers whose MSB is one are negative are negative. The number having all its bits set to one is -1, the previous number (all one but the last bit) is -2 and so on up to (in this case it should be better to say 'down to') the number having all the bits valued zero.

The following table shows the encoding for signed integer number under the
educational hypothesis of three or four bit wide numbers.
Three bits permit to encode numbers in the range -4, +3, the range of
a four bit integer is -8, +7.
In the real world integers are 16, 32, 64 or even 128 bit wide.
A 16 bit integer encode numbers in the range -32768, +32767,
a 32 bit integer range is: -2147483648, +2147483647.
It is useless to print here the ranges for larger integers, they are just
very long numbers. The basic point is that the idea presented here is
exactly the same used in the real Arithmetic and Logic Units (ALU)
in the processors (CPU) of our computer. The only difference is the number
of bits.

<pre>
3bits unsigned signed             4bits unsigned signed
000     0        0                0000      0       0
001     1        1                0001      1       1
010     2        2                0010      2       2
011     3        3                0011      3       3
100     4       -4                0100      4       4
101     5       -3                0101      5       5
110     6       -2                0110      6       6
111     7       -1                0111      7       7
                                  1000      8      -8
                                  1001      9      -7
                                  1010     10      -6
                                  1011     11      -5
                                  1100     12      -4
                                  1101     13      -3
                                  1110     14      -2
                                  1111     15      -1
</pre>

This encoding has several nice properties.

From the table it is possible to see that all the numbers in the
three bit encoding have the same representation when encoded using four
bits if we take into consideration only the three least significant bits.
If we want to convert a number encoded as 4-bit integer in one encoded
as 3-bit integer, it is sufficient to delete the MSB. If the number has
in the range allowed for a 3-bit number the resulting number represents
the same value.
The conversion of a 3-bit integer to a 4-bit integer is always possible but
it is a bit trickier: the missing MSB of the 4-bit encoding must have the
same value of the MSB of the 3-bit encoding.
<pre>
010 -> 0010
101 -> 1101
</pre>
In general to convert an n-bit integer into an m-bit integer:
* if n>m: delete n-m leading bits, if the original number is in the
range of an m-bits encoding both encodings represent the same number.
(the n-bit encoding should have n-m+1 leading bits having the same value,
i.e. n-m+1 leading zero bits or n-m+1 leading one bits)
* if n<m: copy the n bits of the n-bit encoding in the final, right-hand
side of the m-bit result. Set all the remaining bits of the results as
copies of the MSB/sign bit of the n-bit configuration.
<pre>
Examples:
conversion 8->4 bit:
00000110 is 6 -> 0110 is 6 (it is possible, it begins by five zeros)
11111011 is -5 -> 1011 is -5 (this time there are five ones)
00011000 is 24 the truncation gives a wrong result, 24 is not representable
in the range of a 4-bit integer, in fact there are ones and zeroes in the
first five bits of the number).

conversion 4->8 bits:
0100 is 4 -> 00000100 is 4
1110 is -2 -> 11111110 is -2
</pre>

The most important property of this encoding for negative numbers is that
we can sum unsigned and signed integers using the same circuit (provided we
do not take into account the final carry).

Let us try some sums using 4-bit signed numbers:
<pre>
4 + 2 -> 0100 + 0010 = 0110 -> 6
6 + (-2) -> 0110 + 1110 = (1)0100 -> 4
(-2) + (-3) -> 1110 + 1101 = (1)1011 -> -5
(-3) + 6 -> 1101 + 0110 = (1)0011 -> 3
</pre>

So, we don't need a different circuit to sum relative numbers, if we choose
this smart encoding for the negatives.
The same circuit does the same work, we just change the interpretation, i.e.
the meaning we give to each configuration of bits.

For the sake of completeness, there is one difference. The detection of the
overflow should be computed in a different way. By the way, an overflow
occurs when the result of a cumputation exceeds the range of the
representation for the number of bits provided for the result.

For unsigned integers an overflow occurs when the carry generated by the
adder of the MSB bit is one.
This is not the case for relative numbers, as we have seen in the examples
above that the MSB carry can be generated, in three out of four example
there has been a carry but all the results are correct, no overflow
occured.

The general rule is that there is an overflow of the sum between signed
numbers when (and only if) the XOR between the Cin and Cout bit of the
MSB is one.

It might be clearer using an example:
<pre>
4 + 2 -> 0100 + 0010 = 0110 (Cout = 0)
          100 +  010 =  110 (Cin = 0)  0 XOR 0 = 0 no overflow
6 + (-2) -> 0110 + 1110 = (1)0100 (Cout = 1)
             110 +  110 =  (1)100 (Cin = 1) 1 XOR 1 = 0 no overflow
(-2) + (-3) -> 1110 + 1101 = (1)1011 (Cout = 1)
                110 +  101 =  (1)011 (Cout = 1)  1 XOR 1 = 0 no overflow
(-3) + 6 -> 1101 + 0110 = (1)0011 (Cout = 1)
             101 +  110 =  (1)011 (Cout = 1)  1 XOR 1 = 0 no overflow
In fact these example are the same, and the results are correct.

6 + 4 -> 0110 + 0100 = 1010 (Cout = 0)
          110 + 0100 = (1)010 (Cin = 1) 0 XOR 1 = 1 overflow
in fact ten, the result is beyond the range of representation for a 4-bit
signed integer.
-7 + (-5) -> 1001 + 1011 = (1)0100 (Cout = 1)
              001 +  011 =  (0)100 (Cin = 0) 1 XOR 0 = 1 overflow.
-12 is not representable either.
</pre>