A Study of Universal Coding for Enumerable Discrete Information Structures

点击翻译按钮获取中文摘要

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.