シャノンの情報源符号化定理

内容

アルファベット上の確率分布に従い、エントロピー $H$（ビット単位、$\log_2$ を使用）を持つ離散無記憶情報源が記号を出力するとする。このとき任意の $\varepsilon > 0$ に対し、ブロック長 $n$ を十分大きくとれば、記号あたりの平均長が $H + \varepsilon$ 未満となる可逆ブロック符号が存在する。逆に、記号あたりの平均長を $H$ 未満にできる可逆符号は存在しない。要するに、エントロピー $H$ は記号あたりの平均ビット数の理論的最小値である。

なぜ正しいのか?

メッセージの長さは、それが運ぶ『驚き』の量とちょうど釣り合う：ほぼ確実に出現する記号を伝えるにはほとんどビットが要らず、稀な記号には多くのビットが必要になる。エントロピーはこの『驚き』（$-\log_2 p$ で測る）を情報源全体で平均したものであり、確固たる下限を与える——よくあるパターンは圧縮して取り除けるが、ランダムな情報源をその統計自体に内在する真の予測不可能性より下に圧縮することは決してできない。

この定理を使うトピック

ステップごとの証明

この定理のステップごとの証明はまだありません。