書記が数学やるだけ#722 情報源符号化の性質

望ましい符号化を考える基礎を考えていく。

問題

例として4文字のアルファベットを01で符号化してみる。

説明

情報源符号化はデータ圧縮ともいい，データを効率よく運ぶことに不可欠の技術である。

クラフトの不等式は，符号理論における不等式の1つで可変長符号が一意復号可能である為の必要条件を与える。

シャノンの情報源符号化定理は，1948年のクロード・シャノンの論文『通信の数学的理論』で発表されたもので，シャノンの第二基本定理（通信路符号化定理）に対してシャノンの第一基本定理とも言う。この定理から，情報源がどのくらい圧縮できるかを見積もることができる。

解答

まず一意に復元可能かについて，(6)は同じ符号を割り当てているので明らかに一意に復元不可能である（特異符号）。一方(5)は非特異であるが，0110を復号するときにACAとDBの2通りが考えられるため，一意に復元不可能である。

次に平均符号長を考える。(1)は4文字を割り当てるのに素直ではあるが，これよりも平均符号長を短くすることができる。実際には，出現確率が大きい記号には短い符号，出現確率が小さい記号には長い符号を割り当てることで実現できる。

最後に瞬時符号（その符号が送られた 瞬間に復号できる符号）であるか，これを考えるには符号木を作るとよい。(4)では0111111までだと3通りの復号が考えられ，0を加えることでようやく一意に復号できる。(3)のように符号が全て葉で終わっていれば，瞬時符号であることが言える。

以上より最も望ましい符号化は(3)であると結論づけられる。

クラフトの不等式からは瞬時符号の存在を示すことができる。例えば(3)では左辺が1以下であり，確かに瞬時符号の存在を示している。ここで(3)より符号長を短くできるかを考えると，クラフトの不等式に反することから瞬時符号は存在しないことが言える。

ではシャノンの情報源符号化定理の証明を行う。まず無記憶情報源Sについて示していく，証明の鍵となるのはクラフトの不等式である。

これをN次拡大情報源に拡大することで，より一般の場合について示せる。

本記事のもくじはこちら：