Entropy - Introduction to Information Theory
情報量 - 情報理論への招待

書籍情報

山本宙著，「情報量　ー情報理論への招待ー」，コロナ社， ISBN978-4-339-02890-4 （2019年3月）

内容紹介

ナビゲーションやコニュニケーションツールなど， 常時インターネットに接続されている機器を前提とした サービスが日々新しく開発され，どんどん便利に，快適に なっています．これを支えているのが情報通信技術です． なかでもデジタル通信の高速化，高信頼化がブレイクスルーの 鍵となったのですが，これは1940年代にはじまる情報理論 という学問が基礎になっています． 情報理論には情報を失わずにどこまでデータのサイズを小さく できるかを明らかにした「情報源符号化定理」と， 通信時にどの程度の冗長性をもたせておけばエラーを回復 できるのかを明らかにした「通信路符号化定理」という2つの重要な 定理があります． 本書はこのうち「情報源符号化定理」を平易に解説することに特化した 教科書です．結果として「情報量」の概念を理解するための教科書と なっています．

「平易な」教科書といっても，

• 使い道の多い知識を網羅し，何が成り立つのかの説明に注力する． なぜ成り立つのか，の説明を省略する．
• なぜ成り立つのか，の説明に注力する．かわりに 説明する項目は厳選する．

というアプローチが考えられます．本書では後者の立場をとりました． 情報理論の教科書としては本書は学べる項目数こそ少ないのですが， 　証明技法を学ぶことを重視しているため，本書を理解した後， より一般的な情報理論の専門書を学習するときの 助けになることを期待しています．

正誤表

• p.8 脚注
  「符号語長の期待値は4章であらためて平均符号語長として定義する。」を追加
• p.11 章末問題1.2問題文を以下に変更
  天気が晴，曇，雨，雪，霧の 5 種類であるとし， これを 0,1 の系列に符号化する固定長符号を考える。 使い物になる符号を構成するための符号語長の最小値を答えよ。 理由も示せ。
• p.27 図3.2 $s_4$の符号語
  誤：01 → 正：11
• p.34 脚注番号1の脚注を削除
• p.37，9,10行目
  クラフトの不等式を示す。 \[ \sum_{i=1}^q \left(\frac{1}{2}\right)^{l_i}\leq 1 \] →
  クラフトの不等式 \[ \sum_{i=1}^q \left(\frac{1}{2}\right)^{l_i}\leq 1 \] を示す。
• p.40，3 行目
  誤：$-(n-1)$ は負なので → 正：$-(n-1)$ は 0 以下なので
• p.41，Coffee Break，図
  誤：(b) 値域 → 正：(b) 終集合
• p.41，Coffee Break，4 行目
  誤：値域の要素数よりも → 正：終集合の要素数よりも
• p.42，18, 20, 22, 24 行目
  誤：符号語長並びが$(l_1, 1_2, \ldots, l_q)$の → 正：符号語長並びが$(l_1, l_2, \ldots, l_q)$の
• p.45，10行目
  誤：上限になるように符号長を → 正：上限になるように符号語長を
• p.46，11行目
  誤：まず情報源を生起確率の → 正：まず情報源シンボルを生起確率の
• p.51，12行目
  誤：枝で結ばれた節点は → 正：枝で結ばれた節点について，
• p.53，10行目
  誤：接頭語 → 正：語頭
• p.53，12行目
  誤：接頭語 → 正：語頭
• p.54，補題4.1と証明を下記に差し替え
  

  補題4.1　情報源シンボル $S = \{s_1,s_2,\ldots,s_q\}$ が生起確率の降順に並んでいる，すなわち $P_1 \geq P_2 \geq \cdots \geq P_q$ であるとき，符号語長が $l_1 \leq l_2 \leq \cdots \leq l_q$ である瞬時に復号可能なコンパクト符号が存在する。

  証明　情報源シンボルの生起確率が $P_1 \geq P_2 \geq \cdots \geq P_q$ であるとき，コンパクト符号の符号語長並びが $(l_1,l_2,\ldots,l_q)$ であったとする．$m > n$ である添え字 $m,n$ について $l_m>l_n$ であった場合，$s_m$ と $s_n$ の符号語を入れ替える。入れ替え前と入れ替え後の平均符号語長の差は， 入れ替えなかった符号の生起確率と符号語長が同じことから入れ替えた 2つの情報源シンボルに関する生起確率と符号語長の積の差に等しい。 これは \[ P_ml_m + P_nl_n - (P_ml_n + P_nl_m)\\ = (P_m - P_n)(l_m - l_n)\\ \geq 0 \] となる。入れ替えによって平均符号語長が大きくならないので入れ替えた後もコンパクト符号であり，語頭条件が維持されるので瞬時に復号可能な符号である。 この操作を整列アルゴリズムと同様に繰り返すことで 符号語長が $l_1 \leq l_2 \leq \cdots \leq l_q$ である瞬時に復号可能なコンパクト符号が得られる。 例えば整列アルゴリズムの一つであるバブルソートを用いる場合は $l_1$ と $l_2$ の隣り合うペアについて $l_1 > l_2$ であれば $s_1$ と $s_2$ の符号語を入れ替え，次に $l_2$ と $l_3$ のペアについて同じことを行う。 これを $l_{q-1}$ と $l_q$ のペアまで行うと $l_q$ は最大の符号語長となる。 この操作を $q-1$ 回繰り返すことで必ず $l_1 \leq l_2 \leq \cdots \leq l_q$ となる。

• p.56，5行目
  誤：瞬時に復号可能なコンパクト符号の符号木を考えると，補題 4.1により
  → 正：補題 4.1 により存在が保証さている符号語長が $l_1 \leq l_2 \leq \cdots \leq l_q$ である瞬時に復号可能なコンパクト符号を考える。
• p.56，11行目
  補題4.1により → （削除）
• p.57，図 4.13
  右下の $p_{q-j-1}$ と$p_{q-j}$ を一段上に移動。
• p.59，図 4.14
  右下の $p_{q-j-1}$ と$p_{q-j}$ を一段上に移動。
• p.60，20行目
  等長符号で符号化する → 瞬時に復号可能な等長符号で符号化する
• p.60，24行目
  符号語長の最大値が $q-2$ → 符号語長の最大値が $q-1$
• p.73，13行目
  $P(\sigma_4)=0.081, P(\sigma_5) = 0.009$ → $P(\sigma_4)=0.009, P(\sigma_5) = 0.081$
• p.74，表5.3
  $\sigma_3$ → $\sigma_4$
  $\sigma_4$ → $\sigma_3$
  $\sigma_5$ → $\sigma_7$
  $\sigma_6$ → $\sigma_5$
  $\sigma_7$ → $\sigma_6$
  
• p.77，図 5.3
  エントロピーによる下限 → エントロピーによる下界
• p.78，8行目
  次善の策として $l_i$ に「つ → 次善の策として $l_i$ に「$\log1/P(s_i)$ のつ
• p.87，11行目
  誤：$f$の値域という。 → 正：$f$の終集合という。
• p.87，13行目
  誤：値域$B$ → 正：終集合$B$
• p.87，17行目
  誤：値域である整数集合 → 正：終集合である整数集合
• p.87，22行目からp.88，1行目
  誤：入力の集合 → 正：定義域
• p.88，1行目
  誤：出力の集合 → 正：終集合
• p.88，図A.1 (a) 右下$b_4$の説明
  誤：使われない要素が値域に → 正：使われない要素が終集合に
• p.89，図A.2 (a) 下$b_4$の説明
  誤：使われない要素が値域に → 正：使われない要素が終集合に
• p.105 [1.2]解答
  符号語長が 2 である固定長符号を用いた場合，符号語の数が 4種類であるため，5種類のどれか異なる天気に同じ符号語を 割り当てることになるため，使い物にならない符号となる。 一方，000, 001, 010, 011, 100 という符号語長 3 の固定長符号を 使用すれば 5種類の天気を区別できる。よって最小値は 3 である。
• p.105 [2.2]解答
  誤：(1)瞬時に復号可能な符号は$C_1, C_4$
  (2)一意に復号可能な符号は$C_1, C_2, C_4$
  →
  正：(1)瞬時に復号可能な符号は $C_4$
  (2)一意に復号可能な符号は $C_2, C_4$
  
• p.105 [2.3]解答
  誤：一意に復号可能であれば狭義に特異でない。 また固定長符号であるから符号シンボル系列の区切りが一意に決まる。 命題2.1より一意に復号可能である。
  →
  正：固定長符号であるから全ての符号語は同じ長さである。 同じ長さの文字列が他の文字列の語頭になるには 同一の文字列でなければならないが，一意に復号可能であるから 命題2.1より狭義に特異でないのでそのような符号語は存在しない。 よって語頭条件を満たすので瞬時に復号可能である。
  
• p.109 [5.2(3)]解答
  誤：$L_{C_2} = a^2 + 3(-2a^2_2a) + 5(a^2-2a+1)$
  →
  正：$L_{C_2} = a^2 + 3(-2a^2+2a) + 5(a^2-2a+1)$
  
• p.111（索引）
  一意に複合可能な符号 46 → （削除）
  仮定 92 → （削除）
  結論 92 → （削除）
  根本が十分条件 92 → （削除）
  【さ】先が必要条件 92 → （削除）
  十分 92 → （削除）
  定義 92,93 → （削除）
  必要 92 → （削除）