Title :
On the redundancy of the fixed-database Lempel-Ziv algorithm for φ-mixing sources
Author :
Yang, En-Hui ; Kieffer, John C.
Author_Institution :
Dept. of Math., Nankai Univ., Tianjin, China
fDate :
7/1/1997 12:00:00 AM
Abstract :
The redundancy problem of the fixed-database Lempel-Ziv (1977) algorithm is considered. It is demonstrated that for a class of φ-mixing sources which includes Markov sources, unifilar sources, and finite-state sources as special cases, the redundancy of the fixed-database Lempel-Ziv algorithm with database size n is lower-bounded by H(loglogn)/logn+O((logloglogn)/logn) and upper-bounded by 2H(loglogn)/logn+O((logloglogn)/logn) where H is the entropy rate of the source. The method of proof is new and uses the concept of variable-length to variable-length codes
Keywords :
Markov processes; entropy; variable length codes; φ-mixing sources; Markov sources; database size; finite-state sources; fixed-database Lempel-Ziv algorithm; lower bound; redundancy; source entropy rate; unifilar sources; upper bound; variable length codes; Data compression; Databases; Decoding; Entropy; Mathematics; Statistics;
Journal_Title :
Information Theory, IEEE Transactions on
