九州大学学術情報リポジトリ
Kyushu University Institutional Repository
SSReflectによる可変長情報源符号化逆定理の形式化
小尾, 良介
千葉大学理学研究科
http://hdl.handle.net/2324/1520937
出版情報：MI lecture note series. 61, pp.11-15, 2015-03-06. Institute of Mathematics for Industry, Kyushu University
バージョン：
権利関係：
可変長情報源符号化逆定理
情報源符号化について
情報源符号化とはデータ圧縮のこと． 可変長情報源符号化のモデル 情報源が無記憶な分布になってる． 例： ある程度長い系列：背景
の定理
「」における， の定理一覧背景
背景
情報理論の形式化の意義 曖昧な表現の存在を十分大きくすると 近年の情報理論は証明の大規模化現代符号理論，シャノン理論． による形式化 四色定理（，） の定理（，） の定理（，）による 可変長情報源符号化逆定理の形式化
小尾 良介 萩原学（千葉大学） 山本光晴（千葉大学） 千葉大学理学研究科可変長情報源符号化逆定理 可変長情報源符号化逆定理 任意の一意復号可能な符号の平均符号長は， を満足する． 正整数を取る確率変数に従う分布を， ビット列を取る確率変数に従う分布をとする．
可変長情報源符号化逆定理 正整数を取る確率変数のエントロピーの上界 正整数を取る確率変数について，
証明 確率変数
に従う確率分布を，とする． このとき，対数和不等式より， の定義の展開，及び，が成り立つことから， 任意の無限和が収束する非負数列及びについて， が成り立つ．
可変長情報源符号化逆定理 個の確率変数（それぞれが分布に従う） 分布のエントロピー ビット列の長さ 可変長情報源符号化逆定理 任意の一意復号可能な符号の平均符号長は， を満足する． 一意復号可能であるによる像の長さの平均は，ビットより小さくでき ない． ならば，圧縮後の長さの平均を ビットより小さくできない．
可変長情報源符号化逆定理
情報源符号化について
一意復号可能な符号 例： 一意復号可能な符号 符号化写像が一意復号可能な符号であるとは，の拡張 が単射であることである．
極限の扱い
総和の扱い
情報理論では，総和が頻出する． 例有限集合上の分布の満たす性質： 分布のエントロピー： 有限和であれば，では関数を用いて，総和を記述できる． 紙上 ：有限順序数可変長情報源符号化逆定理 符号化写像の型（） 平均符号長（）の定義 （可変長情報源符号化逆定理） 任意の一意復号可能な符号の 平均符号長は， を満たす．
可変長情報源符号化逆定理 符号化写像をに拡張する． を先の不等式に適用する， の定義より 両辺をで割る
可変長情報源符号化逆定理 性質；エントロピーの上界，及び，補題より， のとき， エントロピーの上界より，直ちに題意が満たされる． のとき，より， より，
極限の扱い
論法
無限和を避けることはできたが，証明の最後の は極限を取らざるを得ない． では，論法を扱うための定理がある： ここで，任意に取れるを以下の値に定めた：極限の扱い
総和の扱い
とする． ならばなので に置き換えることで，関数が使える：極限の扱い
総和の扱い
に従う分布を． だが，無限まで和を取る必要がない．極限の扱い
総和の扱い
テキストの証明では無限和を扱う． 例： は計算可能な関数しか書けない． 無限和は，関数だけでは書けないので，述語を使う． もし無限和を扱うと，述語原因で，式が煩雑に 例：，がで 無限和を避けたいので，証明を工夫．おわりに
まとめ
本研究にて形式化した定理： 可変長情報源符号化逆定理 一意復号可能な符号の性質， 符号化写像が一意復号可能ならばは単射． の拡張も一意復号可能 今後の研究題目： 別証明での，可変長情報源符号化定理の形式化おわりに 植松友彦，植松友彦，現代シャノン理論タイプによる情報理論，培風館，
