情報理論・確率論（平成23年度前期） 宮崎明雄

テキスト：大石進一、例にもとづく情報理論入門、講談社、1993年

配付資料：�@ 確率の計算（5月9日）

　　　　　�A 符号化と復号、符号の木、クラフトの不等式など（5月30日）

　　　　　�B エントロピー、ハフマン符号など（6月6日）

　　　　　�C 対数について（数学基礎演習の教科書より）（6月13日）

　　　　　�C 情報量の従う方程式（6月13日）

　　　　　�D 情報量とエントロピー（6月20日）

　　　　　�E エントロピー、相互情報量の計算（6月27日）

　　　　　�F 通信路方程式、最尤復号法、通信路容量（7月11日）

　　　　　�G 練習問題（7月18日）

※印の内容は大学院の授業（情報セキュリティ特論又は情報数理特論）で説明する。

--------------------------------第１回（4月11日）

0　講義の概要

・ 情報理論：1948年、シャノン（C. E. Shannon）の論文“A Mathematical Theory of Communication（通信の数学的理論）”（Bell System Tech. J.）によって誕生。

・ 情報量の定量化：情報を確率・統計的に扱うこと。情報を理論的、定量的に扱えるように情報量を定義し数値化すること。

・ 符号の高能率化（情報源符号化）：情報量を失わずにデータ全体の長さを短くする符号化の方法（データ圧縮）。

・ 符号の高信頼化（通信路符号化）：通信や記録の途中の雑音によって生じる符号の誤りに対処できる符号化の方法（誤り検出符号、誤り訂正符号）。

・ 情報伝送の流れ（モデル）：情報源、メッセージ（通報）、符号化、符号列、通信路（伝送路）、雑音、復号化、など。

1　確率論の基礎

1.1　集合・・・「離散数学�T（１年次前期）」の内容を復習し、用語などをもう一度確認しておくこと。

--------------------------------第2回（4月18日）

1.2　試行、試行列と事象

−事象：試行の可能な結果の集合

−全事象、事象、根元事象

1.3　確率と確率空間

−確率の定義

−確率の性質

�@ 確率のとり得る値

�A 確率の加法定理

�B 余事象の確率

�C 和事象の確率

--------------------------------第3回（4月25日）

�D 独立な試行の確率

�E 反復試行の確率

1.4　確率変数と確率分布

1.5　確率変数の平均値（期待値）と分散

　　−平均値と分散の定義と意味

　　−確率変数の線形変換と期待値・分散

--------------------------------第4回（5月9日）

−確率変数の和の期待値

1.6　条件付確率

　　−条件付確率の定義

　　−確率の計算

1.7 ベイズの定理

P(A|B) ＝ P(B|A)P(A)／P(B)

1.8 確率変数の独立性

−確率変数の独立性

--------------------------------第5回（5月16日）

−独立な確率変数の積の期待値

−独立な確率変数の和の分散

1.9 確率分布の例

一様分布、二項分布、・・・

1.10 確率の計算

1.11　大数の法則

�@ チェビシェフの不等式

�A 大数の法則

1.12　マルコフ過程（※）

--------------------------------第6回（5月23日）

2　情報源符号化

2.1 情報源のモデルと情報源符号化問題

�@ 情報源の統計的モデル化

�A 無記憶・定常・離散的情報源

�B 情報源符号化の問題

2.2 情報源符号

�@ 2元情報源符号化

�A 符号化、符号語、符号、符号長、平均符号長

�B 復号、一意的に復号可能

�C 固定長符号、可変長符号、瞬時符号、特異符号、非特異符号

2.3 瞬時符号

�@ グラフ＝［節点、枝］

�A パス、連結グラフ、閉路、木

�B 符号の木、2分木、葉

�C 瞬時符号

�D 復号木

--------------------------------第7回（5月30日）

・「レポート課題：確率の計算（5月23日提出締切）」の解説

2.4 クラフトの不等式による瞬時符号の幾何学的特徴付け

2.5 符号空間

2.6 一意的に復号可能な符号

�@ 瞬時符号、非瞬時符号

�A クラフト−マクミランの不等式

2.7 平均符号長とエントロピー

u 一意的に復号可能な符号Cの平均符号長Lは、情報源SのエントロピーH(S)より短くすることはできない。

u どのくらい短い平均符号長をもつ一意的に復号可能な符号が作れるか？

-------------------------------第8回（6月6日）

2.8 情報源符号化定理

�@ ｎ次の拡大情報源（配付プリントの例題で解説）

�A ブロック符号化（配付プリントの例題で解説）

�B 情報源符号化定理：「情報源符号化の効率の限界と、その限界に任意に近い効率を持つ情報源符号の存在を保証する。」

3　いろいろな情報源符号

3.1 ハフマン符号

�@ 情報源と縮退情報源

�A ハフマン符号化アルゴリズム

3.2 コンパクト符号

�@ コンパクト符号：「情報源に対する瞬時符号の中で最短の平均符号長をもつ符号」

�A ハフマン符号はコンパクト符号

3.3 マルコフ情報源と状態遷移図（※）

3.4 エルゴード的マルコフ情報源（※）

3.5 マルコフ情報源に対する情報源符号化（※）

3.6 ランレングス符号（ランレングスハフマン符号）（※）

3.7 情報源符号化とアルゴリズム（2−パスハフマン符号化）（※）

3.8 ZL符号（Ziv‐Lempel符号）（※）

--------------------------------第9回（6月13日）

・「レポート課題：符号化と復号、符号の木、クラフトの不等式（6月6日提出締切）」の解説

４　情報量とエントロピー

4.1 情報量（＝あいまいさの減少分）

4.2 情報量の従う方程式

4.3 アルゴリズム的情報量（系列の複雑さとプログラムの長さ）（略）

4.4 エントロピーの関数としての性質

u エントロピーは非負（H(S)≧0）である。

u エントロピーが最大になるのは、確率分布が一様分布のとき。

-------------------------------第10回（6月20日）

4.5 条件付エントロピー、結合エントロピー

4.6 相互情報量“I(X,Y)=H(X)-H(X|Y)”：Yを知ることによってもたらされたXに関する情報量

◆ エントロピー、条件付エントロピー、結合エントロピー、相互情報量の間の関係

-------------------------------第11回（6月27日）

・「レポート課題：ハフマン符号、エントロピー（6月20日提出締切）」の解説

◆ エントロピー、条件付エントロピー、結合エントロピー、相互情報量の間の関係（復習）

・例題：エントロピー、条件付エントロピー、相互情報量の計算

-------------------------------第12回（7月4日）

５　通信路符号化の限界

5.0 概要

u 通信路符号化問題：雑音を受ける通信路を通して信頼性を保ちながら、いかに効率的に情報を伝送するか？

u シャノンによる情報通信のモデル

5.1 通信のモデル

�@ 通信路行列、通信路方程式

�A ベイズの定理

5.2 通信路容量：「与えられた通信路を通して最も効率的に通信を行ったときに、受信記号1記号当り得られる平均の情報量」

5.3 最尤復号化：ベイズの定理、最尤復号法と平均誤り率

-------------------------------第13回（7月11日）

5.4 2元対称通信路

5.5 2元対称通信路の通信路容量

5.6 2元対称通信路に対する最尤復号化

5.7 平均誤り率

・例題：通信路方程式、最尤復号化と平均誤り率、通信路容量の計算

-------------------------------第14回（7月18日）※海の日（月曜授業実施日）

5.8 通信路符号化

�@ 通信路符号化＝誤り検出・誤り訂正を行うことによって、平均誤り率を小さくする手法

�A 多数決符号とその平均誤り率

�B 情報速度ｒ＝(情報部分のビット数)÷(通信路符号語のビット数)

-------------------------------第15回（7月25日）

5.9 ハミング距離（⇒「６ 符号理論」のところで説明）

5.10 通信路符号化定理：「通信路容量がCの通信路が与えられているとする。このとき任意に小さな正数εとδに対して、情報速度（全符号長に対する情報ビットの割合）がC−εで、誤り確率がδ以下となる通信路符号が存在する。」（シャノンによる証明：ランダム符号化による通信路符号化の方法）（証明は省略、結果のみ紹介）

5.11 通信路符号化定理の証明のための補題（略）

・講義のまとめ、演習（練習問題）

--------------------------------

６　符号理論

6.1 パリティチェック

6.2 剰余演算

�@ 雑音による誤りの数学モデル

�A 排他的論理和

�B 剰余演算（a mod p）

�C 体（field）、有限体、ガロア体GF(q)

6.3 パリティチェック符号

6.4 長方形符号

6.5 三角形符号

（5.9 ハミング距離）

6.6 ハミング符号

6.7 生成行列とパリティチェック行列

−誤り訂正の仕組み−

【送信側（符号化）】

情報ベクトルをｘとする。

生成行列Ｇを用いてｘを符号ベクトル（送信ベクトル）ｃに変換する（ｃ＝Ｇｘ）。

【受信側（誤り訂正と復号化）】

受信ベクトルをｚとする。

パリティチェック行列Hを用いてｚからシンドロームベクトルｓを計算する（ｓ＝Ｈｚ）。

ｓ＝０（零ベクトル）のときは、誤りなしと判定し、受信ベクトルから情報ベクトルｘを取り出す。

ｓ≠０のときは、ｚの誤り位置とｓの対応関係より誤り位置を特定し、誤りを訂正する（0,1を反転する）。そして、訂正後の受信ベクトルから情報ベクトルｘを取り出す。

6.8 組織符号

6.9 符号の最小距離（符号の誤り訂正能力）

�@ ハミング距離

�A 符号の最小重みと最小距離

�B 限界距離復号法と符号の誤り訂正能力：ある符号の最小距離dがd≧2t+1（ただしtは正整数）を満たすとする。この符号に対して、各符号語を中心としてハミング距離で半径tの球に入った受信語はその球の中心の符号語に復号する、という復号規則（限界距離復号法）を設けたとき、この符号は符号語にt個以下の誤りが生じても正しく復号される（符号の誤り訂正能力）。

6.10 ベクトルと多項式（略）

6.11 原始多項式と拡大体（略）

6.12 ハミング符号と符号生成多項式（略）