In this arithmetic, positive numbers are coded using their binary repre- sentation. For example, using 3 bits, we can represent numbers from 0 to 7 as
0 1 2 3 4 5 6 7
-+----+----+----+----+----+----+----+- 000 001 010 011 100 101 110 111
Thus, with 8 bits the numbers represented can be 0 to 255, with 10 bits we can represent the numbers from 0 to 1023, and with 16 bits the range covered is 0 to 65535. For negative numbers, the following three formats are used: sign-magnitude, one’s-complement, and two’s-complement.
Sign-magnitude format In this format, positive numbers are repre- sented using bits as before. However, the leftmost bit (also known as the most-significant bit or MSB) is used as the sign bit (0 is +, and 1 is−), and the remaining bits hold the absolute magnitude of the number as shown here:
Sign Bit
-+ Absolute Magnitude +---+---+
| | |
+---+---+
This system has thus two different codes for 0, one for the positive 0, the other one for the negative 0. For example, using 3 bits, we can represent numbers from−3 to 3 as
-3 -2 -1 -0 0 1 2 3
-+----+----+----+----+----+----+----+- 111 110 101 100 000 001 010 011
Thus, 8 bits cover the interval [−127,+127], while 16 bits cover [−32,767, +32,767]. If we use B bits in the sign-magnitude format, then we can represent integers from−(2B−1−1) to +(2B−1−1) only.
This format has two drawbacks. First, there are two representations for 0. Second, the arithmetic using sign-magnitude format requires one
rule to compute addition, another rule to compute subtraction, and a way to compare two magnitudes to determine their relative value before subtraction.
MATLAB Implementation MATLAB is a 64-bit floating-point com- putation engine that provides results in decimal numbers. Therefore, fixed-point binary operations must be simulated in MATLAB. It provides a function, dec2bin, to convert a positive decimal integer into a B-bit representation, which is a symbol (or a code) and not a number. Hence it cannot be used in computation. Similarly, the functionbin2dec con- verts aB-bit binary character code into a decimal integer. For example, dec2bin(3,3) gives011 and bin2dec(’111’)results in 7. To obtain a sign-magnitude format, a sign bit must be prefixed. Similarly, to convert a sign-magnitude format, the leading bit must be used to impart a positive or negative value. These functions are explored in Problem P9.1.
One’s-complement format In this format, the negation (or comple- mentation) of an integerxis obtained by complementing every bit (i.e., a 0 is replaced by 1 and a 1 by 0) in the binary representation ofx. Suppose theB-bit binary representation of xis bB−1bB−2 ã ã ãb0; then the B-bit one’s-complement, ¯x, ofxis given by
¯
x= ¯bB−1¯bB−2ã ã ã¯b0
where each bit ¯bi is a complement of bitbi. Clearly then
x+ ¯x≡1 1. . . 1 = 2B−1 (6.29) The MSB of the representation once again represents the sign bit, because the positive integer has the MSB of 0 so that its negation (or a negative integer) has the MSB of 1. The remaining bits represent either the number x (if positive) or its one’s-complement (if negative). Thus, using (6.29) the one’s-complement format representation2is given by
x(1)=∆
x, x≥0
|x|, x <0=
x, x≥0 2B−1− |x|, x <0=
x, x≥0 2B−1 +x, x <0 (6.30) Clearly, ifB bits are available, then we can represent only integers from (−2B−1+1) to (+2B−1−1), which is similar to the sign-magnitude format.
2The one’s-complement format refers to the representation of positive and negative numbers, whereas the one’s-complement of a number refers to the negation of that number.
For example, using 3 bits, we can represent numbers from−3 to 3 as
-3 -2 -1 -0 0 1 2 3
-+----+----+----+----+----+----+----+- 100 101 110 111 000 001 010 011
which is a different bit arrangement for negative numbers compared to the sign-magnitude format.
The advantage of this format is that subtraction can be achieved by adding the complement, which is very easy to obtain by simply comple- menting a number’s bits. However, there are many drawbacks. There are still two different codes for 0. The addition is a bit tricky to implement, and overflow management requires addition of the overflow bit to the least significant bit (or 20).
MATLAB Implementation The 1s-complement of a positive in- teger x using B bits can be obtained by using the built-in function bitcmp(x,B), which complements the number’s bits. The result is a dec- imal number between 0 and 2B−1. As before, thedec2bin can be used to obtain the binary code. Using (6.30), we can develop the MATLAB function, OnesComplement, which obtains the one’s-complement format representation. It uses the sign of a number to determine when to use one’s-complement and can use scalar as well as vector values. The result is a decimal equivalent of the representation.
function y = OnesComplement(x,B)
% y = OnesComplement(x,B)
% ---
% Decimal equivalent of
% Sign-Magnitude format integer to b-bit Ones’-Complement format conversion
%
% x: integer between -2^(b-1) < x < 2^(b-1) (sign-magnitude)
% y: integer between 0 <= y <= 2^b-1 (1’s-complement) if any((x <= -2^(B-1) | (x >= 2^(B-1))))
error(’Numbers must satisfy -2^(B-1) < x < 2^(B-1)’) end
s = sign(x); % sign of x (-1 if x<0, 0 if x=0, 1 if x>0) sb = (s < 0); % sign-bit (0 if x>=0, 1 if x<0));
y = (1-sb).*x + sb.*bitcmp(abs(x),B);
EXAMPLE 6.11 Using the functionOnesComplement, obtain one’s-complement format represen- tation of integers from−7 to 7 using 4 bits.
Solution MATLAB script:
>> x = -7:7 x =
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
>> y = OnesComplement(x,4) y =
8 9 10 11 12 13 14 0 1 2 3 4 5 6 7
Note that the number 15 is missing since we do not have −0 in our original
array.
Two’s-complement format The disadvantage of having two codes for the number 0 is eliminated in this format. Positive numbers are coded as usual. TheB-bit two’s-complement, ˜x, of a positive integerxis given by
˜
x= ¯x+ 1 = 2B−x or x+ ˜x= 2B (6.31) where the second equality is obtained from (6.30). Once again, the MSB of the representation provides the sign bit. Thus, using (6.31) the two’s-complement format representation3is given by
x(2)=
x, x≥0
|˜x|, x <0=
x, x≥0 2B− |x|, x <0=
x, x≥0
2B+x, x <0 (6.32) Thus, inB-bit two’s-complement format negative numbers are obtained by adding 2B to them. Clearly, ifBbits are available, then we can repre- sent 2Bintegers from (−2B−1) to (+2B−1−1). For example, using 3 bits, we can represent numbers from−4 to 3 as
-4 -3 -2 -1 0 1 2 3
-+----+----+----+----+----+----+----+- 100 101 110 111 000 001 010 011
This format, by shifting to the right (e.g., by incrementing) the code of the negative numbers, straightforwardly removes the problem of having 2 codes for 0 and gives access to an additional negative number at the left of the line. Thus, 4 bits go from−8 to +7, 8 bits cover the interval [−127,+127] and 16 bits cover [−32768,+32767].
3Again, the two’s-complement format refers to the representation of positive and neg- ative numbers, whereas the two’s-complement of a number refers to the negation of that number.
MATLAB Implementation Using (6.32), we can develop the MATLAB function,TwosComplement, which obtains the two’s-complement format representation. We can use thebitcmpfunction and then add one to the result to obtain the two’s-complement. However, we will use the last equality in (6.32) to obtain the two’s-complement since this approach will also be useful for fractional numbers. The function can use scalar as well as vector values. The result is a decimal equivalent of the two’s- complement representation. As before, thedec2bincan be used to obtain the binary code.
function y = TwosComplement(x,b)
% y = TwosComplement(x,b)
% ---
% Decimal equivalent of
% Sign-Magnitude format integer to b-bit Ones’-Complement format conversion
%
% x: integer between -2^(b-1) <= x < 2^(b-1) (sign-magnitude)
% y: integer between 0 <= y <= 2^b-1 (2’s-complement) if any((x < -2^(b-1) | (x >= 2^(b-1))))
error(’Numbers must satisfy -2^(b-1) <= x < 2^(b-1)’) end
s = sign(x); % sign of x (-1 if x<0, 0 if x=0, 1 if x>0) sb = (s < 0); % sign-bit (0 if x>=0, 1 if x<0));
y = (1-sb).*x + sb.*(2^b+x); % or y = (1-sb).*x + sb.*(bitcmp(abs(x),b)+1);
EXAMPLE 6.12 Using the functionTwosComplement, obtain the two’s-complement format rep- resentation of integers from−8 to 7 using 4 bits.
Solution MATLAB script:
>> x = -8:7 x =
-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
>> y = TwosComplement(x,4) y =
8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7
>> y = dec2bin(y,4); disp(sprintf(’%s’,[y’;char(ones(1,16)*32)]))
1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 The two’s-complement format has many interesting characteristics and advantages. These will be given after we discuss the next format, namely the ten’s-complement.
Ten’s-complement format This is a representation for decimal inte- gers. We will describe it so that we can explore characteristics of two’s- complement through decimal integers, which is much easier to understand.
Following (6.31), theN-digit ten’s-complement of a positive integerxis given by
˜
x= 10N−x or x+ ˜x= 10N (6.33) Using (6.33), theN-digit ten’s-complement format representation is given by
x(10N)=∆
x, x≥0
|˜x|, x <0=
x, x≥0 10N− |x|, x <0=
x, x≥0
10N+x, x <0 (6.34) Thus, in N-digit ten’s-complement format (which is sometimes re- ferred to as 10N-complement format), negative numbers are obtained by adding 10N to them. Clearly, when N digits are available, we can repre- sent 10N integers from (−102N) to (+102N −1). For example, using 1 digit, we can represent numbers from−5 to 4 as
-5 -4 -3 -2 -1 0 1 2 3 4
-+----+----+----+----+----+----+----+----+----+
5 6 7 8 9 0 1 2 3 4
EXAMPLE 6.13 Using the 2-digit ten’s-complement, i.e., 100s-complement format, perform the following operations:
1. 16−32, 2. 32−16, 3.−30−40, 4. 40 + 20−30, 5.−40−20 + 30.
Solution 1. 16−32
First we note that 16−32 = −16. If we use the usual subtraction rule to proceed from right to left generating carries in the process, we cannot complete the operation. To use the 100s-complement format, we first note that in the 100s-complement format we have
16(100)= 16, −16(100)= 100−16 = 84, and −32(100)= 100−32 = 68 Hence 16−32 ≡ 16 + 68 = 84 ≡ −16 in the sign-magnitude format as expected.
2. 32−16
In this case the 100s-complement format gives 32 + 84 = 116≡16
in the sign-magnitude format by ignoring the generated carry digit. This is because the sign bits were different; therefore, the operation cannot generate an overflow. Hence, we check for overflow only if the sign bits are same.
3. −30−40
In this case the 100s-complement format gives
(100−30) + (100−40) = 70 + 60 = 130
Since the sign bits were the same, an overflow is generated and the result is invalid.
4. 40 + 20−30
This is an example of more than one addition or subtraction. Since the final result is well within the range, the overflow can be ignored—that is,
40 + 20 + (100−30) = 40 + 20 + 70 = 130≡30 which is a correct result.
5. −40−20 + 30 In this case, we have
(100−40) + (100−20) + 30 = 60 + 80 + 30 = 170≡ −30
in the sign-magnitude format, which is, again, a correct result.
MATLAB Implementation Using (6.34), one can develop the MATLAB function, TensComplement, which obtains ten’s-complement format representation. It is similar to theTwosComplementfunction and is explored in Problem P6.25.
Advantages of two’s-complement format Using the results of the Example 6.13, we now state the benefits of the two’s-complement format.
These also hold (with obvious modifications) for the ten’s-complement format.
1. It provides for all 2B+1 distinct representations for aB-bit fractional representation. There is only one representation for zero.
2. This complement is compatible with our notion of negation: the com- plement of a complement is the number itself.
3. It unifies the subtraction and addition operations (subtractions are essentially additions).
4. In a sum of more than two numbers, the internal overflows do not affect the final result so long as the result is within the range (i.e., adding two positive numbers gives a positive result, and adding two negative numbers gives a negative result).
Hence in most A/D converters and processors, negative numbers are rep- resented using two’s-complement format. Almost all current processors implement signed arithmetic using this format and provide special func- tions (e.g., an overflow flag) to support it.
Excess-2B−1 format This format is used in describing the exponent of floating-point arithmetic; hence it is briefly discussed here. In excess- 2B−1 signed format (also known as a biased format), all positive and
negative integers between−2B−1 and 2B−1−1 are given by x(e)
∆= 2B−1+x (6.35)
For example, using 3 bits, we can represent the numbers from−4 to 3 as
-4 -3 -2 -1 0 1 2 3
-+----+----+----+----+----+----+----+- 000 001 010 011 100 101 110 111
Notice that this format is very similar to the two’s-complement format, but the sign bit is complemented. The arithmetic for this format is similar to that of the two’s-complement format. It is used in the exponent of floating-point number representation.
6.6.2 GENERAL FIXED-POINT ARITHMETIC