Finding a general algorithm for constructing optimal prefix-free codes for infinite sources has been an open problem for many years. Not much has been discovered so far on this topic expect the fact that (i) if the entropy of a random variable associated with a source is finite then its Huffman code exists and (ii) there exists some subsequence of Huffman codes for truncated versions of the source that converges structurally to an optimal prefix code for the infinite source. In this thesis, we present some stronger convergence theorems, the most important one is that, given an infinite set of trees (finite or infinite), T0, Tl, T2, . . ., such that limi{Ti} = C where C is the optimal cost for the random variable source, then there exist a subsequence of Ti's that converges structurally...[ Read more ]

Finding a general algorithm for constructing optimal prefix-free codes for infinite sources has been an open problem for many years. Not much has been discovered so far on this topic expect the fact that (i) if the entropy of a random variable associated with a source is finite then its Huffman code exists and (ii) there exists some subsequence of Huffman codes for truncated versions of the source that converges structurally to an optimal prefix code for the infinite source. In this thesis, we present some stronger convergence theorems, the most important one is that, given an infinite set of trees (finite or infinite), T0, Tl, T2, . . ., such that limi{Ti} = C where C is the optimal cost for the random variable source, then there exist a subsequence of Ti's that converges structurally to an optimal tree for the source. Furthermore, if the source P has a unique optimal tree than the complete sequence of optimal tree for the truncated version of the source converges structurally to the optimal tree for P.

We also show that there exists an infinite sequence, ε, such that, P' = P + [epsilon][epsilon] has a unique optimal tree and this optimal tree is the lexicographically smallest optimal tree for P. As a result, the complete sequence of optimal trees for the truncated versions of P' converge structurally to the lexicographically smallest optimal tree for P.

However, no algorithm can be developed through the strong theorems that we have proved. In fact we can show that there exists no general algorithm for finding optimal trees for infinite sources.