Example: Shannon Coding

In this example, we illustrate that the code length for a codeword using the Shannon coding algorithm, must be . Consider the following table:

x	p(x)	F(x)	F(x)	l(x)	Codeword
1	0.1	0.1	0.05	5+1	000011
2	0.1	0.2	0.15	3+1	0010
3	0.7	0.9	0.55	1+1	10
4	0.1	1.0	0.95	1+1	11


Note that 2 bits are required for the last two codewords to maintain a prefix code.

The entropy for this source is 1.36 bits (it is highly predictable). The average codeword length is:

According to Eq. 5.74 (page 103) in the textbook, we showed:

for the Shannon code:

It is obviously sub-optimal compared to the Huffman code in this case.