Mira Bernstein
Berkeley Math Circle
December 10, 2000

Information Theory

The Morse Code

Letter	Code	Duration
A	. -	3
B	- . . .	5
C	- . - .	6
D	- . .	4
E	.	1
F	. . - .	5
G	- - .	5
H	. . . .	4
I	. .	2
J	. - - -	7
K	- . -	5
L	- . - -	7
M	- -	4
N	- .	3
0	- - -	6
P	. - - .	6
Q	- - . -	7
R	- . -	5
S	. . .	3
T	-	2
U	. . -	4
V	. . . -	5
W	. - -	5
X	- . . -	6
Y	- . - -	7
Z	- - . .	6

(A dash lasts twice as long as a dot)

For more information about codes and information theory, see for example

www.data-compression.com

A few problems for exploration:

1. How many different maximal, instantaneous codes with $n$ words are there? By ``different'', I mean corresponding to different trees. Two trees are considered the same if one can be obtained from the other by any number of left-right flips. For example, the following codes with 4 words are all the same:
   0, 10, 110, 111
   0, 11, 100, 101
   1, 01, 000, 001
   1, 00, 010, 011

   Draw the trees, and you'll see what I mean. But this code is different:

   00, 01, 10, 11

   Can you figure out and prove a recursive formula for the number of maximal instantaneous codes with $n$ words? For help, you might consult the Online Encyclopedia of Integer Sequences:

   www.research.att.com/$\sim$njas/sequences

2. In class, we saw an example of an alphabet of five letters, with probabilities assigned in such a way that all three maximal instantaneous codes with 5 words worked equally well. Can you do this with an alphabet of 6 letters? More? (I do not know the answer to this question. If you figure it out, please email me: mira@math.berkeley.edu)

3. Is it possible to have an instantaneous code with codewords of length 1,2,3,5,5,5?

   How about 1,2,4,4,4,5,5?

   How about 1,3,3,4,4,4,5,5,5?

   How about 1,3,3,4?

   Of the possible codes, which ones are maximal? Can you formulate and prove a way to determine whether an instantaneous code with given lengths of codewords exists, and if so, whether it is maximal?