問題設定

情報を"0"と"1"の二つの記号を用いて伝達するときの最適なエンコード方法について考察する。
そしてその方法とは、シグナルの発生確率に反比例した語長（具体的には $\log \dfrac{1}{p(x)}$ ）のコードワードを割り当てることであることをこれから説明する。
最後に情報量との関係について述べる。

あるシグナルの伝達の効率の評価

シグナル $x$ に対して、その出現確率を $p(x)$ 、その語の長さを $L(x)$ と定義すると、平均のメッセージ長として $p(x)L(x)$ を考えることができる。この和 $\sum p(x)L(x)$ が短ければ短いほど効率よく伝達できていることになる。

コードワードの採用とそのコスト

デコードのプロセスを考えるとコードワードに $"010"$ を選んだ場合、 $"0100"$ や $"01011"$ など、接頭"01"を持つコードワードを新規に採用出来なくなる。このようにあるコードワードに対してそのコードワードを採用することで、コードワード全体のうち、どれだけのコードワードが使用不可になるか？を定量的に評価するためにコストの概念を導入する。

シグナル $x$ に対してある語 $word(x)$ （語長は $l(x)$ ）を採用すると、それによって使用不可になるコードワードの割合は $cost=\dfrac{1}{2^{l(x)}}$ と定量的に評価できる。

例

最大の語長を3とする。コードワードの総数は語長0の空文字も含めて $1+2+4+8=15$ である。 $"01"$ をコードワードに採用した場合、コードワード全体のうち $"01"$ を接頭に持つのは $"01","010","011"$ の3つであるから、コストは $\dfrac{2^{2}-1}{2^{3}-1}$ $\simeq$ $\dfrac{1}{4}$ （ $=$ $\dfrac{1}{2^{l(x)}}$ ）と定義される。 f:id:python_beginner:20201121233001p:plain

出現確率 $p(x)$ のシグナルに対してコスト $p(x)$ を割り当てるのが最適であることの証明

出現確率 $p(x)$ のシグナルに対してはコードワード全体のうち $p(x)$ を使用不可にするようなコードワードを採用することが最適であることを示す。これから、議論をわかりやすくするために、語長の最大は5であるとする。 f:id:python_beginner:20201122000042p:plain

出現確率 $p(x)$ のシグナルに対して語長 $\log \dfrac{1}{p(x)}$ のコードワードを割り当てるのが最適であることの証明

これまでの議論によって、
①語長 $l(x)$ のコードワードの割り当てによってコードワード全体のうち $\dfrac{1}{2^{l(x)}}$ が使用不可になる。
②出現確率 $p(x)$ のシグナルに対してコスト $p(x)$ を割り当てるのが最適である。

が示された。よってシグナル $x$ に対して、 $p(x)=\dfrac{1}{2^{l(x)}}$ 分のコストを割り当てることが最適であるから、この式を変形して $l(x)=\log \dfrac{1}{p(x)}$ が得られる。