数理情報科学特論Ⅳ

科目名	数理情報科学特論Ⅳ
教員名	齋藤明
単位数	2	課程	前期課程	開講区分	文理学部
科目群	地球情報数理科学専攻
学期	後期	履修区分	選択必修

授業概要	符号理論を学ぶ。
授業のねらい・到達目標	符号理論の初歩を学ぶ。主にブロック符号について、通信時の誤り訂正の仕組みを理解する。本講義を通して、符号を構成し使いこなすことができるようになる。この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法	講義を中心に行う。本授業の事前・事後学習は，各２時間の学習を目安とする。

授業計画
1	符号理論の概念について学ぶ。例として7ビットのハミング符号を取り上げる。 [事前学習] 予め配布する資料を読んでおくこと。 [事後学習] 授業で指示する受信語について、１ビットの誤りを訂正すること。
2	体と線形符号の概念を学ぶ。 [事前学習] 学部の講義「線形代数」で学んだベクトル空間の公理的定義を復習すること。 [事後学習] 授業で出題する部分空間の判定問題を解くこと。
3	生成行列とその規約標準形を学ぶ。 [事前学習] 学部の講義「基礎線形代数」で学んだ行列の基本演算を復習すること。 [事後学習] 講義で出題する生成行列の既約標準形を求めておくこと。
4	パリティチェック行列とそれを用いた誤り検出の方法を学ぶ。 [事前学習] 学部の講義「線形代数」で学んだ直交補空間の概念を復習しておくこと。 [事後学習] 講義で生成行列から、対応するパリティチェック行列を求めておくこと。
5	符号の最小距離と復号の概念を学ぶ。 [事前学習] インターネットで「三角不等式」を検索しておくこと。 [事後学習] ハミング距離が距離の公理を満たすことを自力で証明しておくこと。
6	有限体と体上の多項式の概念を学ぶ。 [事前学習] 多項式の計算について復習しておくこと [事後学習] 多項式の計算問題を出題するので、解いておくこと。
7	規約多項式と原始元、原始規約多項式の概念を学ぶ。 [事前学習] 実数上では既約だが、GF(2)上では可約な多項式の例を１つ考えておくこと。 [事後学習] 講義で与える多項式の既約性を判定しておくこと。
8	有限体の構成法を学ぶ。 [事前学習] 前回講義で現れた原始元について、いくつか計算を実行してみること。 [事後学習] 講義で持ちいたものとは異なる原始既約多項式でGF(16)を構成してみること。
9	巡回符号の概念を学ぶ。 [事前学習] 講義で現れた線形符号について、各符号後を巡回シフトするとどうなるか考察せよ。 [事後学習] 講義で与えた巡回符号の生成多項式とパリティチェック多項式を求めておくこと。
10	巡回符号の性質を学ぶ。特に生成行列とパリティチェック行列の性質を調べる。 [事前学習] 前回講義に現れた巡回符号の生成行列を求めてみること。 [事後学習] 生成多項式から得られる生成行列と事前学習で得た生成行列を比較すること。
11	BCH符号の構成法とその性質を学ぶ。 [事前学習] GF(2)上の多項式の根について、その２乗を多項式に代入するとどうなるか計算すること。 [事後学習] 実際にBCH符号の例を１つ自力で構成してみること。
12	Reed-Solomon符号の構成法とその性質を学ぶ。 [事前学習] 以前の講義で用いたGF(16)の構成方を復習しておくこと。 [事後学習] 講義で現れたものとは異なる Reed-Solomon符号の例を構成してみること。
13	2-誤り訂正BCH符号を例に取り、BCH符号の復号の仕組みを学ぶ。 [事前学習] GF(16)上で２次方程式を解く練習をしておくこと。 [事後学習] いくつか受信後を渡すので、その符号を訂正すること。
14	Gilbert-Varshamov 限界を学び、線形代数的符号理論から代数幾何符号への研究の展開を概観する。 [事前学習] インターネットで「球詰め限界」という語を検索しておくこと [事後学習] Gilbert-Varshamov 限界と球詰め限界の違いを確認しておくこと。
15	畳み込み符号の概念を学ぶ。 [事前学習] オートマトンの動作について復習しておくこと。 [事後学習] 畳み込み符号とブロック符号の違いを確認すること。

その他
教科書	教科書は使用しない。
参考書	先名健一『例題で学ぶ符号理論入門』森北出版 2011年第1版
成績評価の方法及び基準	レポート(100%) ３回のレポートを課す。レポートの内容は、いずれも授業で学んだ理論を用いて具体例を計算するものであり、学んだ題材の理解度や計算の正確さを評価する。
オフィスアワー	毎週火曜日と水曜日の 12:10～13:00 をオフィスアワーとする。可能であれば電子メールでアポイントを取ること。電子メールアドレスは授業初回に伝える。アポイントを取らずに来室することも可能だが、アポイントを取ってきた人がいる場合にはそちらを優先する。