Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS240 Computer Organization / 2015-Fall / Notes

1. Representing Information¶

How do we represent data in a computer?

At the lowest level, a computer is an electronic machine.

• works by controlling the flow of electrons

Easy to recognize two conditions:

1. presence of a voltage - we'll call this state "1"
2. absence of a voltage - we'll call this state "0"

Could base state on value of voltage, but control and detection circuits more complex.

• compare turning on a light switch to
• measuring or regulating voltage

After Gregory Byrd (North Carolina State University), Chris Wilcox, S. Rajopadhye (Colorado State University)

2. Representing numbers in different bases¶

2.1 Positional number systems¶

Consider these positions in a number system:

 n3 n2 n1 n0 d3 d2 d1 d0

$$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.

2.2 Converting to base n¶

To convert a base 10 number to base n, use the following algorithm:

In [4]:
%%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="")
65535 in base 16 is:
FFFF
In [53]:
%%python
print(bin(14))
0b1110

3. Data Types¶

3.1 Integers¶

There are two categories of integers (whole numbers):

• Unsigned integers
• Typically, each bit represents decreasing (from left to right) magnitudes of powers of 2
• Signed integers
• Signed magnitude
• 1's complement
• 2's complement

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.

3.1.1 Unsigned Integers¶

NumberBits
00000
10001
20010
30011
40100
50101
60110
70111
81000
91001
101010
111011
121100
131101
141110
151111

What is the largest unsigned integer using 16 bits? Using 32 bits?

In [58]:
%%python

print(2 ** 4 - 1)
15
In [ ]:
%%processing

println(pow(2, 4) - 1);

3.1.2 Signed Integers¶

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.

3.1.2.1 Signed Magnitude¶

The simplest pattern (at least for humans) might be the "signed magnitude"... just use the left-most bit to mean negative.

NumberBits
-71111
-61110
-51101
-41100
-31011
-21010
-11001
-01000
00000
10001
20010
30011
40100
50101
60110
70111

3.1.3 One's Complement¶

NumberBits
-71000
-61001
-51010
-41011
-31100
-21101
-11110
-01111
00000
10001
20010
30011
40100
50101
60110
70111

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:

• negative zero?
• 0001 + 1110 = 1111
• does 1111 == 0000? (one's complement); 1000 == 0000? (signed magnitude)

3.1.4 Two's Complement¶

NumberBits
-81000
-71001
-61010
-51011
-41100
-31101
-21110
-11111
00000
10001
20010
30011
40100
50101
60110
70111

Consider:

• no negative zero
• 0111 + 1000 = 1111... correct?

Now, we have solved all of the negative zero issues.

What is the range of numbers represented in 16 bits using 2's complement?

3.2 Floating Point Numbers¶

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:

• 1 bit for the sign (0 = positive, 1 = negative)
• 8 bits for exponent (offset by 127)
• 23 bits for precision (leading 1 assumed)

3.2.1 To IEEE format¶

Consider converting:

$$-6 \dfrac{5}{8}$$

to IEEE floating-point representation.

3.2.1.1 Convert to binary representation¶

 Decimal n3 n2 n1 n0 n-1 n-2 n-3 n-4 d3 d2 d1 d0 . 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

3.2.1.2 Normalize¶

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.

3.2.1.4 Combine, leaving off leading 1 of precision¶

1 100000001 10101

and pad to a total of 32 bits:

1 100000001 10101000000000000000000

3.2.2 From IEEE format¶

Consider:

00111101100000000000000000000000

Do the reverse:

3.2.2.1 First digit is sign¶

Break into parts:

0 01111011 00000000000000000000000

It is positive!

3.2.2.1 Next 8 bits is exponent, minus 127¶

Convert next 8 unsigned bits into decimal, and subtract 127:

01111011 is 123

123 - 127 = -4

3.2.2.1 Get precision¶

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} ...$$

3.2.2.1 All together¶

$$• \dfrac{1}{16}$$
In [7]:
%%python

for i in range(0, 10, .1):
print(i)
Traceback (most recent call last):
File "/usr/lib/python3.4/site-packages/metakernel-0.10.5-py3.4.egg/metakernel/magics/python_magic.py", line 63, in eval
exec(code.strip(), self.env)
File "<string>", line 1, in <module>
TypeError: 'float' object cannot be interpreted as an integer