Binary Representation

We consider ways in which the computer might represent information.

Background

At the lowest level, computers represent every value (and every instruction) as a series of only two values. Why two? Because it turns out to be safest to distinguish between two states (e.g., high current and low current, or high magnetism and low magnetism). One of the interesting challenges in computing is how to represent more complex values, such as letters or numbers.

We almost always use 0 and 1 as the two values, and call them "bits" for "binary digits".

An Example: Representing Letters

Suppose we only use the letters e, g, i, l, n, r, and s in writing, and also spaces. Can we design a way to represent each letter as a sequence of 0's and 1's? Certainly. Here's one easy approach. We give each character a fout-bit representation and we ensure that they are all different.

Letter  Representation
-----   --------------
space   1111
e       0001
g       0010
i       0011
l       0100
n       0101
r       0110
s       0111

The word "grinnell" would then be represented as

00100110001101010101000101000100

Inserting spaces make it a little easier to see

0010 0110 0011 0101 0101 0001 0100 0100

Activities

Write the binary representation of is in using this model.

Decode the following

0111001101010010001101010010111101100011010100100111

Considering Binary Representations

• There are certainly other options for representing characters.
• What criteria might we use in choosing between representations (or in making our own)?

Non-Uniform Lengths

• What if you don't have to use the same number of bits for each letter?

• Here's a text to think about

  grinnellers sing in nine grinning rings

• Here's an analysis of letter frequency (I hope). Does it help?

  space 5 e 3 g 5 i 7 l 2 n 9 r 4 s 3

• If we can save one bit for n (9) by adding one to e (3) and l (2), we have a net reduction of 4 bits. (Hey, every little bit helps!)

Designing a New Representation

Spend a few minutes seeing if you can come up with a variable-length representation that will save us space, at least in representing this text.