Universal Coding of Positive Integers with Suppressed Codeword Length Order

这个为期四年的学术活动是关于正整数的通用编码，因为它是可以对任意出现概率的无界正整数进行有效编码的编码。本研究的结果可以总结为：1。在研究对较小正整数具有良好性能的通用编码的基础上(1)提出了一种将给定正整数的长度按几何级数分组的编码。它是渐近最优的。它具有保持长度顺序、数字顺序和字典顺序的特性。(2)采用正整数编码的分组策略，对图像分形表示的仿射变换参数进行分组。我们证明了图像的可逆分形表示是可能的。在研究长度接近已知最小长度阶的通用编码的基础上(1)提出了一种用数值计算方法分配码字的编码。首次启用码字长度顺序为修改后的log-star函数。对于正整数n，其编码和解码的时间复杂度均为log n，这是理论上的最小阶数。(2)提出了一种码字分量与Levenshtein-Elias码最多相差1位的码，其中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.