A Noiseless Coding Theorem for Sources Having Utilities
Giuseppe Longo · SIAM Journal on Applied Mathematics · 1976
An investigation is carried out concerning discrete memoryless sources possessing an additional parameter (utility) which seems to be significant in problems of storage and transmission. A cost function is then defined in terms of the additional parameters and of the length of the codewords. Lower and upper bounds are derived for the cost function and its asymptotic behavior is studied with reference to the problem of encoding source blocks of increasing length. It is shown that, in the limit, the average cost per letter approaches the Shannon entropy of the source, and therefore the influence of the additional parameter disappears. As a consequence, the minimum cost per letter can be obtained in general when the blocks have a finite length (possibly equal to 1) rather than asymptotically when the length tends to infinity.