On the Expected Codeword Length Per Symbol of Optimal Prefix Codes for Extended Sources
Jay Cheng · IEEE Transactions on Information Theory · 2009
Given a discrete memoryless sourceX, it is well known that the expected codeword length per symbolLn(X) of an optimal prefix code for the extended sourceXnconverges to the source entropy asnapproaches infinity. However, the sequenceLn(X) need not be monotonic inn, 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 ofLn(X) and obtain for eachnges1 and nondyadicp1n(p1is the probability of the most likely source symbol) an integerk* for whichLkn(X)Ln(X) for allkgesk*, implying that the coding efficiency of encoding blocks of lengthknis higher than that of encoding blocks of lengthnfor allkgesk*. This question is simpler in part becauseLkn(X)lesLn(X) is guaranteed for allnges1 andkges1, but our results distinguish scenarios where increasing the multiplicative factor guarantees strict improvement. These results extend and generalize those by Montgomery and Kumar.