Generalized Universal Coding of Integers
share
Universal coding of integers (UCI) is a class of variable-length code, such that the ratio of the expected codeword length to max{1,H(P)} is within 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), the ratio tends to infinity by using UCI, when H(P) tends to zero. To solve this issue, this paper introduces a class of codes, termed generalized universal coding of integers (GUCI), such that the ratio of the expected codeword length to H(P) is within a constant factor K. First, the definition of GUCI is proposed and the coding structure of GUCI is introduced. Next, we propose a class of GUCI 𝒞 to achieve the expansion factor K_𝒞=2 and show that the optimal GUCI 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.
READ FULL TEXT