Exercise

Symbol Probability

A 1 /2³

B 1 / 2⁴

C 1 / 2⁴

D 1 / 2³

E 1 / 2¹

F 1 / 2⁴

G 1 / 2⁴

Symbol Probability

E 1 / 2¹

A 1 /2³

D 1 / 2³

F 1 / 2⁴

G 1 / 2⁴

B 1 / 2⁴

C 1 / 2⁴

Symbol Probability

E 1 / 2¹

A 1 /2³

D 1 / 2³

[B,C] 1 / 2³

[F,G] 1 / 2³

Symbol Probability

E 1 / 2¹

[[B,C],[F,G]] 1 / 2²

[A,D] 1 /2²

Symbol Probability

E 1 / 2¹

[[[B,C],[F,G]],[A,D]] 1 / 2¹

Symbol Code

E 0

[[[B,C],[F,G]],[A,D]] 1

Symbol Code

E 0

[[B,C],[F,G]] 10

[A,D] 11

Symbol Code

E 1

[B,C] 100

[F,G] 101

A 110

D 111

Symbol Code

E 1

B 1000

C 1001

F 1010

G 1011

A 110

D 111

Comments:

The code is balanced in terms of 1s and 0 s

Note that: p_F ≤ p_H = p_C ≤ p_B = p_D ≤ p_G ≤ p_A ≤ p_E
and l _F ≥ l _H ≥ l _C ≥ l_B ≥ l _D ≥ l _G ≥ l _A ≥ l _E (length)

There are two codes of longest length, in this case 5. This is not a coincidence thought there may be more than two of longest length.

Huffman's Algorithm produces code that is best possible in a very important sense. We will come to understand the meaning of the previous sentence in the next few weeks. However, in the case where all probabilities are of the form 1/2ⁱ the nature of the argument is particularly transparent. We do some of the necessary arithmetic below.

Lemma: Suppose we have a set of letters {a_1, a_2,.......,an } and Probability(a_i) =1/2^l_i where l _i is an integer greater than 0, then

if l = max( l_1, l_2,.......,ln ) then there are an even number of letters with Probability(a_i) =1/2^l.

Proof:
Exercise: Remember

\sum

1/2^l_i= 1

Theorem: Suppose we have a set of letters {a_1, a_2,.......,an } and Probability(a_i) =1/2^l_i where l _i is an integer greater than 0, then in the associated Huffman Code, the length of the code for a_i is l _i.

Proof:
Exercise: This is an induction argument. Start with {a_1, a₂} then, assuming an-1 and an are letters of lowest probability look at the Huffman Code for {a_1, a_2,.......[an-1 ,an ]}
_____________________________________________________________________________

Shannon's First Big Theorem: In terms of expected length of an encoded string of letters, you can't do any better.