A Tighter Upper Bound of the Expansion Factor for Universal Coding of Integers and Its Code Constructions

Abstract

In entropy coding, universal coding of integers~(UCI) is a binary universal prefix code, such that the ratio of the expected codeword length to $\max \{1,H(P)\}$ is less than or equal to a constant expansion factor $K_{\mathcal{C}}$ for any probability distribution $P$, where $H(P)$ is the Shannon entropy of $P$. $K_{\mathcal{C}}^{\ast }$ is the infimum of the set of expansion factors. The optimal UCI is defined as a class of UCI possessing the smallest $K_{\mathcal{C}}^{\ast }$. Based on prior research, the range of $K_{\mathcal{C}}^{\ast }$ for the optimal UCI is $2\le K_{\mathcal{C}}^{\ast }\le 2.75$. Currently, the code constructions achieve $K_{\mathcal{C}}=2.75$ for UCI and $K_{\mathcal{C}}=3.5$ for asymptotically optimal UCI. In this paper, we propose a class of UCI, termed $\iota$ code, to achieve $K_{\mathcal{C}}=2.5$. This further narrows the range of $K_{\mathcal{C}}^{\ast }$ to $2\le K_{\mathcal{C}}^{\ast }\le 2.5$. Next, a family of asymptotically optimal UCIs is presented, where their expansion factor infinitely approaches $2.5$. Finally, a more precise range of $K_{\mathcal{C}}^{\ast }$ for the classic UCIs is discussed.