A Study of Universal Coding for Enumerable Discrete Information Structures

本研究项目的主题是研究枚举离散信息结构的通用编码，例如在计算机科学中经常出现的整数、树、图和杨氏表，以及表示文本字母的有限离散数据、采样量化语音数据和图像中亮度和色度数据。我们已经完成了二叉树的编码分析，并将我们的方法扩展到k-ary树和向量k-ary树，它的使用应该是强大的通用编码。此外，我们在Young tableaux的研究上迈出了一步，其中包含了树的子集。我们可以将二叉树对应为2xn的杨氏矩形表。但是我们不能把k元树和向量k元树和标准杨氏表相对应。然而，我们证明了由整数格中的偏序集定义的扩展Young表可以表示它们。这些结果为构造一般树的新代码提供了有吸引力的思路。在此基础上，通过将标准Young表推广到多维表，对Hook公式和碰撞算法的意义进行了多方面的探讨。我们在几个国际会议上发表了这些结果（IEEE ISIT 2002,2004，帕尔马ISITA2004， Bielefeld大学通用信息传递和组合学会议）。在进行上述理论研究的同时，对水印和隐写的性能进行了实验研究。在版权保护和隐写水印的研究中，我们考虑到相关数据的结构，对水印在抗联合和使用频率域隐写方面的基本效率进行了实验。

The theme of this research project is on a study of universal coding of enumerative discrete information structures, such as integers, trees, graphs and Young tableaux that frequently appear in the computer science, as well as finite discrete data representing letters of text, sampled quantized voice data, and data of brightness and chroma in pictures.We have completed the analysis of coding of binary trees, and extended our method to k-ary trees and vector k-ary trees, the use of which should be powerful for universal coding. Furthermore, we moved a step towards the study of Young tableaux containing the class of trees as a subset of them. We can correspond a binary tree to a 2 x n rectangular Young tableaux. But we cannot correspond k-ary tree and vector k-ary tree to a standard Young tableaux in general. However, we show that by an extended Young tableaux defined by a poset in the integer lattice, it is possible to represent them. These results suggest attractive idea on constructing new code for general trees. Furthermore, we got many aspects on the meaning of Hook formula and the bumping algorithm by generalizing the standard Young tableaux to multi-dimensional tableaux. We presented these results at several international conference(IEEE ISIT 2002,2004,ISITA2004 at Parma, Conferences on General information transfer and combinatorics at Bielefeld university).As well as the above theoretical study, we researched experimentally the performance of watermark and steganography. In the study of watermark for copyright protection and steganography that is considered as a generalized version of hiding information, we performed experiments with respect to the fundamental efficiencies of watermark on resistance against coalition, and steganography using frequency region by considering the structure of relevant data.