山本宙著,「情報量 ー情報理論への招待ー」,コロナ社, ISBN978-4-339-02890-4 (2019年3月)
ナビゲーションやコニュニケーションツールなど, 常時インターネットに接続されている機器を前提とした サービスが日々新しく開発され,どんどん便利に,快適に なっています.これを支えているのが情報通信技術です. なかでもデジタル通信の高速化,高信頼化がブレイクスルーの 鍵となったのですが,これは1940年代にはじまる情報理論 という学問が基礎になっています. 情報理論には情報を失わずにどこまでデータのサイズを小さく できるかを明らかにした「情報源符号化定理」と, 通信時にどの程度の冗長性をもたせておけばエラーを回復 できるのかを明らかにした「通信路符号化定理」という2つの重要な 定理があります. 本書はこのうち「情報源符号化定理」を平易に解説することに特化した 教科書です.結果として「情報量」の概念を理解するための教科書と なっています.
「平易な」教科書といっても,
というアプローチが考えられます.本書では後者の立場をとりました. 情報理論の教科書としては本書は学べる項目数こそ少ないのですが, 証明技法を学ぶことを重視しているため,本書を理解した後, より一般的な情報理論の専門書を学習するときの 助けになることを期待しています.
補題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$ となる。