Wojciech Szpankowski - Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding

dmtcs:3555 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3555
Average Redundancy for Known Sources: Ubiquitous Trees in Source CodingArticle

Authors: Wojciech Szpankowski 1

  • 1 Department of Computer Science [Purdue]

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).


Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: complex asymptotics,Mellin transform,distribution modulo $1$,redundancy,Khodak code,Tunstall code,Huffman code,data compression,Source coding,prefix codes,Kraft's inequality,Shannon lower bound,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Combinatorial &Probabilistic Methods for Biol Sequences; Funder: National Institutes of Health; Code: 5R01GM068959-04
  • Optimization driven Multi-hop Network Design and Experimentation; Funder: European Commission; Code: 224218
  • Crossroads of Information Theory and Computer Science: Analytic Algorithmics, Combinatorics, and Information Theory; Funder: National Science Foundation; Code: 0513636
  • Collaborative Research: Information Theory of Data Structures; Funder: National Science Foundation; Code: 0830140
  • Information Transfer in Biological Systems; Funder: National Science Foundation; Code: 0800568
  • Collaborative Research: Nonlinear Equations Arising in Information Theory and Computer Sciences; Funder: National Science Foundation; Code: 0503742

3 Documents citing this article

Consultation statistics

This page has been seen 244 times.
This article's PDF has been downloaded 201 times.