Researchers determine exact optimal factor for universal integer coding
Optimal Universal Coding of Integers
Information Theory
Summary
This paper deals with the problem of how to represent any positive integer as a string of binary digits in a way that works well no matter how frequently different numbers appear. The authors find a special number, called the optimal minimum expansion factor, that measures how much longer codewords might get compared to the best possible limit. They prove this number precisely and show how to calculate it. Knowing this number helps build the best possible universal code for integers.
What this means in practice
- •For data compression engineers: Design coding schemes for integers with provably minimal worst-case average length ratios for any nonincreasing data distribution.
- •For communication protocol developers: Ensure the most efficient universal integer codes in bandwidth-limited systems by applying the optimal minimum expansion factor.
A theory result. No direct application yet.
Authors
Wei Yan, Yunghsiang S. Han, Leqian Zheng
Abstract
Universal coding of integers (UCI) provides binary codewords for positive integers such that, for every nonincreasing source distribution $P$, the average codeword length stays within $K$ times $\max\{1,H(P)\}$. The smallest constant $K$ is called the minimum expansion factor of UCI $\mathcal{C}$, denoted $C_{\mathcal{C}}^{*}$. The optimal minimum expansion factor $C^*=\inf\{C_{\mathcal{C}}^{*}\}$ is the minimum expansion factor corresponding to the optimal UCI. The optimal minimum expansion factor is currently known to lie in the range $2\le C^*\le 2.0386$. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every universal code, the worst-case ratio is attained by a distribution in this family, so that the family is least favorable for the UCI problem. We further establish an inequality, called the \emph{UCI inequality}, which plays the same role for UCI as the Kraft inequality does for prefix codes: for any real number $B$, it decides whether $B$ lies below or above $C^*$. Through the UCI inequality, we obtain an equivalent definition of $C^*$. By numerical computation, we determine $C^*=2.000124757036101\cdots$, the first fifteen decimal digits being certified. Once $C^*$ is known, we can theoretically construct the optimal UCI.