Length of Phase-in Codes

September 23, 2008

In a previous post, I presented the phase-in codes. I stated that they were very efficient given the distribution is uniform. I also stated that, given the distribution is uniform, they never do worse than \approx 0.086 bits worse than the theoretical lower bound of \lg N, where N is the number of distinct symbols to code and \lg N is a convenient shorthand for \log_2. In this post, I derive that result.

Read the rest of this entry »