Title :
Universal noiseless codes for sources of arbitrary entropy
Author :
Wyner, Abraham ; Foster, Dean ; Stine, Bob
Author_Institution :
Wharton Sch., Pennsylvania Univ., Philadelphia, PA, USA
Abstract :
We offer two noiseless codes for representing blocks of n integers Xn generated independently by a source characterized by an unknown monotone probability function. Though assumed monotone, the source is allowed arbitrary entropy H⩾0, including zero. Our first coding procedure is illustrative, yet universal in the strong sense that the expected value of the code length L(Xn) is dominated by a linear function of the source entropy, EL(Xn)⩽c0 +c1nH. Our second procedure is asymptotically optimal in the sense that EL(Xn)⩽nH+0(nH). We discuss the implications of these coding procedures for model selection using the minimum description length (MDL)
Keywords :
arithmetic codes; entropy; probability; source coding; MDL; arbitrary entropy sources; arithmetic coder; asymptotically optimal method; code length; coding procedure; linear function; minimum description length; model selection; monotone probability function; prefix code; source entropy; universal noiseless codes; Arithmetic; Character generation; Decoding; Encoding; Entropy; Noise generators; Probability distribution; Random variables; Statistics; Upper bound;
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Conference_Location :
Sorrento
Print_ISBN :
0-7803-5857-0
DOI :
10.1109/ISIT.2000.866623
