pipette
ENEnglish

Optimal Universal Coding of Integers

Wei Yan, Yunghsiang S. Han, and Leqian Zheng

Preprint

En palabras de los autores

Universal coding of integers (UCI) provides binary codewords for positive integers such that, for every nonincreasing source distribution , the average codeword length stays within times . The smallest constant is called the minimum expansion factor of UCI , denoted . The optimal minimum expansion factor is the minimum expansion factor corresponding to the optimal UCI. The optimal minimum expansion factor is currently known to lie in the range . In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every universal code, the worst-case ratio is attained by a distribution in this family, so that the family is least favorable for the UCI problem. We further establish an inequality, called the UCI inequality, which plays the same role for UCI as the Kraft inequality does for prefix codes: for any real number , it decides whether lies below or above . Through the UCI inequality, we obtain an equivalent definition of . By numerical computation, we determine , the first fifteen decimal digits being certified. Once is known, we can theoretically construct the optimal UCI.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.