2021/09/18 by Wei Yan, Sian-Jheng Lin, Yan, Wei +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2109.08920
openalex publication_date 2021/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 KC for any probability distribution P, where H(P) is the Shannon entropy of P. KC* is the infimum of the set of expansion factors. The optimal UCI is defined as a class of UCI possessing the smallest KC*. Based on prior research, the range of KC* for the optimal UCI is 2≤ KC*≤ 2.75. Currently, the code constructions achieve KC=2.75 for UCI and KC=3.5 for asymptotically optimal UCI. In this paper, we propose a class of UCI, termed ι code, to achieve KC=2.5. This further narrows the range of KC* to 2≤ KC*≤ 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 KC* for the classic UCIs is discussed.