# Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding

Abstract : Analytic information theory aims at studying problems of information theory using analytic techniques of computer science and combinatorics. Following Hadamard's precept, these problems are tackled by complex analysis methods such as generating functions, Mellin transform, Fourier series, saddle point method, analytic poissonization and depoissonization, and singularity analysis. This approach lies at the crossroad of computer science and information theory. In this survey we concentrate on one facet of information theory (i.e., source coding better known as data compression), namely the $\textit{redundancy rate}$ problem. The redundancy rate problem determines by how much the actual code length exceeds the optimal code length. We further restrict our interest to the $\textit{average}$ redundancy for $\textit{known}$ sources, that is, when statistics of information sources are known. We present precise analyses of three types of lossless data compression schemes, namely fixed-to-variable (FV) length codes, variable-to-fixed (VF) length codes, and variable-to-variable (VV) length codes. In particular, we investigate average redundancy of Huffman, Tunstall, and Khodak codes. These codes have succinct representations as $\textit{trees}$, either as coding or parsing trees, and we analyze here some of their parameters (e.g., the average path from the root to a leaf).
Keywords :
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.19-58, 2008, DMTCS Proceedings
Domaine :

Littérature citée [151 références]

https://hal.inria.fr/hal-01194680
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:51:03
Dernière modification le : mercredi 10 mai 2017 - 17:41:03
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:59:45

### Fichier

dmAI0102.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01194680, version 1

### Citation

Wojciech Szpankowski. Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.19-58, 2008, DMTCS Proceedings. 〈hal-01194680〉

### Métriques

Consultations de la notice

## 223

Téléchargements de fichiers