植松研究室

smooth Renyiエントロピーによる情報理論の統一的な取扱い

smooth Renyiエントロピーを用いて、一般情報源に対する符号化問題、resolvability問題、intrinsic randomness問題について 新しい統一的な方法を確立しました。smooth Renyiエントロピーを用いることで、Hanが情報スペクトルを用いて示した成果を、 確率的上極限や下極限を用いずに通常の極限を用いて与えることができます。また、smooth Renyiエントロピーの操作的な意味は明確 であり、各種問題についての直感的な解釈を与えることができます。

トレーニング系列を用いた乱数生成に関する研究

任意の情報源から出力された十分長い系列（トレーニング系列と呼ぶ）と 真の乱数列を利用して、その情報源と統計的に同一の性質を有する系列を 生成する問題が「トレーニング系列を用いた乱数生成問題」です。 この問題は「情報源のユニバーサルシミュレーション問題」とも呼ばれ、 物理学等における応用を有しています。
　 植松研究室では、実用性を考慮し有限精度の演算によって 乱数生成を行うアルゴリズムを検討すると共に、 長さnの乱数系列の生成に必要な、真の乱数列の長さや 演算語長について評価を行っています。

無限系列が真の乱数と識別できないための条件

無限に長い０と１の系列が与えられたとき、有限長系列に関する乱数判定法では真の乱数と区別できないための 必要十分条件が下記の３条件の各々と等価であることを示すのに成功しました。

• 有限状態機械では過去の系列から次の1ビットを予想できない
• 有限状態機械ではこの系列を圧縮できない
• この系列の経験分布が一様分布であること

更に、Lempel-Ziv78符号で圧縮できない無限系列は、上記の２番目の条件を満たし、真の乱数と区別 できないことを明らかにしました。この研究は、乱数の本質に対して新たな知見を与えるものです。

乱数の生成に関する研究

曲がったコインを振って１ビットの乱数（０と１の出る確率が共に等しい乱数）を作るにはどうすれば良いでしょうか？　
(答え)コインを２度振って表裏の順に出たら１、裏表の順に出たら０とし、表表および裏裏が出たら改めてもう２度振る。
それでは、曲がったコインを振ってkビットの乱数を作るには平均何回コインを振ればよいでしょうか？　
(答え）ほぼk／H回になります。 但し、Hは曲がったコインの表と裏の出る確率から計算されるエントロピーです。
　 このように乱数の生成はエントロピーと密接な関係があり、情報理論的な乱数の性質を明らかにすると共に、与えられた情報源から効率的に乱数を生成する方法について研究を行っています。

万能な情報圧縮アルゴリズムに関する研究

通信理論で習ったハフマン符号は、情報源から出力される各記号の生起確率を知らないと符号を構成することができませんでした。これに対して、予め情報源の性質を知らなくても符号化が行え、しかも、入力データが長くなるにつれて圧縮率が情報源のエントロピーレートに収束するという性質を有する符号を「ユニバーサル（万能） 符号」といいます。
　 最も実用的なユニバーサル符号としてLempel-Ziv符号が知られており、現在、パーソナルコンピュータのデータ圧縮ツール(LHA, ZIP等)として広く用いられています。
　 植松研究室では、ユニバーサル符号による圧縮率がエントロピーレートに収束する速度や、ユニバーサル符号を用いた通信路符号の復号法などについて研究を行っています。