Introduction to Arithmetic Coding Theory and Practice

Said, Amir

HP Development Company

关键词: entropy coding;    compression;    complexity;   

RP-ID  :  HPL-2004-76

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

美国|英语

来源: HP Labs

【 摘 要 】

This introduction to arithmetic coding is divided in two parts. The first explains how and why arithmetic coding works. We start presenting it in very general terms, so that its simplicity is not lost under layers of implementation details. Next, we show some of its basic properties, which are later used in the computational techniques required for a practical implementation. In the second part, we cover the practical implementation aspects, including arithmetic operations with low precision, the subdivision of coding and modeling, and the realization of adaptive encoders. We also analyze the arithmetic coding computational complexity, and techniques to reduce it. We start some sections by first introducing the notation and most of the mathematical definitions. The reader should not be intimidated if at first their motivation is not clear: these are always followed by examples and explanations. Notes: Copyright Academic Press Published as a chapter in Lossless Compression Handbook by Khalid Sayood 64 Pages