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

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}}^{*}$ 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}}^{*}$ . Based on prior research, the range of $K_{\mathcal {C}}^{*}$ for the optimal UCI is $2\leq K_{\mathcal {C}}^{*}\leq 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 construct a class of UCI, termed $\iota $ code, to achieve $K_{\mathcal {C}}=2.5$ . This further narrows the range of $K_{\mathcal {C}}^{*}$ to $2\leq K_{\mathcal {C}}^{*}\leq 2.5$ . Next, a family of asymptotically optimal UCIs is presented, where their expansion factor infinitely approaches 2.5. Then, tighter upper bounds of the expansion factors are derived for several classic UCIs. Finally, we prove that the length of the first codeword of optimal UCI is one.