On Precision - Redundancy Relation in the Design of Source Coding Algorithms - Computer Science > Information Theory

Abstract: We study the effects of finite-precision representation of source-sprobabilities on the efficiency of classic source coding algorithms, such asShannon, Gilbert-Moore, or arithmetic codes. In particular, we establish thefollowing simple connection between the redundancy $R$ and the number of bits$W$ necessary for representation of source-s probabilities in computer-s memory$R$ is assumed to be small: \begin{equation*} W \lesssim \eta \log 2\frac{m}{R}, \end{equation*} where $m$ is the cardinality of the source-salphabet, and $\eta \leqslant 1$ is an implementation-specific constant. Incase of binary alphabets $m=2$ we show that there exist codes for which $\eta= 1-2$, and in $m$-ary case $m > 2$ we show that there exist codes for which$\eta = m-m+1$. In general case, however which includes designs relying onprogressive updates of frequency counters, we show that $\eta = 1$. Usefulnessof these results for practical designs of source coding algorithms is alsodiscussed.

Author: Yuriy Reznik

Source: https://arxiv.org/