Resilient Parameterized Tree Codes for Fast Adaptive Coding

Said, Amir

HP Development Company

关键词: entropy coding;    tree codes;    adaptive coding;   

RP-ID  :  HPL-2004-102

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

This report presents an introduction to efficient adaptive compression using parameterized prefix codes. Advanced adaptive coding techniques can be quite complex because of the need to reliably estimate the probability of a large number of data symbols, each in number of coding contexts, and then create the codes for each context, and finally code the data. We present practical alternatives with much smaller complexity, which uses a pre-defined group of codes with special structure. The adaptive coding process is simplified to estimating which is the best code for a given symbol. This approach is commonly used with Golomb-Rice codes. However, we demonstrate how these codes are quite sensitive to errors in the code- selection process, but which are in practically unavoidable, due to statistical uncertainty, and the non-stationary nature of real sources. We propose a new family of codes that would have inferior performance if applied to stationary sources, but that are much more "resilient" to errors in the code selection parameters. C++ source code that exemplifies the implementation of the new codes is provided. In addition we propose a combination of those codes with arithmetic coding, in order to exploit the best characteristics of each, and obtain nearly optimal compression, but with complexity (both memory and computation time) much lower than required for arithmetic-only coding. 35 Pages