Generalized Universal Coding of Integers

Universal coding of integers (UCI) is a class of variable-length code such that the ratio of the expected codeword length to max1, H (P) is bounded by a constant factor, where H (P) is the Shannon entropy of the decreasing probability distribution P. However, if we consider the ratio of the expected codeword length to H (P) for UCI, the ratio tends to infinity when H (P) tends to zero. To resolve this issue, we introduce a class of codes, called generalized universal coding of integers (GUCI), where the ratio of the expected codeword length to H (P) is bounded by a constant factor K. First, the definition of GUCI is proposed. The coding structure of GUCI is introduced. Next, we propose a class of GUCIs C to reach the expansion factor KC = 2, and we show that the smallest minimum expansion factor is in the range 1 ≤ K * ≤ 2. Then, by comparing UCI and GUCI, we show that when the entropy is very large or P (0) is not large, there are also cases where the average codeword length of GUCI is shorter. Finally, the asymptotically optimal GUCI is presented.