情報理論 第6回 情報源符号化とその限界

2020.7.03 (金), 3限

今日の内容

次の内容を学ぶ。今日は、第4章「情報源符号化の限界」に入ります。今日の内容の「情報源符号化」とはデータ圧縮のことです.良いデータ圧縮とは何か,また,その限界について学びます.

今日の手順

  1. 下記の「授業スライド」をダウンロードして読み,理解する (50~60分)
  2. 演習レポートに取り組む (30~40分)

今日の資料

「今日の資料」の補足

演習レポート

その他

勉強のヒント:今日はどこまでわかれば良いか

今日の授業は,データ圧縮の話です.今日の授業スライドを読んで,次が理解できれば良いです.それで,後半の演習問題も解けます.(下記で,「計算」は計算方法を,「理解」はその意味がわかれば良いです.もちろん,興味ある人,やってみたい人は証明も難しくありません.基本の考え方は十分理解できると思います.)
  1. 計算:符号(code)の表で,符号が瞬時符号かどうか判定できる.(pp.10の「語頭条件」を使う.これは大事で簡単なので,ぜひ覚えましょう)
  2. 計算:平均符号長の定義がわかって,符号の表からそれが計算できる.(これも定義と計算は簡単です.ぜひ覚えましょう.)
  3. 理解:ある符号長をもつ瞬時符号がつくれるかの必要十分条件である「クラフトの不等式」の意味がわかって,書けること
    (ヒント:数学的な証明はできなくてもかまいません.15ページの「直感的理解」が説明です.分かる人は,証明に挑戦しても良いです.)
  4. 理解:「情報源符号化定理」の意味がわかること(定理4.2と定理4.3)

さいごに: 情報理論は,日本中・世界中の情報通信系の大学院入試で,必ず(まず)選択問題に入っている一般的な科目です.最近人気がある職業の一つである「データサイエンス」の仕事でも,情報理論は必須の勉強の一つになっています.今日の演習の課題が解ければ,今日の授業の理解は大丈夫です.あとは,次回学ぶ「ハフマン符号」圧縮アルゴリズムがわかれば,私の担当の「情報源符号化」は合格です.)

2020.6.29 作成,2020.7.03,21:42 改訂,担当:有村


info-theoryAist.hokudai.ac.jp