符号理論（Coding Theory）[2D10]

＜授業のねらい＞

コンピュータ処理の性能は目覚しく進展し、その容量の大きさ、スピードは日々向上しているといっても過言ではない。これには効率的でかつ付加的機能が充実した、符号化の恩恵がはかり知れない。ここでは、情報理論を基礎に、符号化の考え方を学び、基礎的な符号化の主なものが実践できるまでになることをねらいとする。

＜受講にあたっての前提条件＞

必修の情報理論が習得されていること。

＜具体的な到達目標＞

符号化にはハフマンの符号化法などの高効率符号化法と、巡回符号やリードソロモンなどの誤り訂正符号化法がある。これらについて、その原理と具体的は方法を学び、それらによる簡単な符号化応用ができることを到達目標とする。

＜授業計画及び準備学習＞

１． [イントロダクション]全般的な符号化法の考え方について概説する。
　　　符号化を行う目的や意義について説明する。
　　　準備学習：教科書7.1、7.2の解説のところを読んでくること。　　　
２． 情報源記号と具体的な符号例。
　　　符号化する情報源記号のモデル記号を挙げて、モデル符号化を示し、符号化の要件を考える。
　　　準備学習：教科書7.1の最初の表から符号例を確認し、解説をよく読んでおくこと。　　　
３． 符号の条件、評価の考え方、種類。
　　　前回に引き続き、符号化の要件を具体的に挙げ、その評価法を解説する。
　　　準備学習：教科書7.1〜7.3のところの特に符号化の良否について予習しておくこと。　　　
４． 符号の条件とその判断方法。（符号の木とクラフトの不等式）
　　　符号化の良否、評価を与える、符号の木とクラフトの不等式などを解説する。
　　　準備学習：教科書7.3〜7.5について予習しておくこと。
５． シャノンの第１基本定理とハフマンの符号化法
　　　高効率符号化のハフマンの方法を解説する。
　　　準備学習：教科書7.6、8.1,8.2について予習しておくこと。
６． マルコフ情報源の符号化法
　　　マルコフ情報源に場合のハフマンの符号化法最適化について解説する。
　　　準備学習：教科書8.4について予習しておくこと。
７． その他の高効率符号化法
　　　ハフマン以外の方法について紹介する。
　　　準備学習：教科書8.5について解説のところを読んでくること。
８． シャノンの第２基本定理（雑音がある場合の符号化）
　　　誤り訂正符号化法の考え方を解説する。
　　　準備学習：教科書11.3または参考書の標記定理等からこの定理の下調べをしておくこと。
９． ハミング距離、パリティー検査法、誤り検出/訂正の原理
　　　前回に引き続き、上記の事項を中心に解説する。
　　　準備学習：参考書の標記項目、または、キューポートにアップ予定の電子教材を予習のこと。
10． ハミングの符号化法―検査符号の生成方法と誤り訂正方法―
　　　具体的な誤り訂正符号化法の上記方法を解説する。
　　　準備学習：教科書11.5〜12.1について予習しておくこと。
11． 巡回符号化法―符号の生成方法と誤り訂正方法―
　　　実用的な誤り訂正符号化法の一つの上記方法を解説する。
　　　準備学習：参考書の標記項目、または、キューポートにアップ予定の電子教材を予習のこと。
12． リードソロモンなど現代符号化法の基礎となるガロア体について
　　　有限個の元による四則演算であるガロア体を解説する。
　　　準備学習：キューポートにアップ予定の電子教材の上記項目を予習のこと。
13． 拡張ガロア体による巡回符号
　　　拡張ガロア体について解説し、これによって巡回符号方式がどのように発展するかを学ぶ。
　　　準備学習：キューポートにアップ予定の電子教材の上記項目を予習のこと。
14． リードソロモン符号の基礎と原理
　　　前回に引き続き、発展した巡回符号によってどのように多数のバースト誤りが訂正できるのかを解説する。
　　　準備学習：キューポートにアップ予定の標記電子教材を予習のこと。
15． 学習成果の確認(試験)
　　　準備学習：前回までの総復習を行う。

＜成績評価方法＞

原則として定期試験で評価し、到達目標に達したと判断できる６０点以上の者に単位を認める。ただし、６０点に満たない者であっても、４週に１回程度行う小問題演習の解答内容が十分であると認められた場合には合格とすることがある。

＜教科書＞

「情報理論入門」野村由司彦著、コロナ社

＜参考書＞

「ディジタル情報理論」塩野充著、オーム社

＜オフィスアワー＞

木曜日、17:00〜18:00、事前にメイル等で申し出ること。これ以外でもその都度個別にメールで約束の上、対応可とする。