TRULY ERROR RESILIENT LEMPEL-ZIV'77 BASED DATA COMPRESSION ALGORITHM

Stefano Lonardi

University of California, Riverside

Wojciech Szpankowski

Purdue University, West Lafayette

Last updated:
Apr 24, 2003

Overview

Source coding and channel coding are two opposing forces that present significant challenges in error-resilient adaptive lossless data compression. Source coding tries to decorrelate the input sequence as much as possible by removing redundant information, while channel coding introduces additional correlation by adding the information in order to protect against errors. Due to their devastating effects, errors in adaptive data compression have been a long-standing open problem. As a result, the non-resilience of adaptive data compression has hindered its use in many applications. However, joint source-channel coding has emerged as a possible solution to the problem. We have developed a novel joint source-coding algorithm capable of correcting errors in the popular Lempel-Ziv'77 scheme without losing any practical compression power.

This is possible since the LZ'77 (as well as gzip) encoder does not completely remove all redundancy. The inherent additional redundancy left by LZ'77 encoder is used succinctly by a channel coder (e.g., Reed-Solomon coder) to protect against a limited number of errors. In addition to this, the scheme proposed here is perfectly backward-compatible, that is, a file compressed with our error-resilient LZ'77 can be still decompressed by a common LZ'77 decoder.