情報源符号化(コインの言語: 4/9)

無駄のない圧縮方法を考えることで、符号理論 (可変長の符号化) への入門とする。 この簡略化された問題では、１つの記号（はじくこと）の通信を通して、他の記号を伝える方法を扱う。情報源符号化により、情報源をデータに圧縮して効率的に通信することを試みる。

ある問題に取り掛かろう。

[風が吹く音]

アリスとボブは樹上に家を構えて住んでいる。

2人の家は遠く離れているため、

互いを目視することはできないが、

意思疎通を行いたい。

そこで2つの家の間に、

針金を張ることにした。

針金を強く張り、

末端にブリキの缶を取り付けた。

そして互いの声を弱い信号として、

針金越しに送れるようにした。

[ボブのくぐもった声] もしもし？

[アリスのくぐもった声] もしもし、聞こえないよ。

[ボブのくぐもった声] こっちも辛うじて聞き取れるくらいだ。

[アリスのくぐもった声] 1. 2. 3. 4. 5.

しかし、問題があった:

「ノイズ」だ。

風が強い日は決まって、

ノイズにかき消され、

信号を聞き取れない。

そこで信号のエネルギーをー

増加させ、ノイズ下でも信号をー

識別できるようにする必要があった。

ここでボブに案が閃いた。

針金をはじく音なら、

ノイズの中でも認識しやすい。

そうすると新たな問題が生じた。

どうすればメッセージを「はじき方」に変換できるだろう？

さて彼らは、

遠距離間でボードゲームをしたいため、

最もありがちなメッセージの１つであるー

サイコロ２つを振った数値の送信に取り組んだ。

ここで送信するメッセージは、

有限個の記号、

この場合11通りの数値から、

1つを選択したものとみなせる。

これを「離散情報源」という。

最初、彼らは最もシンプルな方法を採用した。

はじく回数で結果を送信するのだ。

つまり「3」を送信するためには3回はじく。

「9」なら9回はじき、

「12」なら12回はじく。

しかし、これでは必要以上に時間がかかるとー

すぐに気付いた。

経験から、はじくスピードは最大でー

毎秒2回だと分かった。

これ以上だと信号が混ざってしまう。

つまり、毎秒２回弾きが、

この通信手段の「通信路容量」とみなせる。

[弾く音]

それから、最もー

出やすい目は7だと分かった。

さて、7を送信するには3.5秒かかる。

[7回弾く音]

ここでアリスは、符号化の方法を変えることで、

ずっと良くできることに気付いた。

彼女は、それぞれの目が出る確率に、

簡単な規則がある事に目をつけた。

2が出るのは1通り。

3が出るのは2通り。

4が出るのは3通り。

5が出るのは4通り。

6が出るのは5通り。

7が出るのは6通りで、

これが最も出やすい。

8が出るのは5通り。

9には4通り。

以下続いて、12では1通りに戻る。

このグラフは、

結果ごとの場合の数を表していて、

明確なパターンが見て取れる。

それでは、グラフを

「数値 対 はじく回数」 に変えてみよう。

彼女は、最も出やすい数であるー

7を、

最も短い信号である1回はじきに割り当てた。

[1回弾く音]

それからその次に出やすい数を割り当てた。

同確率の時は、ランダムに選んだ。

今回は6を2回に、

8を3回に、

戻って5を4回に、

それから9を5回、

次に5を…と割り当て、最後の12には

11回はじきを割り当てた。

すると、最も出やすい7をー

1秒とかからずに送ることができる。

大きな改善だ。

この簡単な改善で、

同じ時間でも平均的にはより多くの情報を送れるようになった。

実際、この簡単な例では、

この符号化手法が最も良い。

しかし、はじくだけでー

サイコロ2つの結果を送る、

もっと速い方法を思いついたなら話は別だ。

さて、針金で何度か遊んだ後、

ボブに新たなアイデアが閃いた。