Efficient universal noiseless source codes
- 1 May 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 27 (3) , 269-279
- https://doi.org/10.1109/tit.1981.1056355
Abstract
Although the existence of universal noiseless variable-rate codes for the class of discrete stationary ergodic sources has previously been established, very few practical universal encoding methods are available. Efficient implementable universal source coding techniques are discussed in this paper. Results are presented on source codes for which a small value of the maximum redundancy is achieved with a relatively short block length. A constructive proof of the existence of universal noiseless codes for discrete stationary sources is first presented. The proof is shown to provide a method for obtaining efficient universal noiseless variable-rate codes for various classes of sources. For memoryless sources, upper and lower bounds are obtained for the minimax redundancy as a function of the block length of the code. Several techniques for constructing universal noiseless source codes for memoryless sources are presented and their redundancies are compared with the bounds. Consideration is given to possible applications to data compression for certain nonstationary sources.Keywords
This publication has 4 references indexed in Scilit:
- Variable-rate universal block source coding subject to a fidelity constraintIEEE Transactions on Information Theory, 1978
- Variable rate coding for nonergodic sources and classes of ergodic sources subject to a fidelity constraintIEEE Transactions on Information Theory, 1976
- Universal noiseless codingIEEE Transactions on Information Theory, 1973
- Codes based on inaccurate source probabilitiesIEEE Transactions on Information Theory, 1971