検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
数理情報科学特論Ⅲ
| 令和２年度以降入学者 | 数理情報科学特論Ⅲ | ||||
|---|---|---|---|---|---|
| 教員名 | 齋藤明 | ||||
| 単位数 | 2 | 課程 | 開講区分 | 文理学部 | |
| 科目群 | 地球情報数理科学専攻 | ||||
| 学期 | 後期 | 履修区分 | 選択必修 | ||
| 授業の形態 | 対面授業 BlackBoard コースID：20224917 |
|---|---|
| 授業概要 | 符号理論の初歩を学ぶ。主にブロック符号について、通信時の誤り訂正の仕組みを理解する。 |
| 授業のねらい・到達目標 | 線形代数的な符号をを理解し、使いこなすことができる。 |
| 授業の方法 | (1) 授業の形式︓【 講義 】 板書とスライドにより基本事項を説明する。また適宜授業内課題を与える。与えた課題について は、講義時間内に解説を⾏う。 (2) 対⾯授業に参加できない学⽣への代替⽅法、要件対⾯授業に参加できない場合、以下の要件を満たす学⽣は、別途実施するオンライン授業（Zoom）への参加を認める。 オンライン授業への参加を認める要件︓学部の⽅針に従う オンライン授業の⽅法︓予め授業資料を渡し、対⾯授業とは別の時間枠で反転授業を⾏う。授業時間は受講者との協議の上で決めていく。 |
| 授業計画 | |
|---|---|
| 1 |
符号理論の概念について学ぶ。例として7ビットのハミング符号を取り上げる。【対面】
【事前学習】予め配布する資料を読んでおくこと。 （1時間） 【事後学習】講義で紹介した符号を用いて、授業内で提示する受信語について、１ビットの誤りを訂正する。 （3時間） |
| 2 |
体と線形符号の概念を学ぶ。【対面】
【事前学習】学部の講義「線形代数」で学んだベクトル空間の公理的定義を復習する。 （2時間） 【事後学習】講義で出題する部分空間の判定問題を解く。 （2時間） |
| 3 |
生成行列とその規約標準形を学ぶ。【対面】
【事前学習】学部の講義「基礎線形代数」で学んだ行列の基本演算を復習する。 （2時間） 【事後学習】講義で出題する生成行列の既約標準形を求める。 （2時間） |
| 4 |
パリティチェック行列とそれを用いた誤り検出の方法を学ぶ。【対面】
【事前学習】 学部の講義「線形代数」で学んだ直交補空間の概念を復習する。。 （2時間） 【事後学習】講義で得られた生成行列から、対応するパリティ検査行列を求める。 （2時間） |
| 5 |
符号の最小距離と復号の概念を学ぶ。【対面】
【事前学習】距離空間の定義と性質を調べる。 （2時間） 【事後学習】ハミング距離が距離の公理を満たすことを証明する。 （2時間） |
| 6 |
有限体と体上の多項式の概念を学ぶ。【対面】
【事前学習】実数係数の多項式の計算について復習する。 （2時間） 【事後学習】講義内で出題する多項式の計算問題を解く。 （2時間） |
| 7 |
規約多項式と原始元、原始規約多項式の概念を学ぶ。【対面】
【事前学習】実数上では既約だが、GF(2)上では可約な多項式の例をできるだけ多く見つける。 （2時間） 【事後学習】講義で出題する多項式の既約性を判定する。 （2時間） |
| 8 |
有限体の構成法を学ぶ。【対面】
【事前学習】第７回の講義で現れた原始元について、いくつか計算例を作る。 （2時間） 【事後学習】講義で用いたものとは異なる原始既約多項式でGF(16)を構成する。。 （2時間） |
| 9 |
巡回符号の概念を学ぶ。【対面】
【事前学習】これまでの講義に現れた線形符号について、各符号語を巡回シフトしても符号語に留まるか否かを考察する。 （2時間） 【事後学習】講義で与えた巡回符号の生成多項式と検査多項式を求める。 （2時間） |
| 10 |
巡回符号の性質を学ぶ。特に生成行列とパリティチェック行列の性質を調べる。【対面】
【事前学習】前回の講義で与えられた巡回符号の生成多項式を基底から求める （2時間） 【事後学習】生成多項式から得られた生成行列と事前学習で得た生成行列を比較する。 （2時間） |
| 11 |
BCH符号の構成法とその性質を学ぶ。【対面】
【事前学習】GF(2)上の多項式の根について、その２乗を多項式に代入するとどうなるかを実験しておく。 （2時間） 【事後学習】BCH符号の例を１つ作る。 （2時間） |
| 12 |
Reed-Solomon符号の構成法とその性質を学ぶ。【対面】
【事前学習】以前の講義に現れたGF(16)の構成法を復習する。 （2時間） 【事後学習】講義に現れたものとは異なる Reed-Solomon符号の例を１つ自作する。 （2時間） |
| 13 |
2-誤り訂正BCH符号を例に取り、BCH符号の復号の仕組みを学ぶ。【対面】
【事前学習】GF(16)上で２次方程式を解く練習をする。 （2時間） 【事後学習】2-誤り訂正BCH符号について、講義で渡された符号語を訂正する。 （2時間） |
| 14 |
Gilbert-Varshamov 限界を学び、線形代数的符号理論から代数幾何符号への研究の展開を概観する。【対面】
【事前学習】球詰め限界、Singleton限界について予習する。 （2時間） 【事後学習】球詰め限界とGilbert-Varshamov 限界の違いを復習する。 （2時間） |
| 15 |
畳み込み符号の概念を学ぶ。【対面】
【事前学習】有限オートマトンについて復習する。 （2時間） 【事後学習】畳み込み符号とブロック符号の違いを復習する。 （2時間） |
| その他 | |
|---|---|
| 教科書 | なし。 |
| 参考書 | 先名健一 『例題で学ぶ符号理論入門』 森北出版 2011年 第1版 |
| 成績評価の方法及び基準 | レポート:第13回講義終了後に１回のレポートを課す。(30%)、授業参画度:授業外演習の提出状況と内容(70%) |
| オフィスアワー | 毎週⽕曜⽇ 12:20〜13:00 に研究室で⾏う。またメール（[email protected]）での質 疑応答も受け付ける。 |