On the Expected Codeword Length Per Symbol of Optimal Prefix Codes for Extended Sources

Given a discrete memoryless source X, it is well known that the expected codeword length per symbol L _n(X) of an optimal prefix code for the extended source X ⁿ converges to the source entropy as n approaches infinity. However, the sequence L _n(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 _n(X) and obtain for each nges1 and nondyadic p ₁ n ( p ₁ is the probability of the most likely source symbol) an integer k* for which L _kn(X)<L _n(X) for all kgesk*, implying that the coding efficiency of encoding blocks of length kn is higher than that of encoding blocks of length n for all kgesk*. This question is simpler in part because L _kn(X)lesL _n(X) is guaranteed for all nges1 and kges1, but our results distinguish scenarios where increasing the multiplicative factor guarantees strict improvement. These results extend and generalize those by Montgomery and Kumar.

I. Introduction

Let be a discrete memoryless source defined on a finite or countably infinite alphabet . Without loss of generality, we assume that , where can be infinite, and that the probabilities , are ordered so that . The th extension of the source , denoted , is characterized by the probability distribution for all . For a given code for , the expected codeword length for is given by

$$L(C)=\sum_{(i_1,i_2,\ldots,i_n)\in{\cal X}^n}p(i_1,i_2,\ldots,i_n) l(i_1,i_2,\ldots,i_n)$$ where is the length of the codeword . Let be the expected codeword length per source symbol of an optimal prefix code for the extended source , namely $$\eqalignno{L_n(X)&=\min\left\{{1 \over n}L(C): C\ {\hbox{is\ a\ prefix\ code\ for}}\ X^n \right\}. \qquad &\hbox{(1)} }$$ It is well known from Shannon's noiseless coding theorem [1], [2] that $$H(X) \leq L_n(X) < H(X)+{1 \over n} \eqno{\hbox{(2)}}$$ where is the entropy of the source .