Optimal (minimum cost) binary prefix codes for infinite sources with geometrically distributed frequencies, e.g. , P = {pⁱ(1 - p)}_i=0^∞, 0 p 1, were first (implicitly) suggested by Golomb over thirty years ago in the context of run-length encodings. Ten years later Gallager and Van Voorhis exhibited such optimal codes for all values of p. Just recently Merhav, Seroussi and Weinberger extended this further to find optimal binary prefix codes for two-sided geometric distributions....[ Read more ]

Optimal (minimum cost) binary prefix codes for infinite sources with geometrically distributed frequencies, e.g. , P = {pⁱ(1 - p)}_i=0^∞<, 0 < p < 1, were first (implicitly) suggested by Golomb over thirty years ago in the context of run-length encodings. Ten years later Gallager and Van Voorhis exhibited such optimal codes for all values of p. Just recently Merhav, Seroussi and Weinberger extended this further to find optimal binary prefix codes for two-sided geometric distributions.

These codes were derived by cleverly "guessing" optimal codes for finite sources, validating these guesses by using the sibling property of Huffman encoding, and then showing that the finite codes converge in a very specific sense to an optimal infinite one.

In this thesis we describe the first algorithmic approach to constructing optimal prefix infinite codes. Our approach is to define an infinite weighted graph with the property that the least cost infinite path in the graph corresponds to the optimal code. We then show that even though the graph is infinite, the least-cost infinite path has a repetitive structure and that it is therefore possible to not only find this path but to find it relatively efficiently.

This approach will work for even more complicated generalizations of geometric sources where solutions cannot be guessed as well as in extensions of Huffman-coding for which the Huffman algorithm no longer works, e.g., non-uniform cost encoding alphabet characters and/or other restrictions on the codewords. We illustrate our approach by deriving an algorithm for constructing optimal prefix free codes with a geometric source for the telegraph channel. We also implement our algorithm and show what the constructed codes look like in this case.