Abstract
For a discrete memoryless source X, it is well known that the expected codeword length per symbol L <sub>n</sub> (X) of an optimal prefix code for the extended source X <sup>n</sup> converges to the source entropy. However, the sequence L <sub>n</sub> (X) need not be nonincreasing. As the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is both important and of interest to know when we can have a decrease in the expected codeword length per symbol by increasing the block length. In this paper, we obtain some results on the behavior of L <sub>n</sub> (X) and provide sufficient conditions for L <sub>kn</sub> (X)< L <sub>n</sub> (X) in terms of k, n, the probability of the most likely source symbol p <sub>1</sub> and/or the minimum codeword length of an optimal code for the original source. By using these sufficient conditions, for any given n 1 and non-dyadic pn<over>1, we also obtain an integer k* 2 such that L <sub>k'n</sub> (X) < L <sub>n</sub> (X) for all k' k*. Our results could be regarded as extensions and generalizations of those by Montgomery and Kumar. Copyright 2007 ACM.