CUED Publications database

An implementable lossy version of the Lempel-Ziv algorithm - Part I: Optimality for memoryless sources

Kontoyiannis, I (1999) An implementable lossy version of the Lempel-Ziv algorithm - Part I: Optimality for memoryless sources. IEEE Transactions on Information Theory, 45. pp. 2293-2305. ISSN 0018-9448

Full text not available from this repository.

Abstract

A new lossy variant of the Fixed-Database Lenipel-Ziv coding algorithm for encoding at a fixed distortion level is proposed, and its asymptotic optimality and universality for memoryless sources (with respect to bounded single-letter distortion measures) is demonstrated: As the database size m increases to infinity, the expected compression ratio approaches the rate-distortion function. The complexity and redundancy characteristics of the algorithm are comparable to those of its lossless counterpart. A heuristic argument suggests that the redundancy is of order (log log m)/log m, and this is also confirmed experimentally; simulation results are presented that agree well with this rate. Also, the complexity of the algorithm is seen to be comparable to that of the corresponding lossless scheme. We show that there is a tradeoff between compression performance and encoding complexity, and we discuss how the relevant parameters can be chosen to balance this tradeoff in practice. We also discuss the performance of the algorithm when applied to sources with memory, and extensions to the cases of unbounded distortion measures and infinite reproduction alphabets. © 1999 IEEE.

Item Type: Article
Subjects: UNSPECIFIED
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 08 Jan 2018 20:11
Last Modified: 18 Aug 2020 12:42
DOI: 10.1109/18.796370