Problem 1
Interpret the following sequence of bits
as the encoding of an English word in ASCII. What is the word?
010110010110010101100011
Chop the sequence of bits into three pieces:
YEC? Shouldn't that have been YES? In fact, YEC is one bit away from being YES. If the 4th bit from the left in the 3rd word was a 1, rather than a 0, the word would decode as YES.
[Note: in this case, "Yec" isn't in Webster's 7th Collegiate Dictionary. Can you think of two words that do show up in the dictionary, and are but one bit apart? If so, then you've proven that the "distance" of the English "code" is 1 bit.]
Excess-16 notation is a method of encoding positive and negative integers in the range -16..15, using 5 bits. To encode a number in excess-16 notation, add 16 to it, then convert the result to binary. To convert back to decimal, convert from binary, then subtract 16 from the result.
[Note: why do we do this? Because computers are not good at storing negative numbers. We have to encode them. A natural way to do this is to add a large amount, in this case 16, so that every number gets blown up into a positive number. Then we store the positive number.]
So, for part (c), 01101 binary would normally convert to
8+4+1=13. But you subtract 16 to get 13-16= -3.
For part (e), 10111 binary converts to 16 + 4+2+1 = 23.
Subtracting 16 gives you 23-16 = 16 + 4+2+1 - 16 = 4+2+1 = 7.
In this problem, we use excess-4 notation. Same basic procedure, except you encode by adding a 4, rather than a 16.
For part (b) we want to encode 3. First we add 4 to
get 3+4=7, then encode the number 7 to binary: 7 = 4+2+1 = binary 111.
For part (c) we wish to encode -3. Again, we add 4 to
-3 to get 1, then encode the number 1 in binary: 1 (decimal) = binary
001.
[Note: how did we know to use 3 binary digits? Also, how did Brookshear know to use 5 binary digits in problem 36?]
A note on overflow: Overflow is not necessarily the occurrence of extra 1's . Several students declared that part (c) was an example of overflow. Let's do part c:
12 == 01100
-4 == 11100 <-- How do we know this? 4 normally encodes as
------------- 00100. To get -4, we complement the bits to get
101000 11011. then we add 1 to this, giving us
11100.
The result is 01000 That last 1 bit is chopped off, because we're using 5-bit arithmetic. Is this overflow? Well, the decimal value of 01000 is 8. 12-4=8. We got the right answer.
Overflow invariably results in the wrong answer. Sure, we had an extra 1, which we just threw away, and intuition suggests that we must have made a mistake by throwing away a digit! However, the procedure works. On the other hand, part (e):
12 == 01100
+4 == 00100
-------------
10000
Here we don't have any extra 1 bits falling off the left side. Yet, this is overflow. We add 12 and 4, and get ... negative 16. This is 2-s complement arithmetic, and that 1 on the far left indicates a negative number. An incorrect answer, due to overflow.
Finally, what happens when we subtract 12 from 4? That's the same as adding 4 and -12: 12 is binary 01100, the complement of 01100 is 10011, and adding 1 to this gives us 10100:
4 == 00100
-12 == 10100
-------------
11000
It's a negative number because of that left-most 1. Converting back, we complement the bits in 11000 to get 00111, then add 1 to get 01000: 8. So 11000 represents negative 8. Check: 4-12=-8, so overflow hasn't occurred.
(Part c) How would you represent -3.75 in binary? Well, 3 is binary 11, and .75 is 1/2 plus 1/4, or binary 0.11, so -3.75 is -11.11
Clearly that isn't all we need to do, because computers can't store negative numbers or decimals without some help in encoding them (See the note from problem 2, on excess-16 notation!) To encode this in Brookshear's floating point notation, we separate the exponent from the mantissa: 11.11 is .1111 times 2^2; in other words, it's .1111 with the point moved two digits to the right. We encode that 2 in excess-4 notation (Add 4, then convert the result to binary,) and finally throw in a 1 bit to indicate that it is negative. The result:
1 110 1111
| | |
| | Encoding of .1111
| |
| "2" in excess-4 notation. 2+4 is 6, 6 is binary 110
|
Sign bit: 1 means that the number is negative.
Part (e): 31/32 is 1/2+1/4+1/8+1/16+1/32, or binary 0.11111 Problem: this mantissa needs to be squeezed into four digits, and it apparently takes up five. What do we do? The only thing we can do: leave off the last digit. The answer:
0 100 1111
| | |
| | Encoding of .11111, with the rightmost bit lost
| |
| "0" in excess-4 notation. We don't move the radix point
|
Sign bit: 0 means that the number is positive.
If we decode this, we discover that we ended up with the number 15/16, rather than 31/32. That's as close as we can get with this floating point representation.
We want to represent metric measurements using floating point notation. Is this a good idea? Metric units are related by multiples of 10, meaning that any fraction will be in tenths, hundredths, thousandths.... all fractions which can not be represented in binary, with any finite number of digits. 1/10, for instance, is binary 0.000110011001100110011001100...., forever repeating. Any binary representation of a metric fraction will not be accurate for this reason.
110 centimeters is 1.1 meters, for instance. In Brookshear's notation, that comes out as .1000110011001100.. times 2^1, with all but the first 4 digits chopped off: 0 101 1000 Decoding, we see that we accidentally encoded the number 1! Off by a tenth! By the way, we couldn't encode it in centimeters either, since 110 can not even be stored in Brookshear's notation: the largest number you can store is 7.5 . However, the whole number 110 can be stored in 8-bit 2's complement, using the same number of bits but a different represention.
A table:
| In excess-16 | In 2s complement | |
|---|---|---|
| 01011 | -5 | 11 |
| 11011 | 11 | -5 |
What can we say? The value could be either 11 or -5.
What is the relationship between excess-16 and 2s complement? What pattern can we see? The obvious difference is that first bit. In excess-16, a leftmost 1 means the remaining bits should be interpreted as a positive number. In 2s complement, a 0 means the remainder should be treated as a positive number.
Here's the subtle part: adding a negative number to 16 is the same as subtracting a number from 16, which is the same as subtracting a number from 15, then adding 1. It so happens that subtracting a 4-bit number from 15 is the same as complementing the bits. An example:
1111
-0110 <-- Notice how no messy borrows occur, since
---- every digit in the top number has a '1' in it.
1001 So, every digit is simply flipped.
Similarly, in 5-bit 2s complement, we encode a negative number by complementing the 5-bit representation of its positive absolute value and adding 1, which is equivalent to adding that number to 32.
Putting this all together, we see that any 5-bit number with a leading 1 is either the 2's complement for some negative x, represented by the binary for 32+x, or the excess-16 for some positive number y represented by the binary for 16+y, and so y must be x +16. Similarly, any 5-bit number with a leading 0 is either the 2's complement for some positive number x, represented by the binary for x, or the excess-16 for some negative number y represented by the binary for 16+y. Again, x and y must differ by 16. So interpreting any 5-bit number as 2s complement versus excess-16 will always give numbers 16 apart.