Universal Coding of Positive Integers with Suppressed Codeword Length Order

具有抑制码字长度顺序的正整数通用编码

基本信息

批准号：
13650441
负责人：
NAKAMURA Hirofumi
金额：
$ 1.54万
依托单位：
Miyakonojo National College of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2004
项目状态：
已结题

项目摘要

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.

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