Abstract
Given 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 as n approaches infinity. However, the sequence L <sub>n</sub> (X) need not be monotonic in n, which implies that the coding efficiency cannot be increased by simply encoding a larger block of source symbols (unless the block length is appropriately chosen). As the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is useful to know when an increase in the block length guarantees a decrease in the expected codeword length per symbol. While this paper does not provide a complete answer to that question, we give some properties of L <sub>n</sub> (X) and obtain for each n ≥ 1 and nondyadic p <sub>1</sub> <sup>n</sup> (p <sub>1</sub> is the probability of the most likely source symbol) an integer k* for which L <sub>kn</sub> (X) <L <sub>n</sub> (X)k≥ k*, implying that the coding efficiency of encoding blocks of length kn is higher than that of encoding blocks of length n for all k ≥ k*. This question is simpler in part because L <sub>kn</sub> (X) ≤ L <sub>n</sub> (X) is guaranteed for all n ≥ 1 and k ≥ 1, but our results distinguish scenarios where increasing the multiplicative factor guarantees strict improvement. These results extend and generalize those by Montgomery and Kumar. © 2009 IEEE.