| 准教授 | 森野博章 |  |
情報理論２ |
Information Theory |
開講部 | 工学部 |
開講学科 | 通信工学科 |
開講学年 | 2年次 |
開講時期 | 後期 |
単位数 | 2 |
単位区分 | 選択 |
系列区分 | 専門 |
講義区分 | 講義 |
| 准教授 | 森野博章 | |
| 1. | 誤り訂正符号・誤り検出符号の原理を理解する． |
| 2. | 巡回符号等，非2元巡回符号，リードソロモン符号による符号化・復号の処理に習熟する。 |
| 3. | グラフ理論を用いたネットワークシステムの解析について，その原理を理解し，具体的な問題が解けるようになる。 |
| 【授業計画】 | 【授業時間外課題（予習および復習を含む）】 | |
| 1. | 誤り訂正符号の基礎 ・誤りを生じる通信路のモデル化 - BSC(Binary Symmmetric Channel) ・通信路によって運ばれる情報量（相互情報量） ・誤り訂正符号・誤り検出符号の原理 - 符号の幾何学的表現、ハミング距離 - 単一パリティ符号 | 高校課程の「確率と統計」を復習する． |
| 2. | 巡回符号（１） ・2元系列の多項式表現 ・多項式の加減乗除 ・巡回符号の基本的な性質 | 誤り訂正符号・誤り検出符号の原理について，問題演習を復習する． |
| 3. | 巡回符号（２） ・生成多項式 ・符号化と復号 〜シンドロームによる誤り検出〜 | 巡回符号の符号化法と復号法を復習する． |
| 4. | 巡回符号（３） ・巡回符号の連続誤り検出能力 ・シフトレジスタによる復号器の実現 ・実システムで利用されている巡回符号 ・巡回ハミング符号 - 生成多項式の周期 - 1ビット誤り訂正復号 | 巡回ハミング符号について，具体的に与えられた系列に対する符号化法，誤り訂正復号演算ができるように復習する． |
| 5. | 情報ビットブロック単位で誤り訂正を行う符号（１） ・バースト誤りに対するブロック単位誤り訂正の有用性 ・剰余多項式によるブロックへの記号割り当て ・多項式の解のべき乗表現とブロックとの対応付け ・ブロック同士の加減乗除演算 | 多項式の解のべき乗表現と情報ビットブロックの対応方法について復習する． |
| 6. | 情報ビットブロック単位で誤り訂正を行う符号（２） ・非2元巡回ハミング符号 - 符号化と復号 - 誤り訂正能力 | 非2元巡回ハミング符号の符号化と復号方法について復習する |
| 7. | 中間試験および問題解説 | 第一回から第六回までの内容を復習する． |
| 8. | グラフ理論の基礎（１） ・イントロダクション - グラフ理論とは - グラフ理論の端緒 - ケーニヒスベルグの橋問題 - 集合によるグラフの表記 - 路，経路，回路，閉路 - オイラー路とオイラーグラフ - グラフ理論とネットワーク理論の用語対比 | 高校課程で学習した「集合」の内容を復習する． |
| 9. | グラフ理論の基礎（２） ・リンクに対するコスト設定 ・通信ネットワークにおけるリンクコストの設定法 ・最短経路探索問題の求解 ・ダイクストラ法 ・最小全域木の構築 ・ブロードキャスト・マルチキャスト通信における 最小全域木の有用性 ・プリム法 | グラフを用いた通信ネットワークのモデル化について復習する． |
| 10. | グラフ理論の基礎（３） ・グラフの連結性からみたネットワークの信頼性評価 ・連結性尺度 - 点連結度 - 枝連結度 ・ネットワークの経路信頼性評価 ・予備経路による障害対応 ・リンク独立経路とノード独立経路 ・メンガーの定理 | リンクコスト，最短経路探索問題，最小全域木構築問題について復習する． |
| 11. | グラフ理論の基礎（４） ・ネットワークフローとは ・リンクが容量をもつグラフにより解かれる問題の例 − 回路網，道路網，，， ・フローの定義 ・最大フロー問題 ・最大フロー算出の一般的なアルゴリズム ・フォード・ファーカルソンアルゴリズム ・残余グラフによるリンク容量の可視化 | グラフの連結性尺度について復習する． |
| 12. | グラフ理論の基礎（５） ・有向グラフのカットと最小カット ・最大フロー・最小カット定理 ・問題演習 | 最大フロー算出のアルゴリズムについて復習する |
| 13. | 総合問題演習 | 第八回から第十二回までの内容を復習する． |
| 14. | グラフ理論の基礎（６） ・通信ネットワーク分野においてグラフ理論により 解かれる問題の例 | 第八回から第十三回までの内容を復習する． |
| 15. | 学期末試験および問題解説 | 第八回から第十四回までの内容を復習する． |
| ・ | 講義終了後 |