A Study of Universal Coding for Enumerable Discrete Information Structures

可枚举离散信息结构的通用编码研究

• 批准号: 14550351
• 负责人: KOBAYASHI Kingo
• 金额: $ 2.24万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14550351/
• 关键词: universal code; discrete information structure; binary tree; vector k-ary tree; Young tableaux; low density parity check code; watermark; steganography; k-分木; 算術符号; 情報源変換; 落し戸通信路; κ分木; 一般化カタラン数; パーコレーション; エントロピー; Sum-Product復号; ベルヌイ分岐過程 /

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.

本研究课题的主题是对计算机科学中经常出现的整数、树、图、Young tableaux等枚举离散信息结构，以及表示文本字母的有限离散数据、采样量化的语音数据、图像中的亮度和色度数据的通用编码进行研究，完成了二叉树编码的分析，并将我们的方法扩展到k叉树和向量k叉树，其使用对于通用编码应该是强大的。此外，我们提出了一个步骤的研究杨tableaux包含类的树木作为一个子集。我们可以把一棵二叉树对应成一个2 × n的矩形Young tableaux。但是我们不能将k元树和向量k元树对应到一般的标准Young tableaux。然而，我们表明，由一个扩展的杨tableaux定义的偏序集在整数格，它是可能的，以表示它们。这些结果为构造一般树的新编码提供了有吸引力的思路。通过将标准的Young tableaux推广到多维tableaux，得到了Hook公式的意义和碰撞算法的许多方面。我们在几个国际会议上（IEEE ISIT 2002，2004，ISITA 2004 in Parma，Conferences on General Information Transfer and Combinatorics in比勒费尔德university）介绍了这些结果。在水印的版权保护和隐写术的研究，被认为是一个广义的版本的隐藏信息，我们进行了实验方面的基本效率的水印抵抗联盟，和隐写术使用频域考虑相关数据的结构。

项目成果

修正プライム系列符号を用いたLDPC符号の性能評価

使用修改素数序列码的 LDPC 码性能评估

• 发表时间: 2003
• 期刊: 第26回情報理論とその応用シンポジウム予稿集
• 作者: H.Morita;M.Hoshi;K.Kobayashi;K.Kobayashi;Silvia Torres Maya;H.Morita;K.Kobayashi;K.Kobayashi;山本裕一
• 通讯作者: 山本裕一

K.Kobayashi: "When the entropy function appears in the residue"Abstracts of Preparatory Meeting of General Theory of Information Transfer. 38 (2002)

K.Kobayashi：“当熵函数出现在残差中时”信息传递一般理论筹备会议摘要。

A Tree Source and its Entropy

树源及其熵

• 发表时间: 2003
• 期刊: Proc. of the 2003 IEEE ISIT, Yokohama, Japan
• 作者: H.Morita;M.Hoshi;K.Kobayashi;K.Kobayashi;Silvia Torres Maya;H.Morita;K.Kobayashi
• 通讯作者: K.Kobayashi

低密度パリティ検査符号のBit Serial Sum-Product復号法

低密度奇偶校验码的比特串行和积译码方法

• 发表时间: 2003
• 期刊: 第26回情報理論とその応用シンポジウム予稿集
• 作者: H.Morita;M.Hoshi;K.Kobayashi;K.Kobayashi;Silvia Torres Maya;H.Morita;K.Kobayashi;K.Kobayashi;山本裕一;矢部雅人
• 通讯作者: 矢部雅人

An efficiency evaluation of LDPC codes using modified prime sequence codes

使用修改的素数序列码评估 LDPC 码的效率

• 发表时间: 2003
• 期刊: Proc of 27-th SITA
• 作者: Y.Yamamoto;K.Yamaguchi;K.Kobayashi
• 通讯作者: K.Kobayashi