The Construction of Near-Optimal Universal Coding of Integers
- 5 June 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. PP (00189448) , 1
Abstract
The Universal Coding of Integers (UCI) is suitable for discrete memoryless sources with unknown probability distributions and infinitely countable alphabet sizes. A UCI is a class of prefix codes for which the ratio of the average codeword length to max{1,H(P)} is within a constant expansion factor CC for any decreasing probability distribution P, where H(P) is the entropy of P. For any UCI code C, the minimum expansion factor C∗ C is defined to represent the infimum of the set of extension factors of C. Each C has a unique corresponding C∗ C, and the smaller C∗ C is, the better the compression performance of C is. The class of UCIs C (or a family {Ci}∞ i=1) that achieves the smallest C∗ C is defined as the optimal UCI. The best current result is that the range of C∗ C for the optimal UCI is 2 ≤ C∗ C ≤ 2.5. In this paper, we prove a tighter probability inequality for decreasing distributions, which serves as a new tool for studying the properties of UCIs. On the basis of this inequality, we prove that there exists a class of near-optimal UCIs, called the ν code, achieving Cν = 2.0386. This narrows the range of the minimum expansion factor for the optimal UCI to 2 ≤ C∗ C ≤ 2.0386. We show that the ν code is currently optimal in terms of the minimum expansion factor. In addition, we propose a new proof showing that the minimum expansion factor of the optimal UCI is lower bounded by 2.Keywords
Funding Information
- National Natural Science Foundation of China (62401599)
This publication has 34 references indexed in Scilit:
- A Construction of Evolving k-Threshold Secret Sharing Scheme over A Polynomial Ring2025
- Variable-length Codes for Data Compression2007
- Elements of Information Theory2001
- Alphabetic codes revisitedIEEE Transactions on Information Theory, 1991
- A new asymptotically optimal code for the positive integersIEEE Transactions on Information Theory, 1991
- Flag Encodings Related to the Zeckendorf Representation of Integers1990
- Almost asymptotically optimal flag encoding of the integersIEEE Transactions on Information Theory, 1988
- An upper bound on the entropy seriesInformation and Control, 1972
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948