Jupyter at Bryn Mawr College |
|||
Public notebooks: /services/public/dblank / CS240 Computer Organization / 2015-Fall / Notes |
How do we represent data in a computer?
At the lowest level, a computer is an electronic machine.
Easy to recognize two conditions:
Could base state on value of voltage, but control and detection circuits more complex.
Consider these positions in a number system:
n^{3} | n^{2} | n^{1} | n^{0} |
d_{3} | d_{2} | d_{1} | d_{0} |
$$ d_3 \times n^3 + d_2 \times n^2 + d_1 \times n^1 + d_0 \times n^0 $$
Consider the number 350 in base 10 (radix 10). That is, n is 10, and thus:
$$ 0 \times n^3 + 3 \times n^2 + 5 \times n^1 + 0 \times n^0 $$
$$ 0 \times 1000 + 3 \times 100 + 5 \times 10 + 0 \times 1 $$
Consider the number 0110 in base 2 (radix 2). That is, n is 2, and thus:
$$ 0 \times n^3 + 1 \times n^2 + 1 \times n^1 + 0 \times n^0 $$
$$ 0 \times 8 + 1 \times 4 + 1 \times 2 + 0 \times 1 $$
or 6 in base 10.
To convert a base 10 number to base n, use the following algorithm:
%%python
def rep(digit):
if digit <= 9:
return str(digit)
elif digit == 10:
return "A"
elif digit == 11:
return "B"
elif digit == 12:
return "C"
elif digit == 13:
return "D"
elif digit == 14:
return "E"
elif digit == 15:
return "F"
else:
return "?"
number = 4096 * 15 + 256 * 15 + 16 * 15 + 15
base = 16
positions = 4
print("%d in base %d is: " % (number, base))
for i in range(positions - 1, -1, -1):
digit = (number // base ** i)
number = number - digit * base ** i
print(rep(digit), end="")
%%python
print(bin(14))
There are two categories of integers (whole numbers):
Unsigned integers are all positive, and thus you can use all bits to represent positive numbers.
Signed integers use a bit to represent whether the integer is positive or negative.
Number | Bits |
---|---|
0 | 0000 |
1 | 0001 |
2 | 0010 |
3 | 0011 |
4 | 0100 |
5 | 0101 |
6 | 0110 |
7 | 0111 |
8 | 1000 |
9 | 1001 |
10 | 1010 |
11 | 1011 |
12 | 1100 |
13 | 1101 |
14 | 1110 |
15 | 1111 |
What is the largest unsigned integer using 16 bits? Using 32 bits?
%%python
print(2 ** 4 - 1)
%%processing
println(pow(2, 4) - 1);
Unsigned integers are nice and simple. But, for much of what we want our LC-3 to do might involve negative numbers.
How can we represent negative numbers?
It could be completely arbitrary... but we want to keep the circuits as simple as we can make them. So, it makes sense to have patterns that we can take advantage of.
The simplest pattern (at least for humans) might be the "signed magnitude"... just use the left-most bit to mean negative.
Number | Bits |
---|---|
-7 | 1111 |
-6 | 1110 |
-5 | 1101 |
-4 | 1100 |
-3 | 1011 |
-2 | 1010 |
-1 | 1001 |
-0 | 1000 |
0 | 0000 |
1 | 0001 |
2 | 0010 |
3 | 0011 |
4 | 0100 |
5 | 0101 |
6 | 0110 |
7 | 0111 |
Number | Bits |
---|---|
-7 | 1000 |
-6 | 1001 |
-5 | 1010 |
-4 | 1011 |
-3 | 1100 |
-2 | 1101 |
-1 | 1110 |
-0 | 1111 |
0 | 0000 |
1 | 0001 |
2 | 0010 |
3 | 0011 |
4 | 0100 |
5 | 0101 |
6 | 0110 |
7 | 0111 |
However, we have to implement mathematics in a circuit (as we will see). We want that the Arithmetic and Logic Unit circuit to be able to add any two binary numbers and get the appropriate binary number.
What we want is that REPRESENTATION(a + b) == REPRESENTATION(a) + REPRESENTATION(b)
Problems with 1's complement and Signed magnitude:
Number | Bits |
---|---|
-8 | 1000 |
-7 | 1001 |
-6 | 1010 |
-5 | 1011 |
-4 | 1100 |
-3 | 1101 |
-2 | 1110 |
-1 | 1111 |
0 | 0000 |
1 | 0001 |
2 | 0010 |
3 | 0011 |
4 | 0100 |
5 | 0101 |
6 | 0110 |
7 | 0111 |
Consider:
Now, we have solved all of the negative zero issues.
What is the range of numbers represented in 16 bits using 2's complement?
Could be used just to indicate where a decimal place
Used to represent really big numbers and really small numbers.
Consider that we have 32 bits to use. The IEEE Standard for Floating Point Arithmetic defined the following representation:
Consider converting:
$$ -6 \dfrac{5}{8} $$
to IEEE floating-point representation.
n^{3} | n^{2} | n^{1} | n^{0} | Decimal | n^{-1} | n^{-2} | n^{-3} | n^{-4} | |
---|---|---|---|---|---|---|---|---|---|
d_{3} | d_{2} | d_{1} | d_{0} | . | d_{-1} | d_{-2} | d_{-3} | d_{-4} |
Just as before we see how many column values will go into a number, we continue for $n^{-1}$...
$$ 0 \times n^3 + 1 \times n^2 + 1 \times n^1 + 0 \times n^0 + 1 \times n^{-1} + 0 \times n^{-2} + 1 \times n^{-3} $$
$$ 0 \times 8 + 1 \times 4 + 1 \times 2 + 0 \times 1 + 1 \times \dfrac{1}{2} + 0 \times \dfrac{1}{4} + 1 \times \dfrac{1}{8} $$
or:
-0110.101
Move the decimal place to left or right to get a single 1 to the left of the decimal place. Count how many places and in which direction:
-0110.101
becomes:
-01.10101
with 2 moves (exponent).
2 + 127 = 129
which is:
100000001
in binary.
1 100000001 10101
and pad to a total of 32 bits:
1 100000001 10101000000000000000000
Consider:
00111101100000000000000000000000
Do the reverse:
Break into parts:
0 01111011 00000000000000000000000
It is positive!
Convert next 8 unsigned bits into decimal, and subtract 127:
01111011 is 123
123 - 127 = -4
Put a one in front of the last 23 bits:
1.00000000000000000000000
and move the decimal spot by the exponent. In this case, 4 places to the left:
0.000100000000000000000000000
Convert to decimal:
$$ 0 * \dfrac{1}{2} + 0 * \dfrac{1}{4} + 0 * \dfrac{1}{8} + 1 * \dfrac{1}{16} ... $$
$$
%%python
for i in range(0, 10, .1):
print(i)