## Sunday, April 3, 2011

### Computer Architecture # 02 : Data Representation : SIGNED FIXED POINT NUMBERS (8)

2.2.6 SIGNED FIXED POINT NUMBERS
Up to this point we have considered only the representation of unsigned ﬁxed point numbers. The situation is quite different in representing signed ﬁxed point numbers. There are four different ways of representing signed numbers that are commonly used: sign-magnitude, one’s complement, two’s complement, and excess notation. We will cover each in turn, using integers for our examples.

Throughout the discussion, the reader may wish to refer to Table 2.1 which shows for a 3-bit number how the various representations appear.

Table 2.1: 3-bit Integer Representations

Signed Magnitude
The signed magnitude (also referred to as sign and magnitude) representation is most familiar to us as the base 10 number system. A plus or minus sign to the left of a number indicates whether the number is positive or negative as in +1210 or −1210. In the binary signed magnitude representation, the leftmost bit is used for the sign, which takes on a value of 0 or 1 for ‘+’ or ‘−’, respectively. The remaining bits contain the absolute magnitude. Consider representing (+12)10 and (−12)10 in an eight-bit format:
(+12)10 = (00001100)2
(−12)10 = (10001100)2
The negative number is formed by simply changing the sign bit in the positive number from 0 to 1. Notice that there are both positive and negative representations for zero: 00000000 and 10000000.

There are eight bits in this example format, and all bit patterns represent valid numbers, so there are 28 = 256 possible patterns. Only 28 − 1 = 255 different numbers can be represented, however, since +0 and −0 represent the same number. We will make use of the signed magnitude representation when we look at ﬂoating point numbers in Section 2.3.

One’s Complement
The one’s complement operation is trivial to perform: convert all of the 1’s in the number to 0’s, and all of the 0’s to 1’s. See the fourth column in Table 2.1 for examples. We can observe from the table that in the one’s complement representation the leftmost bit is 0 for positive numbers and 1 for negative numbers, as it is for the signed magnitude representation. This negation, changing 1’s to 0’s and changing 0’s to 1’s, is known as complementing the bits. Consider again representing (+12)10 and (−12)10 in an eight-bit format, now using the one’s complement representation:
(+12)10 = (00001100)2
(−12)10 = (11110011)2
Note again that there are representations for both +0 and  −0, which are 00000000 and 11111111, respectively. As a result, there are only 28 − 1 = 255 different numbers that can be represented even though there are 28 different bit patterns.

The one’s complement representation is not commonly used. This is at least partly due to the difﬁculty in making comparisons when there are two representations for 0. There is also additional complexity involved in adding numbers, which is discussed further in Chapter 3.

Two’s Complement
The two’s complement is formed in a way similar to forming the one’s complement: complement all of the bits in the number, but then add 1, and if that addition results in a carry-out from the most signiﬁcant bit of the number, discard the carry-out. Examination of the ﬁfth column of Table 2.1 shows that in the two’s complement representation, the leftmost bit is again 0 for positive numbers and is 1 for negative numbers. However, this number format does not have the unfortunate characteristic of signed-magnitude and one’s complement representations: it has only one representation for zero. To see that this is true, consider forming the negative of (+0)10, which has the bit pattern:

(+0)10 = (00000000)2

Forming the one’s complement of (00000000)2 produces (11111111)2 and adding 1 to it yields (00000000)2, thus (−0)10 = (00000000)2. The carry out of the leftmost position is discarded in two’s complement addition (except when detecting an overﬂow condition). Since there is only one representation for 0, and since all bit patterns are valid, there are 28 = 256 different numbers that can be represented.

Consider again representing (+12)10 and (−12)10 in an eight-bit format, this time using the two’s complement representation. Starting with (+12)10 = (00001100)2, complement, or negate the number, producing (11110011)2. Now add 1, producing (11110100)2, and thus (−12)10 = (11110100)2:
(+12)10 = (00001100)2
(−12)10 = (11110100)2
There is an equal number of positive and negative numbers provided zero is considered to be a positive number, which is reasonable because its sign bit is 0. The positive numbers start at 0, but the negative numbers start at −1, and so the magnitude of the most negative number is one greater than the magnitude of the most positive number. The positive number with the largest magnitude is +127, and the negative number with the largest magnitude is −128. There is thus no positive number that can be represented that corresponds to the negative of −128. If we try to form the two’s complement negative of −128, then we will arrive at a negative number, as shown below:

The two’s complement representation is the representation most commonly used in conventional computers, and we will use it throughout the book.

Excess Representation
In the excess or biased representation, the number is treated as unsigned, but is “shifted” in value by subtracting the bias from it. The concept is to assign the smallest numerical bit pattern, all zeros, to the negative of the bias, and assign the remaining numbers in sequence as the bit patterns increase in magnitude. A convenient way to think of an excess representation is that a number is represented. as the sum of its two’s complement form and another number, which is known as the “excess,” or “bias.” Once again, refer to Table 2.1, the rightmost column, for examples.

Consider again representing (+12)10 and (−12)10 in an eight-bit format but now using an excess 128 representation. An excess 128 number is formed by adding 128 to the original number, and then creating the unsigned binary version. For (+12)10, we compute (128 + 12 = 140)10 and produce the bit pattern (10001100)2. For (−12)10, we compute (128 + −12 = 116)10 and produce the bit pattern (01110100)2:
(+12)10 = (10001100)2
(−12)10 = (01110100)2

Note that there is no numerical signiﬁcance to the excess value: it simply has the effect of shifting the representation of the two’s complement numbers. There is only one excess representation for 0, since the excess representation is simply a shifted version of the two’s complement representation. For the previous case, the excess value is chosen to have the same bit pattern as the largest negative number, which has the effect of making the numbers appear in numerically sorted order if the numbers are viewed in an unsigned binary representation.

Thus, the most negative number is (−128)10 = (00000000)2 and the most positive number is (+127)10 = (11111111)2. This representation simpliﬁes making comparisons between numbers, since the bit patterns for negative numbers have numerically smaller values than the bit patterns for positive numbers. This is important for representing the exponents of ﬂoating point numbers, in which exponents of two numbers are compared in order to make them equal for addition and subtraction. We will explore ﬂoating point representations in Section 2.3.