科目名 |
符号理論 |
担当教員 |
福本 昌弘 |
対象学年 |
3年 |
クラス |
学部:専門001 |
講義室 |
A107 |
開講学期 |
1学期 |
曜日・時限 |
火3,金3 |
単位区分 |
選択 |
授業形態 |
一般講義 |
単位数 |
2 |
準備事項 |
|
備考 |
|
授業の詳細1 |
授業の目的 現在ではあらゆる場面でネットワークを通じて種々の情報を得ることが当たり前になっており、情報を伝送したり記録したりする場合には、正確さや信頼性、安全性などが強く求められている。このためには、情報をいかに符号化するかが重要になってくる。 この授業は、主に情報学群専門基礎科目「情報代数」や「情報理論基礎」で修めた知識をもとに、誤り訂正符号等の符号理論を学ぶために必要となる、代数系に代表される数学的な基盤と誤り訂正符号の基本を修得する。 この授業では、まず符号の誤りとその検出、訂正の条件などの基本的なことがらを理解し、有限体やなど必要となる代数学の基礎を学ぶ。そして、線形符号の概念を修得した上で、実用的な誤り訂正符号について学ぶ。
キーワード 有限体、誤り検出、誤り訂正、線形符号、巡回符号 |
授業の詳細2 |
授業の進め方 板書と資料を用いて行なう。きちんとノートをとり、予習・復習を行うことが理解への第一歩となる。授業の進度に応じて演習を実施し、理解度を確認する。
達成目標 (1) 誤り検出/誤り訂正の仕組みと数学的基礎を理解できる。 (2) 線形符号の概念をとらえられる。 (3) 巡回符号をはじめ、誤り訂正符号を利用できる。 |
授業の詳細3 |
授業計画 1. 情報源符号化と通信路符号化 まず、この授業全体で学習することを概観した後、情報源符号化と通信路符号化のそれぞれの役割を整理する。 2. ハミング距離 誤り検出・訂正の性能や符号語の違いを表すハミング距離について理解する。 3. 誤り検出・訂正の能力 誤り検出と誤り訂正の原理を理解し、その限界をハミング距離で表現する。 4. 有限体 誤り訂正符号を構成するための代数体である有限体の数学的基礎を学ぶ。 5. 素体と原始元 もっとも基本的な有限体である素体(基礎体)と、その要素をべきにより生成するための原始元について学ぶ。 6. 有限体上の多項式 2進数で表現できる符号を構成する有限体として拡大体を利用するために、その元を表現するための基礎となる有限体の元を用いた多項式の表現について修得する。 7. 既約多項式 拡大体上の原始元に相当する働きをする原始多項式となる既約多項式を用いて拡大体の元の表し方を理解する。 8. 拡大体 拡大体上での演算や性質をとらえる。 9. 演習 1. 誤り検出・訂正能力と有限体に関する演習を行い、理解度を確認する。 10. 線形符号 検査ビットと情報ビットで誤り訂正符号が構成できることを理解し、そのそれぞれが線形の関係となる線形符号の特徴を理解する。 |
授業の詳細4 |
11. 検査行列とシンドローム 線形符号の検査行列とシンドロームを用いて誤りの検出と訂正ができることを学ぶ。 12. ハミング符号 もっとも基本的な線形符号であるハミング符号の構成について学ぶ。 13. 演習 2. 線形符号とハミング符号に関する演習を行い、理解度を確認する。 14. 巡回符号 生成多項式を用いて構成される巡回符号の特徴を理解する。 15. BCH符号とリード・ソロモン符号 巡回符号であるBCH符号と、実用的な誤り訂正符号であるリード・ソロモン符号につ いて学ぶ。 16. 演習 3. 巡回符号に関する演習を行い、理解度を確認する。 17. 習熟度確認 有限体と誤り検出・訂正、符号に関する総合的な課題により習熟度を確認し、修得状況を評価する。 自筆ノーとを持ち込み可とする。 18. まとめ 課題の結果を確認し、解答例を参考にしながらこの授業で学んだことを振り返る。 |
授業の詳細5 |
成績評価: 総合的な課題で達成度の評価を行う。 ●AA:課題の全ての問題を理解した上で正確に解ける ● A:課題の全ての問題の基本的な考え方を理解した上でほぼ正確に解ける ● B:課題の半分以上の問題の基本的な考え方を理解した上でほぼ正確に解ける ● C:課題の半分以上の問題の基本的な考え方を理解した上で部分的には解ける
テキスト: 「C言語による情報理論入門」, 久保田一, 大石邦夫, 福本昌弘 著(コロナ社, 2007.5)ISBN978-4-339-02421-0
参考書 「代数系と符号理論入門」, 坂庭好一, 渋谷智治 著(コロナ社, 2010.4)ISBN978-4-339-02446-3 「誤り訂正符号と暗号の基礎数理」, 笠原正雄, 佐竹賢治 著(コロナ社, 2004.3)ISBN4-339-01054-5 「例題で学ぶ符号理論入門」, 先名健一 著(森北出版, 2011.7)ISBN978-4-627-81741-8 「応用 情報数学」, 横森貴, 小林聡 著(サイエンス, 2011.6)ISBN978-4-7819-1288-2 |
授業の詳細6 |
履修上の注意: ・「コンピュータサイエンス専攻」専門発展科目 ・事前の履修が望ましい科目=「情報代数」、「情報理論基礎」
・この授業のより詳細な情報は http://www.info.kochi-tech.ac.jp/mfukumot/Lecture/CT/index.html に掲載する。
オフィスアワー: 毎週火曜日 第5時限(16:30?) A418教員室 |
授業の詳細7 |
|
授業の詳細8 |
|
授業の詳細9 |
|
授業の詳細10 |
|