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 propose 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$. Finally, a more precise range of $K_{ \mathcal{ C}}^{ *}$ for the classic UCIs is discussed.
Categories: cs.IT math.IT