Optimal Universal Coding of Integers
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.
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.