Continues on the next page!

(1)

582650 Information-Theoretic Modeling (Autumn 2012) Homework 3 (due 25 September)

You should turn in your solutions on paper at the start of the exercise session. For problem 3 and the bonus problem, send your code to Hannes Wettig by e-mail.

1. (Cover & Thomas, Ex5.3.) Consider a prexix codeC:X → {0,1}^∗where|X |=m, and assume the code lengths`1, . . . , `msatisfy

m

X

i=1

2^−`ⁱ <1

(i.e., the Kraft Inequality is not tight.) Show that there are arbitrarily long bit strings that are not codes for any sequence of symbols. That is, there is an infinite number of bit strings s∈ {0,1}^∗such that for allx1. . . xn ∈ X^∗we haveC^∗(x1. . . xn)6=s, whereC^∗is the extension ofC. (Hint: find a stringsthat is not a prefix of any codeword.)

2. Consider a source alphabet X = {x1, . . . , xm} of size m. Assume we are given propabilities p1, . . . , pm for the source symbols, so Pr[X = xi] = pi. Recall that the Shannon-Fano code works as follows:

(a) Sort the symbols according to decreasing probability so that we can assume p₁ ≥ p₂ ≥ . . .≥p_m.

(b) Initialize all codewordsw₁, . . . , w_mas the empty string.

(c) Split the symbols in two sets,(x₁, . . . , x_k)and(x_k+1, . . . , x_m), so that the total probabilities of the two sets are as equal as possible, i.e., minimize the difference|(p1+. . .+pk)−(pk+1+ . . .+pm)|.

(d) Add the bit ‘0’ to all codewords in the first set, wi 7→wi0, for all 1≤i≤k, and ‘1’ to all codewords in the second set, wi 7→wi1 for allk < i≤m.

(e) Keep splitting both sets recursively (Step (c)) until each set contains only a single symbol.

Simulate the Shannon-Fano code, either on paper or by computer, for a source with symbols A : 0.2, B : 0.22, C : 0.25, D : 0.15, E : 0.13, F : 0.05, where the numbers indicate the probabilitiespi.

3. Take a piece of text, estimate the symbol occurrence probabilities from it. Then use them to encode the text using the Shannon-Fano code (on a computer). Compare the code-length to the entropy of the symbol distributionH(X).

4. (Cover & Thomas, Ex5.12.) Consider a random variableX that takes on four values, a, b, c,!, with respective probabilities ¹₃,¹₃,¹₄,₁₂¹

.

(a) Construct a Huffman code for this random variable.

(b) Show that there exist two different sets of optimal (Huffman) lengths for the codewords;

namely, show that codeword length assignments(1,2,3,3)and(2,2,2,2)are both optimal.

(c) Conclude that there are optimal codes with code-word lengths for some symbols that exceed the Shannon code-length l

log₂_p(x)¹ m .

Continues on the next page!

(2)

5. Assume that a personxis picked at random according to distributionpfrom a finite population X. In order to identify x, you are allowed to ask an oracle a sequence of any yes—no questions like “Doesxbelong to the subsetSi={xi,1, xi,2, . . . , x_i,n(i)}?”.

(a) What is the optimal strategy if you want to minimize the expected number of questions required? What can you say about the expected number of questions that are required?

(Hint: the sequence of answers can be regarded as the codeword ofx.)

(b) What if the goal is to minimize theworst-case (maximum) number of questions?

Bonus problem. Implement the Hamming(7,4)code. The decoder should try to find a sequence of data bitsd₁, d₂, d₃, d₄ for which the difference between the received seven-bit sequence and the seven-bit codeword corresponding to the data bits is minimal (at most one bit). For example, in Lecture 2, the (Hamming) distance between the received sequence1111010and the codeword 1011010 is one, so that the data bits is decoded as 1011. Test your code by encoding the sequencerat.txt. Simulate the binary symmetric channel,p= 0.01, by saying ‘bsc.py 0.01’, then decode the noisy signal. You can create a PBM image file by the script ‘txt2pbm.py’. You can display a PBM file by ‘gimp file.pbm’. Compare the result with and without Hamming coding. Your experiment should be something like:

where encand dec are the encoding and decoding commands, respectively. The example file rat.txtand the scriptsbsc.pyandtxt2pbm.pyare available at the course web page.

Figure 1: ratnoisy.pbm

2