科 目 名   	符号理論  
担当教員   	福本　昌弘  
対象学年   	3年次
教　　室   	A106
曜日・時限   	火・金 第3時限（専門科目演習　火 第1時限）
単 位 数   	2


授業の目的
　現在ではあらゆる場面でネットワークを通じて種々の情報を得ることが当たり前になっており、情報を伝送したり記録したりする場合には、正確さや信頼性、安全性などが強く求められている。このためには、情報をいかに符号化するかが重要になってくる。
　この授業は、主に情報学群専門基礎科目「情報代数」や「情報理論基礎」で修めた知識をもとに、誤り訂正符号等の符号理論を学ぶために必要となる、代数系に代表される数学的な基盤と誤り訂正符号の基本を修得する。
　この授業では、まず符号の誤りとその検出、訂正の条件などの基本的なことがらを理解し、有限体やなど必要となる代数学の基礎を学ぶ。そして、線形符号の概念を修得した上で、実用的な誤り訂正符号について学ぶ。

キーワード
　有限体、誤り検出、誤り訂正、線形符号、巡回符号

授業の進め方
　板書と資料を用いて行う。きちんとノートをとり、予習・復習を行うことが理解への第一歩となる。授業の進度に応じて演習を実施し、理解度を確認する。

達成目標
(1) 誤り検出／誤り訂正の仕組みと数学的基礎を理解できる。
(2) 線形符号の概念をとらえられる。
(3) 巡回符号をはじめ、誤り訂正符号を利用できる。

授業計画 

 1. 情報源符号化と通信路符号化
  まず、この授業全体で学習することを概観した後、情報源符号化と通信路符号化のそれぞれの役割を整理する。

 2. ハミング距離
  誤り検出・訂正の性能や符号語の違いを表すハミング距離について理解する。

 3. 誤り検出・訂正の能力
  誤り検出と誤り訂正の原理を理解し、その限界をハミング距離で表現する。

 4. 代数系
  集合上の演算が定義される代数系について学び、もっとも基本となる群について理解する。

 5. 巡回群
  有限群の性質と剰余類について学び、生成元から巡回群がなされることを理解する。

 6. 有限体
  誤り訂正符号を構成するための代数体である有限体の数学的基礎を学ぶ。また、有限体の要素をべきにより生成するための原始元について学ぶ。

 7. 有限体上の多項式
  ２進数で表現できる符号を構成する有限体として拡大体を利用するために、その元を表現するための基礎となる有限体の元を用いた多項式の表現について修得する。

 8. 拡大体
  拡大体上の原始元に相当する働きをする原始多項式となる既約多項式を用いて拡大体の元の表し方を理解する。
  拡大体上での演算や性質をとらえる。

 9. ［演習 1.］
  誤り検出・訂正能力と有限体に関する演習を行う。

10. 線形符号
  検査ビットと情報ビットで誤り訂正符号が構成できることを理解し、そのそれぞれが線形の関係となる線形符号の特徴を理解する。

11. 検査行列とシンドローム
  線形符号の検査行列とシンドロームを用いて誤りの検出と訂正ができることを学ぶ。

12. ハミング符号
  もっとも基本的な線形符号であるハミング符号の構成について学ぶ。

13. ［演習 2.］
  線形符号とハミング符号に関する演習を行う。

14. 巡回符号
  生成多項式を用いて構成される巡回符号の特徴を理解する。

15. 巡回組織符号
  巡回組織符号の構成法を学び、生成多項式からシンドロームを求めて誤り訂正できることを理解する。また、巡回ハミング符号の拡張で多重誤り訂正可能なBCH符号とバースト誤り訂正可能なRS符号について学ぶ。

16. ［演習 3.］
  巡回符号に関する演習を行う。

17. 習熟度確認
  有限体と誤り検出・訂正、符号に関する総合的な課題により習熟度を確認し、修得状況を評価する。

18. まとめ
  総合的な課題の結果を確認し、解答例を参考にしながらこの授業で学んだことを振り返る。


成績評価：
　総合的な課題で達成度の評価を行う。
　●AA：課題の全ての問題を理解した上で正確に解ける
　● A：課題の全ての問題の基本的な解き方について記述でき、８割以上の問題を解ける
　● B：課題の８割以上の問題の基本的な解き方について記述でき、４割以上の問題を解ける
　● C：課題の６割以上の問題の基本的な解き方を記述できる

教科書：
  「C言語による情報理論入門」, 久保田一, 大石邦夫, 福本昌弘 著（コロナ社, 2007.5）
    ISBN978-4-339-02421-0

参考書
  「数学ガール フェルマーの最終定理」, 結城浩 著（ソフトバンククリエイティブ, 2008.8）
    ISBN978-4-7973-4526-1
  「代数系と符号理論入門」, 坂庭好一, 渋谷智治 著（コロナ社, 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

授業外学修（予習・復習）：
・授業の準備として、授業計画に示す教科書の範囲を読んでから出席すること。
・授業後にはノートを整理して授業内容を復習するとともに、該当する範囲の教科書の例、例題、章末問題を解いて理解を深めること。
・LMSで提示されている課題を解いて理解しておくこと。

履修上の注意：
・「コンピュータサイエンス専攻」専門発展科目

・事前の履修が望ましい科目＝「情報代数」、「情報理論基礎」
・クラブ・サークル等の活動での欠席については、オリンピック、ワールドカップなどの国際的な大会以外では特に配慮しない。ただし試験の欠席については、事前に欠席届とは別に相談があれば考慮する場合がある。

・この授業のより詳細な情報は
  http://www.info.kochi-tech.ac.jp/mfukumot/Lecture/CT/index.html
  に掲載する。

・オフィスアワー： 毎週火曜日 第５時限（16:20〜） A418教員室／A357研究室