符号化とエントロピー

情報源が発するメッセージを、通信路に送れるよう符号化することを考えます。(電話音声を電気信号に符号化するなど。)

このとき符号化を解除してメッセージを復元できることはもちろん、なるべく多くの情報を速く送るにはどう符号化したらよいかという疑問が生まれます。これこそシャノンの理論の基本的な問題意識でした。

具体的な設定

情報源が一定のスピードで記号aかbをある確率にしたがって発信しています。ここではまず前後の記号が独立である場合、すなわちベルヌーイ試行を考えます。また記号の列をここではメッセージと呼ぶことにします。

さて、長さLのメッセージを通信路に送り込めるよう0と1の系列に変換するという問題を考えます。この議論は記号二種類、符号二種類の場合を扱いますが、どのような種類数の組み合わせも同様に扱えます。また話を簡単にするため、固定された長さの符号に変換することにします。この長さをNとします。

最低限必要なビット長

このとき、可能なすべてのメッセージ(長さL)を異なる符号で表すには、Nを最低どの程度大きくすればよいでしょうか。いまベルヌーイ試行を考えているので、メッセージを構成する各記号はa, bどちらも可能です。よって全部で2^L個の異なる可能なメッセージがある。また長さNの符号は同様に2^N個の異なるメッセージを表すことができる。よってNは最低でもLに等しくとる必要があります。つまり

は絶対に満たす必要がある。この左辺は符号長をメッセージの長さで割っているので、一記号あたりの符号長という意味を持ちます。この量は通信路を流れる情報の伝達速度を決定します。

すべてを符号化するのは諦める

この伝達能率を1以下にするには(つまり最大の伝達能率の壁を破るには)、すべてのメッセージを符号化することを諦めるという手があります。我々はベルヌーイ試行の考察において、メッセージ長が十分大きければ、典型的なメッセージ(つまりaをほぼpの割合、bをほぼqの割合だけ含むメッセージ)の個数はexp(LH)のように増加し、それらが現れる確率はexp(-LH)のように減少することを見ました。

いまは0・1の符号化(二値符号)を考えているので、エントロピーHの底を2に変換すれば、

となるわけです。

つまりメッセージ長が十分大きいとき、このような典型的なメッセージ以外のメッセージが現れる確率は非常に小さく(この確率をεとします)、Lが大きい極限でε→0となることを導きました。これを見ると、典型的なメッセージのみを符号化することにしても、符号化されていないメッセージが出てくることは無視できる事象になります。また典型的なメッセージはLHの符号長で(Lの大きさによってこれより少し大きくなるものの)表現しきれるでしょう。このとき一記号あたりの符号長は、

となり、情報源が最大エントロピーに達していない限り(つまりa, bが等確率で発信される)、さきほどのすべてを符号化する場合の限界能率を突破し、エントロピーに(上から)近づけていくことができるのです。エントロピーのふるまいについては以下を参照のこと:

符号を情報源としてみる

さらに0と1符号系列そのものを情報源とみることもできます。このときメッセージ長が大きければ、NHの長さのビット列において0と1が等確率で起こることになります。というのも元の情報源の長いメッセージが上の議論によって等確率のベルヌーイ試行とみなせるからです。すると符号化システムを情報源とみたときのエントロピーが最大値の1に近づいていくこともわかります。

シャノンの符号化定理

以上をまとめます。

ベルヌーイ試行を二値符号化する問題において、典型的なメッセージのみを符号化することにしても、それ以外のメッセージが観測される確率は任意に小さくすることができ、かつ一記号あたりの符号長を情報源のエントロピーに限りなく近づけることができる。このとき同時に符号自体のエントロピーは最大値に近づいていく。

エントロピーは情報伝達能率の限界を決定するという解釈がここから出てくるのですが、さらにエントロピーは典型的なメッセージの個数増大の速度と、その確率の減少速度をも決めています。情報伝達の理論においてエントロピーが以下に本質的な量かがここから窺えます。次回はマルコフ連鎖について同様の議論をします。

参考文献

[1] クロード・E.シャノン、ワレン・ウィーバー、『通信の数学的理論』、植松友彦訳、ちくま学芸文庫 (2009).

[2] R.G.Gallager, "Information Theory and Reliable Communication" (John Wiley & Sons, New York, 1968).