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

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

配付資料（配付予定日）

�@ 確率の基礎（Part I）（第2回：4月21日）

�A 確率の基礎（Part II）（第3回：4月28日）

�B 確率の計算（第5回：5月19日）

�C 情報源符号化（定理等のまとめ）（第7回：6月2日）

�D 符号化と復号、符号の木、クラフトの不等式など（第7回：6月2日）

�E 指数と対数について（第7回：6月2日）

�F ハフマン符号化アルゴリズム（第8回：6月9日）

�G エントロピー、ハフマン符号など（第9回：6月16日）

�H 情報量の従う方程式（第9回：6月16日）

�I 情報量とエントロピー（第10回：6月23日）

�J エントロピー、相互情報量の計算（第11回：6月30日）

�K 通信路のモデル、通信路方程式、最尤復号法、平均誤り率、通信路容量（第12回：7月7日）

�L 2元対称通信路、いろいろな通信路モデルと通信路容量の計算（第13回：7月14日）

�M 練習問題（第14回：7月21日 or 第15回：7月28日）

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

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

0　講義の概要

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

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

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

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

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

1　確率論の基礎

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

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

1.2　試行、試行列と事象

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

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

1.3　確率と確率空間

−確率の定義

−確率の性質

�@ 確率のとり得る値

�A 確率の加法定理

�B 余事象の確率

�C 和事象の確率

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

�D 独立な試行の確率

�E 反復試行の確率

1.4　条件付確率

　　−条件付確率の定義

　　−確率の計算

1.5　ベイズの定理

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

1.6　確率変数と確率分布

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

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

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

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

−確率変数の和の期待値

1.8　確率変数の独立性

−確率変数の独立性

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

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

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

1.9 確率分布の例

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

1.10 確率の計算

1.11　大数の法則

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

�A 大数の法則

1.12　マルコフ過程（※）

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

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

2　情報源符号化

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

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

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

�B 情報源符号化の問題

2.2 情報源符号

�@ 2元情報源符号化

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

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

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

2.3 瞬時符号

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

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

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

�C 瞬時符号

�D 復号木

--------------------------------第7回（6月2日）

・「レポート課題：確率の計算（5月19日出題、5月28日提出締切）」の解説（必要に応じて）

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

2.5 符号空間

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

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

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

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

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

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

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

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

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月16日）

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

４　情報量とエントロピー

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

4.2 情報量の従う方程式

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

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

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

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

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

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

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

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

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

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

・「レポート課題：ハフマン符号、エントロピー（6月16日出題、6月25日提出締切）」の解説（必要に応じて）

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

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

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

５　通信路符号化の限界

5.0 概要

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

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

5.1 通信のモデル

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

�A ベイズの定理

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

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

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

5.4 2元対称通信路

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

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

5.7 平均誤り率

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

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

5.8 通信路符号化

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

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

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

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

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 ハミング符号と符号生成多項式（略）