Precise Average Redundancy of an Idealized Arithmetic Coding

Get BibTex-formatted data

Download

PDF

Author

Michael Drmota, Hsien-Kuei Hwang, Wojciech Szpankowski

Tech report number

CERIAS TR 2002-13

Entry type

inproceedings

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.

Download

PDF

Date

2002

URL

https://www.cerias.purdue.edu/papers/archive/2002-13.ps

Booktitle

Data Compression Conference

Institution

CERIAS, Purdue University

Key alpha

Drmota

Publication Date

1900-01-01

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Inproceedings{ Drmota,
	title = "Precise Average Redundancy of an Idealized Arithmetic Coding",
	author = "Michael Drmota, Hsien-Kuei Hwang, Wojciech Szpankowski",
	year = "2002",
	booktitle = "Data Compression Conference",
	institution = "CERIAS, Purdue University",
	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.",
	url = "https://www.cerias.purdue.edu/papers/archive/2002-13.ps",
}