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

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

情報理論において、シャノンの情報源符号化定理は、データ圧縮の限界と情報量（シャノンエントロピー）の操作的な意味を確立する基本的な定理です。この定理は、1948年にクロード・シャノンによって発表され、データ圧縮における理論的な基盤となっています。

定理の概要

情報源符号化定理は、独立同分布（iid）に従う確率変数のデータ列において、データ列の長さが無限に近づくにつれて、以下の2つの重要な点を述べています。

1. 圧縮の限界: データ圧縮において、符号化率（記号1つ当たりの平均符号長）を情報源のシャノンエントロピーよりも小さくすることは、事実上不可能であり、情報が失われる可能性が高まります。
2. 圧縮の可能性: 損失の可能性を無視できる範囲であれば、符号化率を任意にシャノンエントロピーに近づけることが可能です。

言い換えれば、この定理は、データを圧縮する際に、情報量を失わずにどれだけ圧縮できるかの理論的な限界を示しています。

シンボルコードの情報源符号化定理

より具体的なシンボルコードにおける情報源符号化定理は、入力語（確率変数）のエントロピーと、符号化に使用するターゲットアルファベットのサイズに基づいて、符号語の期待される長さの上限と下限を定めます。

具体的には、Σ1とΣ2をそれぞれ入力アルファベットとターゲットアルファベットとし、XをΣ1の値をとる確率変数、fをΣ1からΣ2への一意復号可能な符号とします。このとき、Xの符号語の長さの期待値E[S]は、以下の式で表されます。

H(X) / log2(a) ≤ E[S] < H(X) / log2(a) + 1

ここで、H(X)はXのエントロピー、aはターゲットアルファベットのサイズです。この式は、符号化の効率がエントロピーによって制限されることを示しています。

情報源符号化とは

情報源符号化とは、情報源から発生する記号列を、別のアルファベット（通常はビット列）に変換する処理です。この変換は、情報の損失を伴わない可逆圧縮と、多少の歪みを許容する非可逆圧縮に分類されます。データ圧縮の基本的な概念であり、効率的なデータ保存や伝送に不可欠です。

定理の数学的な詳細

情報源符号化定理は、数学的に厳密に証明されており、その証明には、漸近的等分配性（AEP）やクラフトの不等式などの概念が用いられます。以下では、定理の証明の概略を説明します。

情報源符号化定理の証明

独立同分布の情報源Xについて、その時系列X1, ..., Xnを考えます。このとき、情報源のエントロピーH(X)に対して、十分に大きいnと任意のε>0に対し、情報源X1:nのn個のコピーをn(H(X) + ε)ビットに写像するエンコーダが存在し、その復元は少なくとも1-εの確率で成功します。

この証明は、典型集合という概念を用いて行われます。典型集合とは、情報源によって生成された列の中で、その確率がほぼ等しく、かつその確率の平均値がエントロピーに近い集合のことです。十分大きなnに対して、情報源から生成される列が典型集合に属する確率は1に近づきます。

典型集合内の列は、以下の不等式を満たします。

2^(-n(H(X) + ε)) ≤ p(x1, ..., xn) ≤ 2^(-n(H(X) - ε))

この不等式から、典型集合の要素数|Aεn|は、以下のように評価できます。

Aεn

≤ 2^(n(H(X) + ε))

Aεn

≥ (1-ε)2^(n(H(X) - ε))

これらの評価から、n(H(X) + ε)ビットで典型集合内の任意の文字列を識別できることがわかります。エンコーダは、入力列が典型集合内にあるかどうかをチェックし、あればそのインデックスを出力します。これにより、少なくとも1-εの確率で、エラーなく情報を圧縮できます。

シンボルコードの情報源符号化定理の証明

シンボルコードの定理の証明では、ギブスの不等式とクラフトの不等式が用いられます。まず、符号語の長さをsiとすると、

qi = a^(-si) / C

と定義します。ここで、Cは確率の総和が1になるように調整されます。次に、エントロピーH(X)をqを用いて評価すると、

H(X) ≤ E[S] log2(a)

が得られます。また、符号語の長さsiを

si = ⌈-loga(pi)⌉

とすると、クラフトの不等式を満たす符号が存在し、符号語の期待値E[S]は

E[S] < H(X) / log2(a) + 1

となります。これらの評価から、符号語の期待値はエントロピーによって制限されることがわかります。

非定常独立系への拡張

情報源符号化定理は、非定常独立情報源にも拡張可能です。この場合、典型集合の定義を修正し、平均エントロピーを用いることで、同様の議論を進めることができます。

まとめ

シャノンの情報源符号化定理は、データ圧縮の理論的な限界を明確に示す重要な定理です。この定理は、情報量（エントロピー）という概念を導入することで、情報圧縮の効率を定量的に評価することを可能にしました。この定理を理解することは、データ圧縮アルゴリズムの設計や、情報理論の研究において不可欠です。

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