Name
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 memoryless 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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1109/DCC.2002.999960 | DCC |
Keywords | Field | DocType |
idealized arithmetic coding,finite buffer size,adaptive infinite precision implementation,arithmetic encoder,finite precision,idealized arithmetic code,elias coding,code length,average redundancy,shannon-fano code,precise average redundancy,arithmetic,data compression,fourier series,distributions,arithmetic coding | Weighting,Arbitrary-precision arithmetic,Computer science,Analysis of algorithms,Algorithm,Theoretical computer science,Redundancy (engineering),Shannon–Fano coding,Arithmetic coding,Variable-length code,Context-adaptive binary arithmetic coding | Conference |
ISSN | Citations | PageRank |
1068-0314 | 8 | 0.65 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Drmota | 1 | 438 | 54.46 |
| Hsien-Kuei Hwang | 2 | 365 | 38.02 |
| Wojciech Szpankowski | 3 | 1557 | 192.33 |