2015年4月7日火曜日

第35回助教の会


 今回の助教の会は数理1研の本多が「polar符号および非対称通信路の符号化について」ということで情報理論の最近の結果に関する発表をしました.polar符号は2008年に提案された比較的新しい符号で,符号長に対して多項式時間で指数関数的に小さい復号誤り確率が達成できること示された初めての符号になります.
 情報理論で扱う多くの符号が符号理論特有の手法により解析を行うのに対して,polar符号では分極現象という確率過程に関する基本的な結果から導かれる現象を用いた説明がなされ,情報理論にあまりなじみがない人にはおそらく最も分かりやすい符号になっています.もう少し具体的には,「確率変数のコピーを用意してそれらを可逆な演算により対称性を崩す」という操作を再帰的に繰り返すことにより,値が一意に定まる確率変数と完全にランダムな確率変数に分離することができることから,後者の確率変数のみにより元の確率変数全体をほぼ一意に表現できる(→無歪み圧縮ができる)ほか,前者の確率変数を用いることで情報を誤りなしで伝送することができる,というものです.
 また,初めに提案されたpolar符号は通信路が対称,つまり0が1に反転する確率と1が0に反転する確率が等しい場合のためのものでしたが,これをpolar符号による無歪み圧縮とpolar符号による通信路符号化を組み合わせることにより非対称な通信路に対しても理論限界を達成することができます.
 後半では,非対称の通信路に対してより良い性能を達成する符号の構成についても説明しましたが,こちらは未発表の内容を含むためここでは割愛させて頂きます.

数理第一研究室 本多淳也