World's most popular travel blog for travel bloggers.

# Problems with the proof of Huffman Optimality in Cover's book

, ,
Problem Detail:

There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me.

First question is why he assumes that we can "Consider an optimal code $C_m$. Is he assuming that we are encoding a finite number of words so that $\sum p_i l_i$ must have a minimum value? Here I give you the relevant snapshot.

Second, there is an observation made on this notes that was also done in my class before proving the theory of optimality of huffman codes, that is,

observe that earlier results allow us to restrict our attention to instantaneously decodeable codes

I don't really understand why this observation is necessary.

###### Answered By : Yuval Filmus

To answer your first question, the index $i$ goes over the range $1,\ldots,m$. The assumption is that there are finitely many symbols. While some theoretical papers consider encodings of countably infinite domains (such as universal codes), usually the set of symbols is assumed to be finite.

To answer your second question, the claim is that a Huffman code has minimum redundancy among the class of uniquely decodable codes. The proof of Theorem 10 in your notes, however, only directly proves that a Huffman code has minimum redundancy among the class of instantaneously decodable codes. It does so when it takes an optimal encoding for $p_1,\ldots,p_{n-2},p_{n-1}+p_n$ and produces an optimal encoding for $p_1,\ldots,p_n$ by adding a disambiguating bit to the codeword corresponding to $p_{n-1}+p_n$; it's not clear how to carry out a similar construction for an arbitrary uniquely decodable code.