Universal coding with minimum probability of codeword length overflow

1 May 1991

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory

Vol. 37 (3) , 556-563
https://doi.org/10.1109/18.79912

Abstract

Lossless block-to-variable length source coding is studied for finite-state, finite-alphabet sources. The aim is to minimize the probability that the normalized length of the codeword will exceed a given threshold B, subject to the Kraft inequality. It is shown that the Lempel-Ziv algorithm (1978) asymptotically attains the optimal performance in the sense just defined, independently of the source and the value of B. For the subclass of unifilar Markov sources, faster convergence to the asymptotic optimum performance can be accomplished by using the minimum-description-length universal code for this subclass. It is demonstrated that these universal codes are also nearly optimal in the sense of minimizing buffer overflow probability, and asymptotically optimal in a competitive sense.

Keywords

This publication has 11 references indexed in Scilit:

Upper bounds on the probability of sequences emitted by finite-state sources and on the redundancy of the Lempel-Ziv algorithm
IEEE Transactions on Information Theory, 1992
Asymptotically optimal classification for multiple tests with empirically observed statistics
IEEE Transactions on Information Theory, 1989
Universal coding, information, prediction, and estimation
IEEE Transactions on Information Theory, 1984
Generalization of Huffman coding to minimize the probability of buffer overflow (Corresp.)
IEEE Transactions on Information Theory, 1981
Compression of individual sequences via variable-rate coding
IEEE Transactions on Information Theory, 1978
On the Probability of Buffer Overflow Under an Arbitrary Bounded Input-Output Distribution
SIAM Journal on Applied Mathematics, 1974
Error exponent for source coding with a fidelity criterion
IEEE Transactions on Information Theory, 1974
Universal noiseless coding
IEEE Transactions on Information Theory, 1973
On variable-length-to-block coding
IEEE Transactions on Information Theory, 1972
Buffer overflow in variable length coding of fixed rate sources
IEEE Transactions on Information Theory, 1968