Universal Coding of Positive Integers with Suppressed Codeword Length Order

这项为期四年的学术活动是在正整数的通用编码上完成的，因为它可以有效地对任何出现概率的无界正整数进行编码。本文的主要研究成果如下：1.关于对较小正整数具有良好性能的通用编码的研究（1）提出了一种将给定正整数的长度与等比数列分组的编码。它是渐近最优的。它具有保持长度顺序、数字顺序和字典顺序的性质。(2)We提出了一种利用正整数编码的分组策略对仿射变换的参数进行分组的编码，用于图像的分形表示。我们证明了图象的可逆分形表示是可能的。2.关于长度接近已知理论最小长度阶的通用编码的研究（1）我们提出了一种用数值计算来分配码字的编码。它使得码字长度的阶数首次是修改的对数星形函数。对于正整数n，其编解码时间复杂度均为logn，这是理论上的最小阶数。(2)We提出了一种码，它的每个码字分量与Levenshtein-Elias码相差最多一位，其中Levenshtein-Elias码是最基本的递归型正整数码。在几乎所有足够大的正整数情况下，该码的码字长度都小于对数星函数。

This academic activity for four years was done on the universal coding of positive integers, as it is the coding which can effectively encode unbounded positive integers for any appearance probabilities. The results of this study can be summarized as follows :1.On the study of the universal coding which has good performance for relatively small positive integers(1)We proposed a code which groups the length of given positive integer with the geometric progression. It is asymptotically optimal. And it has the property of preserving length order, number order, and lexicographic order.(2)We proposed a code which groups the parameters of Affine Transformation for the fractal representation of images with the grouping strategy of positive integer coding. We show that the reversible fractal representation for images is possible.2.On the study of the universal coding which length is near known theoretically minimum length order(1)We proposed a code which uses numerical calculations for the assignment of the codewords. It enables that the order of the codeword length is the modified log-star function for the first time. For positive integer n, its time complexity for coding and decoding is both log n which is the theoretically minimum order.(2)We proposed a code whose each codeword component is different from Levenshtein-Elias code with one bit at most, where Levenshtein-Elias code is the most basic recursive-type positive integer code. The codeword length of the proposed code is shorter than log-star function in almost all of sufficiently large positive integers.