Precise Average Redundancy of an Idealized Arithmetic Coding
Author
Michael Drmota, Hsien-Kuei Hwang, Wojciech Szpankowski
Tech report number
CERIAS TR 2002-13
Abstract
Redundancy is defined as the excess of the code length over the optimal (ideal) code length. We study the average redundancy of an idealized arithmetic coding (for memory less sources with unknown distributions) in which the Krichevsky and Trofimov estimator is followed by the Shannon-Fano code. We shall ignore here important practical implementation issues such as finite precisions and finite buffer sizes. In fact, our idealized arithmetic code can be viewed as an adaptive infinite precision implementation of arithmetic encoder that resembles Elias coding. However, we provide very precise results for the average redundancy that takes into account integer-length constraints. These findings are obtained by analytic methods of analysis of algorithms such as theory of distribution of sequences modulo 1 and Fourier series. These estimates can be used to study the average redundancy of codes for tree sources, and ultimately the context-tree weighting algorithms.
Booktitle
Data Compression Conference
Institution
CERIAS, Purdue University
Publication Date
1900-01-01