Advanced Information Theory - 情報理論特論　

電気通信大学 — University of Electro-Communications, Tokyo

2011 Fall Semester 後学期

• Class meeting: Thursdays, 10:40 to 12:10. 木曜日２時限
• Classroom: West Building 1, Room 217 (西1号館 217室)
• Course web site: http://www.lit.ice.uec.ac.jp/kurkoski/ait
• Instructor: Brian KURKOSKI ブライアン　クルカスキー 　(West Building 1, Room 301) kurkoski@ice.uec.ac.jp 0424-43-5295
• Instructor: Hideki Yagi 八木秀樹
• Official Syllabus. 教務かのシラバス. 時間割コード：23232205

Lectures — 講演内容

Lecture 1 - October 6

• Lecture: Overview, introduction to coding theory, message passing using soldiers, Pearl's belief propagation. Lecture slides.
• No homework

Lecture 2 - October 13

• Lecture: Introduction to coding theory (linear codes, generator and parity check matrices).
• Homework: Justensen Text: Problems 1.5.1 (all), 1.5.2 (1 and 3 only)

Lecture 3 - October 20

• Lecture: minimum distance, minimum distance decoding, cosets and syndrome decoding.
• Matlab Tutorials:
  • Mathworks: Getting Started 日本語
  • MATLAB Introduction by Ross Spencer
  • A Practical Introduction to Matlab by Mark S. Gockenbach
  • Introduction to Matlab by Graeme Chandler
  • Examples: Linear Block Codes by Henry Pfister
• Homework: Justensen Text: 1.5.10, 1.5.11, 1.5.13, 1.5.21. To prepare for next week, read Ch. 47 of David J.C.MacKay, Information Theory, Inference, and Learning Algorithms.

Lecture 4 - October 27

• Lecture: Introduction to low-density parity-check (LDPC) codes. LDPC decoding algorithm (part one). Lecture slides.
• No homework

Lecture 5 - November 10

• Lecture: Message-passing decoding framework, belief-propagation (sum-product) decoding, LPDC decoding algorithm
• Homework:
  • Homework 3. Due November 24.
  • Homework 4. Due November 24.
• Note: no class next week (Chofu-sai)

Lecture 6 - November 24

• Lecture: LDPC code ensembles, irregular LDPC codes
• No homework (finish your LDPC code simulations)

Lecture 7 - December 15

• Lecture: Erasure channel capacity, LDPC decoding on erasure channel. Density evolution analysis: LDPC code ensembles, noise thresholds, all-zeros codeword, erasure channel DE and EXIT chart.
• Homework 5: Homework 5.

Lecture 8 - December 22

• Lecture: Entropy. Mutual Information. Capacity. Channel Coding Theorem.
• Homework 6 (page 32 of the slides) (1) Calculation of entropy (2) Properties of binary entropy
• Updated slides

Textbook 教科書

Recommended (but not required) textbooks:

• Thomas M. Cover and Joy A. Thomas, Elements of Information Theory 2nd Edition, Wiley-Interscience, Aug. 1991. book
• David J. C. MacKay, Information Theory, Inference & Learning Algorithms, Cambridge University Press, June 2002. Free PDF

Pre-requirement

• A previous course on information theory or coding theory is required.
• Previous courses in discrete mathematics or linear algebra are desirable.
• 前もって履修しておくべき科目 情報理論、符号理論
• 前もって履修しておくことが望ましい科目 離散数学、線型代数学

Objectives - 主題

Information theory is a field concerned with mathematical aspects of information and communication. Modern communication systems are based on these ideas, which are normally divided into the areas of "channel coding" and "source coding".

The focus of this class is channel coding. In particular, the goal of this class is understanding of Shannon's well-known channel coding theorem, as well as the understanding of how it applies to practical communication systems. Mutual information and channel capacity, used to evaluate channel reliability are explained. The channel coding theorem will be explained. Recent developments in error-correcting codes and decoding algorithms will be reviewed and explained. Codes based upon lattices, and their decoding algorithms will be discussed.

情報理論は情報・通信の様々な性質を数学的に論じる学問分野である．特に，C.E. Shannonによって示された2つの符号化定理（情報源符号化定理と通信路符号化定理）は現在のデジタル通信システムの礎となっている．本授業では，情報理論の2大テーマのうち「通信路符号化」に焦点を当てて講義する．ここでは，Shannonが示した符号化定理を理解し，符号化定理を実現するための様々な技術を理解することを目標とする．

デジタル通信の信頼性の評価に必要な相互情報量や通信路容量について解説した後，通信路符号化定理について述べる．その後，具体的な誤り訂正符号や復号アルゴリズムを最新の技術も取り入れながら概説する．さらに，通信路符号化の発展として，通信路等化アルゴリズムやLattice符号を用いた通信システムなどに言及する．

Outline - 授業内容

Brian Kurkoski gives Lectures 1-9. Hideki Yagi gives Lectures 10-15.

Schedule — スケージェル

BK=Brian Kurkoski; HY = Hideki Yagi

Assessment Policy - 成績評価方法

• Homework 課題: 40%
• Midterm project 中間レポート: 30%
• Final project 期末レポート: 30%

Previous Year - 前年度

• AIT 2010