情報源符号化定理とは、情報を最も効率よく符号化した時に、どのぐらい短く変換できるかを示す定理です。前回、情報量や平均情報量の意味と求め方を学びましたが、それがこの定理に応用されます。人は効率の良い方法を探し続けるものですが、情報源符号化定理によって符号化の効率の限界が示されるため、必要以上の努力をしなくて済みます。その点で非常に重要な定理であると言えます。やや難解ですが、符号化の復習から始め、具体例を交えながら解説します。
このページでは、
- 符号化とは
- 符号化の効率を測る方法（平均符号長について）
- 情報源符号化定理の内容
を解説しています。
効率の良い符号化とは
3つの記号、「A」・「B」・「C」からなる文字列を伝送することを考えましょう。ここで、「A」・「B」・「C」という記号は仮のものであり、深い意味はありません。例えば、それぞれ「晴れ」・「曇り」・「雨」を表すものなどと考えておけばよいでしょう。
さて、文字列を送る際には「A」・「B」・「C」の記号を一定のルールに基づいて「0」と「1」の羅列に変換しなければいけません（符号化）。符号化のルールとして、例えば以下のようなものを考えたとします。
ルール1
| 記号 | 符号 |
| A | 01 |
| B | 10 |
| C | 11 |
これ以外にも、次のようなルールも考えられます。
ルール2
| 記号 | 符号 |
| A | 10 |
| B | 0 |
| C | 11 |
ルール3
| 記号 | 符号 |
| A | 0 |
| B | 10 |
| C | 11 |
文字列を伝送するときは、やはり効率よく、つまり伝送するデータをできるだけ少なく（＝送る「0」「1」の桁数をできるだけ少なく）したいものです。では、どのルールが効率が良いでしょうか。それを測るのが平均符号長です。
符号化についてもう少し詳しく知りたい方はこちらから↓
平均符号長
1記号当たりの符号の長さ（＝「0」「1」の桁数）の平均を平均符号長と定義します。この平均符号長が短いほど効率の良い符号化と言えます。文字列は長さが一定とは限らないので、1記号当たりで比較を行います。記号X（X＝A, B, C）が文字列の中で出現する確率（＝全体に占める割合）をP(X)、Ｘを表す符号の桁数をL(X)とすると、平均符号長は次の式で表されます。
$$\sum_{X=A,B,C} P(X)L(X)$$
・平均符号長の導出
文字列全体の中での「Ａ」の数は、文字列の長さを \(n\)とすると、\(nP(A)\)となる。
よって、「Ａ」を変換した符号（「0」「1」）の桁数は、\(nP(A)L(A)\)となる。
「Ｂ」「Ｃ」についても同様なので、文字列全体を符号化した時の符号の桁数は、
$$nP(A)L(A)+nP(B)L(B)+nP(C)L(C)$$
となる。1記号当たりでは、
$$\frac{1}{n}(nP(A)L(A)+nP(B)L(B)+nP(C)L(C))=\sum_{X=A,B,C} P(X)L(X)$$
であり、これが平均符号長である。
では、先ほどの各ルールにおいて平均符号長はどうなるか求めてみましょう。ここで、\(P(A)=\frac{1}{2}, P(B)=\frac{1}{4}, P(C)=\frac{1}{4}\)とします。
・ルール1：
$$\frac{1}{2}\cdot 2+\frac{1}{4}\cdot 2+\frac{1}{4}\cdot 2=2$$
・ルール2：
$$\frac{1}{2}\cdot 2+\frac{1}{4}\cdot 1+\frac{1}{4}\cdot 2=\frac{7}{4}$$
・ルール3：
$$\frac{1}{2}\cdot 1+\frac{1}{4}\cdot 2+\frac{1}{4}\cdot 2=\frac{3}{2}$$
よって、3つの中ではルール3が最も効率の良い符号化だと分かりました。平均符号長の式からも明らかですが、多く現れる記号には短い符号を、珍しい記号には長い符号を割り当てればよいと分かります。
では、最も効率を良くしたとき、つまり最も平均符号長が短くなるとき、平均符号長の値は何でしょうか。すぐに求めるのは難しそうですが、これを教えてくれるのが情報源符号化定理です。
情報源符号化定理
以下が情報源符号化定理の内容です。
情報源符号化定理
(1) あらゆる符号化は以下の不等式を満たす。
$$\sum_{X=A,B,C,\dots} P(X)L(X) \geq \sum_{X=A,B,C,\dots} P(X)i(X)$$
（平均符号長 \(\geq\) 平均情報量）
(2) また、以下の式を満たす符号化で平均符号長を最小にできる。
全ての記号に対し、\(L(X)=i(X)\) （符号の長さ＝情報量）
つまり、平均符号長が平均情報量に一致するときが最も効率の良い符号化であるということです。言い換えれば、どのような符号化であっても平均符号長を平均情報量より小さくすることはできない（“符号化の限界”）ということになります。
先ほどの例で確認してみましょう。情報量は \(i(X)=-\log_2 P(X)\)と表されるので、今回の文字列の平均情報量は、
$$\frac{1}{2}\cdot(-\log_2 \frac{1}{2})+\frac{1}{4}\cdot(-\log_2 \frac{1}{4})+\frac{1}{4}\cdot(-\log_2 \frac{1}{4})=\frac{3}{2}$$
となります。よって、ルール3の符号化は今回の文字列において最も効率の良い符号化の1つだと言えます。
(2)についても確認します。ルール3において、
$$L(A)=1, i(A)=-\log_2 \frac{1}{2}=1$$
$$L(B)=2, i(B)=-\log_2 \frac{1}{4}=2$$
$$L(C)=2, i(C)=-\log_2 \frac{1}{4}=2$$
となり、確かに定理に合致しています。他のルールについては、確認すると「符号の長さ＝情報量」とならない記号があることが分かります。
つまり、全ての記号で「符号の長さ＝情報量」となる方法を探すのが、最も効率の良い符号化を見つける近道と言えます。
3行まとめ
このページでは情報源符号化定理について解説しました。平均情報量の概念がこんな形で生かされるとは意外だったという方も多いのではないでしょうか。まとめると以下の通りです。
- 平均符号長とは、1記号当たりの変換したときの符号の長さである。
- 符号化は、平均符号長が短くなるものほど効率が良いといえる。
- 情報源符号化定理によれば、平均符号長の最小値は平均情報量に一致する。
皆様の参考になれば幸いです。
当サイトでは教養としての情報科学を体系的に紹介しています。以下から当サイトの記事一覧をご覧いただけます。