ON THE REDUNDANCY OF THE FIXED-DATABASE LEMPEL-ZIV ALGORITHM FOR PHI-MIXING SOURCES

Authors
YANG EH KIEFFER JC
Citation
Eh. Yang et Jc. Kieffer, ON THE REDUNDANCY OF THE FIXED-DATABASE LEMPEL-ZIV ALGORITHM FOR PHI-MIXING SOURCES, IEEE transactions on information theory, 43(4), 1997, pp. 1101-1111
Citations number
17
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
43
Issue
4
Year of publication
1997
Pages
1101 - 1111
Database
ISI
SICI code
0018-9448(1997)43:4<1101:OTROTF>2.0.ZU;2-D
Abstract
The redundancy problem of the fixed-database Lempel-Ziv algorithm is c onsidered. It is demonstrated that for a class of phi-mixing sources w hich includes Markov sources, unifilar sources, and finite-state sourc es as special cases, the redundancy of the fixed-database Lempel-Ziv a lgorithm with database size n is lower-bounded by H(log log n)/log n O((log log log n)/log n) and upper-bounded by 2H(log log n)/log n + O ((log log log n)/log n) where H is the entropy rate of the source. The method of proof is new and uses the concept of variable-length to var iable-length codes.