符号理論 シラバス（ポータル） 時間割番号: 1144067001 符号理論 担当教員 福本 昌弘[FUKUMOTO Masahiro] 開講学部等 正規科目 対象年次 3～ 単位数 2 開講時期 2Q 開講曜時 火2,金2 クラス 授業の目的 現在ではあらゆる場面でネットワークを通じて種々の情報を得ることが当たり前になっており、情報を伝送したり記録したりする場合には、正確さや信頼性、安全性などが強く求められている。このためには、情報をいかに符号化するかが重要になってくる。 この授業は、主に情報学群専門基礎科目「情報代数」や「情報理論基礎」で修めた知識をもとに、誤り訂正符号等の符号理論を学ぶために必要となる、代数系に代表される数学的な基盤と誤り訂正符号の基本を修得する。 この授業では、まず符号の誤りとその検出、訂正の条件などの基本的なことがらを理解し、有限体やなど必要となる代数学の基礎を学ぶ。そして、線形符号の概念を修得した上で、実用的な誤り訂正符号について学ぶ。 授業の概要 まず、符号の誤り検出と訂正の能力を調べるためのハミング距離について学修する。 次に、符号理論の数学的基礎となる代数学、特に有限体（拡大体）について学ぶ。 これらの基礎をもとに、誤り訂正符号の原理を理解する。 こららについての理解度を確認するために、３回の演習と中間・期末課題を行う。 到達目標 (1) 誤り検出／誤り訂正の仕組みと数学的基礎を理解できる (2) 線形符号の概念を理論的にとらえられ、ハミング符号を正しく扱うことができる (3) 巡回符号をはじめとする誤り訂正符号の原理を理解でき、符号化と復号の処理を行うことができる 授業の方法 授業の進め方 板書と資料を用いて行なう。きちんとノートをとり、予習・復習を行うことが理解への第一歩となる。授業の進度に応じて演習を実施し、理解度を確認する。 授業計画 第１回 情報源符号化と通信路符号化 まず、この授業全体で学習することを概観した後、情報源符号化と通信路符号化のそれぞれの役割を整理する。 第２回 ハミング距離 誤り検出・訂正の性能や符号語の違いを表すハミング距離について理解する。 第３回 誤り検出・訂正の能力 誤り検出と誤り訂正の原理を理解し、その限界をハミング距離で表現する。 第４回 代数系 集合上の演算が定義される代数系について学び、もっとも基本となる群について理解する。 第５回 巡回群 有限群の性質と剰余類について学び、生成元から巡回群がなされることを理解する。 第６回 有限体 誤り訂正符号を構成するための代数体である有限体の数学的基礎を学ぶ。また、有限体の要素をべきにより生成するための原始元について学ぶ。 第７回 有限体上の多項式 ２進数で表現できる符号を構成する有限体として拡大体を利用するために、その元を表現するための基礎となる有限体の元を用いた多項式の表現について修得する。 第８回 拡大体 拡大体上の原始元に相当する働きをする原始多項式となる既約多項式を用いて拡大体の元の表し方を理解する。 拡大体上での演算や性質をとらえる。 第９回 演習 1 誤り検出・訂正能力と有限体に関する演習を行う。 【中間課題（有限体） 】 有限体について学修した内容を理解できているか確認するための課題をKUTLMS(moodle)により実施する（全問正解するまで繰り返して理解すること）。 第10回 線形符号 検査ビットと情報ビットで誤り訂正符号が構成できることを理解し、そのそれぞれが線形の関係となる線形符号の特徴を理解する。 第11回 検査行列とシンドローム 線形符号の検査行列とシンドロームを用いて誤りの検出と訂正ができることを学ぶ。 第12回 ハミング符号 もっとも基本的な線形符号であるハミング符号の構成について学ぶ。 第13回 演習 2 線形符号とハミング符号に関する演習を行う。 第14回 巡回符号 生成多項式を用いて構成される巡回符号の特徴を理解する。 第15回 巡回組織符号 巡回組織符号の構成法を学び、生成多項式からシンドロームを求めて誤り訂正できることを理解する。 第16回 巡回組織符号による誤り検出 巡回組織符号により最小ハミング距離以上の誤り訂正が可能なことを理解する。また、巡回ハミング符号の拡張で多重誤り訂正可能なBCH符号とバースト誤り訂正可能なRS符号について学ぶ。 第17回 演習 3 巡回符号に関する演習を行う。 【期末課題（誤り訂正符号） 】 確率について学修した内容を理解できているか確認するための課題をKUTLMS(moodle)により実施する（全問正解するまで繰り返して理解すること）。 第18回 習熟度確認（試験） 有限体と誤り検出・訂正、符号に関する総合的な課題（試験）により習熟度を確認し、修得状況を評価する。 第19回 まとめ 総合的な課題（試験）の結果を確認し、解答例を参考にしながらこの授業で学んだことを振り返る。 成績評価の方法・基準 総合的な課題（試験）で達成度の評価を行う。なお、試験を受験するためには中間課題、期末課題を全問正解していることを前提とする。 AA：課題の全ての問題を理解した上で正確に解ける A：課題の全ての問題の基本的な解き方について記述でき、８割に相当する基礎的な問題をすべて解ける B：課題の８割に相当する基礎的な問題すべての基本的な解き方について記述でき、このうち半数以上の問題を解ける C：課題の８割に相当する基礎的な問題の３／４以上について基本的な解き方を記述でき、このうち一部の問題を解ける F：Cに達しないもの 授業時間外学習（予習・復習等） ・授業の準備として、授業計画に示す教科書の範囲を読んでから出席すること。 ・授業後にはノートを整理して授業内容を復習するとともに、該当する範囲の教科書の例、例題、章末問題を解いて理解を深めること。 ・KUTLMSで提示されている課題を解いて理解しておくこと。 キーワード 有限体、誤り検出、誤り訂正、組織符号、線形符号、巡回符号 他の科目との関連 ・「AI・コンピュータ科学専攻」専門発展科目 ・事前の履修が望ましい科目＝「情報代数」、 ・履修前提科目＝「情報理論基礎」、「オートマトンと形式言語」 備考 履修上の注意： ・遅刻しての出席（授業中の教室への出入り）は、特別な事情がある場合以外は原則認められない。 ・私語や授業に関係ない行動など授業を妨害する行為に対しては、退室を命じるなど厳正に対処する。 ・授業時間外や授業終了後の口頭での質問は、公平性の観点から原則受け付けない。 授業に関する質問は、授業時間中での（挙手による）発言か、「授業に関する質問等の問い合わせ先」への連絡に対して、授業の出席者、もしくは履修登録者のほぼ全員に同時に回答できる場合のみ対応する。 ただし、試験の直前の授業終了後から試験までの期間は原則質問を受け付けない。 ・クラブ・サークル等の活動での欠席については、オリンピック、ワールドカップなどの国際的な大会以外では特に配慮しない。ただし試験の欠席については、事前に欠席届とは別に相談があれば考慮する場合がある。 ・この授業のより詳細な情報は http://www.info.kochi-tech.ac.jp/mfukumot/Lecture/CT/index.html に掲載する。 ・連絡先： fukumoto.masahiro@kochi-tech.ac.jp ・オフィスアワー： 毎週月曜日 第５時限 A418教員室／A357研究室 教科書 教科書1 ISBN 9784339024210 書名 C言語による情報理論入門 著者名 久保田, 一, 1952-,大石, 邦夫, 1962-,福本, 昌弘,久保田一, 大石邦夫, 福本昌弘 共著 出版社 コロナ社 出版年 2007.6 参考書 参考書1 ISBN 9784627817418 書名 例題で学ぶ符号理論入門 著者名 先名, 健一,先名健一 著 出版社 森北出版 出版年 2011.7 参考書2 ISBN 9784627853911 書名 情報理論 : 情報量～誤り訂正がよくわかる 著者名 相河, 聡,相河聡 著 出版社 森北出版 出版年 2018.6 参考書3 ISBN 9784797345261 書名 数学ガール : フェルマーの最終定理 著者名 結城, 浩, 1963-,結城浩 著 出版社 ソフトバンククリエイティブ 出版年 2008.8 参考書4 ISBN 9784339024463 書名 代数系と符号理論入門 著者名 坂庭, 好一, 1948-,渋谷, 智治,坂庭好一, 渋谷智治 共著 出版社 コロナ社 出版年 2010.4 参考書5 ISBN 4339010545 書名 誤り訂正符号と暗号の基礎数理 著者名 笠原, 正雄, 1936-,佐竹, 賢治,映像情報メディア学会,笠原正雄, 佐竹賢治 共著 出版社 コロナ社 出版年 2004.3 参考書6 ISBN 9784781912882 書名 応用情報数学 著者名 横森, 貴, 1951-,小林, 聡, 1965-,横森貴, 小林聡 共著 出版社 サイエンス社 出版年 2011.6