符号・情報理論特論（Fundamentals of Coding and Information Theory）[3603]

＜授業のねらい及び具体的な到達目標＞

この講義では、シャノンの通信路符号化定理に基づいた符号理論について、近年の研究成果を含んだ話題について講義します。この講義を通じて、さらに通信路符号化の具体的な符号化・復号化方式などについて、進んだ知識を得ることができます。（ただし、取上げるテーマは、変更する場合があります。）

※システムデザイン専攻の履修者については以下が適用される。

（JABEE学習・教育到達目標）
「システムデザインプログラム」
（A）工学関連分野の原理・原則に関する深い知識と応用力を身につけた人材を育成します：◎

JABEE基準1の（2）の内容
（c），（d）：◎
（b），（e），（g）：○

[Introduction]

This lecture is a graduate-level of information theory and coding theory. Beginning of information theory is Claude Shannon's 1948 paper in the Bell systems technical journal: A Mathematical Theory of Communication. Shannon has showed how information could be quantified with absolute precision, and demonstrated the essential unity of all information media, which could be encoded in bits. In this lecture, students are able to acquire and recognize the recent topic "network coding" which is one of the important resent research results of information theory. This lecture provides the opportunity to study the development technological interactions between networking technologies and information theory. The idea of network coding gives us insight into how a new field of the information and communications technology evolves.

On the completion of this lecture, the students should be able to:
1. have an awareness of the linear network coding method.
2. have an awareness of the random network coding method.
3. have an awareness of the physical layer network coding method.

＜授業計画及び準備学習＞

1．ネットワーク符号化の位置付け
2．ネットワーク符号化の導入事例
3．最小カット・最大フロー定理について
4．ネットワーク符号化のための「主要定理」について
5．「主要定理」の等価的な代数学的記述について
6．「主要定理」の証明について
7．ネットワークマルチキャストモデル
8．線グラフモデル
9．ネットワーク符号化の理論的枠組みについて
10．ネットワーク符号化と代数学的枠組み
11．ネットワーク符号化と組合せ論的枠組み
12．ネットワーク符号化と情報理論的及び線形計画論的枠組み
13．ネットワーク符号化とルーティングの種別
14．学習成果の確認（レポート課題の作成）
ただし、開講年次により講義で扱うテーマの変更もしくは修正する場合がありますが、その場合には第１回目の講義で通知します。また、第１３回目までの講義に必要となる準備学習については、事前に決められたプリントの該当箇所を読んだ上で、参考書を利用して不明箇所を調べるなどの準備をして下さい。講義終了後には、講義で得られた知識などを基に、不明箇所を中心に各自で復習して下さい。第１４回については、準備学習として、これまでの総復習をしてください。

[Subjects in this lecture]
1. Introduction

Networking technologies and related fields

2. Introductory examples of network coding

The Butterfly network

Benefits, throughput, wireless resources and security

3. The min-cut max-flow theorem

Various approaches shown by Menger, Ford and Fulkerson, Elias.

4. The main network coding theorem (1)

Statement of the theorem

5. An equivalent algebraic statement of the theorem

The global coding vectors and local coding vectors

5. The main network coding theorem (2)

Proof of the theorem

Sparse zeros lemma

6. A network multicast model

The basic model and definitions

7. The line graph model

8. Theoretical frameworks for network coding

9. Algebraic framework for network coding

10. Combinatorial framework for network coding

Basic notions of subtree decomposition

Formal description of subtree decomposition

Properties of subtree graphs

11. Information-theoretic framework for network coding

Network operation with coding

The information rate achievable with coding

12. Linear-programming framework for network coding

Unicast and multicast flows

Multicast with network coding with and without cost

13. Types of rooting and coding

Routing

Network coding

Coding at the source

14. Reviewing of the lecture

＜成績評価方法及び水準＞

講義中の課題、期末のレポートによる課題を課し、これらを対象として評価をします。

[Evaluation]

Students must submit a report at the end of term about a theme related to network coding in the information theory research fields. In the submitted report, the topic is selected from the peer-reviewed English literature in academic journals or reviewed conference proceedings.
The selected literature must be registered with the database of Elsevier's

＜教科書＞

指定教科書はありません。講義開始前にプリントを配布するか、別途指定します。

[Text book]

C. Fragouli and E. Soljanin, ``Network Coding Fundamentals,'' Fundations and Trends in Networking, vol.2, no.1, pp.1-133, now Publishers Inc., 2007.

＜参考書＞

ネットワーク符号化の基礎、銭飛、森北出版
他に、自己に合った符号理論や情報理論の専門書を使って下さい。

＜オフィスアワー＞

水曜日 15:00〜16:00 新宿校舎22階A-2274教室、もしくは、講義開始後に通知するメールアドレスによる連絡でも構いません。

＜学生へのメッセージ＞

符号・情報理論について、さらにもう一歩理解を深めたい人に向いています。