On the Minimum of the Expansion Factor for Universal Coding of Integers
Wei Yan, Sian-Jheng Lin · IEEE Transactions on Communications · 2021
Universal coding of integers (UCI) is a prefix coding suitable for probability distributions without prior knowledge. UCI has the property that the expected codeword length is no more than constant$K_{C}$times$\max \{1,H(P)\}$, where$K_{C}$is called the expansion factor and$H(P)$is the entropy of source$P$. A class of UCI$C$with a smaller$K_{C}$is preferred, but the minimum value of$K_{C}$(as well as its code construction) is still unknown. Thus, this paper provides a range of the minimum values of$K_{C}$. First, we show that$K_{C}\geq 2$for each UCI$C$. Then, for the upper bound, we provide a class of UCIs, termed$\eta $code, to achieve$K_{C}=2.75$. This approach improves the prior result$K_{C}=3$achieved by Elias$\gamma $coding. Next, we propose an asymptotically optimal UCI, termed$\theta $code, to achieve$K_{C}=3.5$. Finally, we compare the range of the minimum value of$K_{C}$of$\eta $code,$\theta $code and some other UCIs.