IMI Colloquium

7月 IMI Colloquium

日時：2014年7月16日（水）
16:45-17:45
場所：九州大学 マス・フォア・インダストリ研究所
大講義室１（数理・IMI図書館棟３F）
講師：村松 純 氏（NTT コミュニケーション科学基礎研究所）

講演タイトル：ハッシュ性に基づく情報理論
講演要旨：
シャノンの1948年の論文から始まった情報理論により, 情報圧縮や誤り訂正符号の性能限界（シャノン限界）が明らかになった. しかしながら, この限界を達成する符号は, 情報源や通信路の次元 n に対して指数的なメモリ量や計算量を必要とするため, 大きな n では実行が困難であるという問題があった. この問題を克服するために開発された疎行列を用いた符号(LDPC/LDGM符号)は大きな n で実行容易な符号で, 近年盛んに研究が進んでいるが, シャノン限界を達成することを保証する情報源や通信路に対称性などの制限があった. 本研究では, 関数アンサンブルのハッシュ性と呼ばれる性質を仮定することにより, シャノン限界を達成する符号の構成を統一的に扱うことができる. 特に, 疎行列を用いて構成した符号が, 一般の情報源や通信路に対してシャノン限界を達成することが証明できる. この講演では, 通信路符号(誤り訂正符号)を例にとって, 本研究の概要を解説する.

Title：Information Theory Based on a Hash Property

Abstract:
In 1948, C. E. Shannon established the information theory, which clarifies the limits of the performance (the Shannon limits) for transmission codes such as the data compression codes and the error correcting codes. However, the optimal code constructions are impractical because the time complexity and the memory size are exponential with respect to the dimension n of source sequences and channel inputs. Recently, codes using sparse matrices (LDPC/LDGM codes), which is tractable with large n, are studied actively. However, it is necessary for the optimality of these codes that a source/channel has symmetry. In this study, we can construct optimal codes based on a hash property of an ensemble of functions. In particular, we can prove that code constructions using sparse matrices can achieve the Shannon limits for a general source/channel. In this talk, the outline of the study is explained by using the channel coding problem (error correcting codes) as an example.