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

テンプレート:情報理論 情報理論において、シャノンの情報源符号化定理（シャノンのじょうほうげんふごうかていり、テンプレート:Lang-en）は、データ圧縮の可能な限界と情報量（シャノンエントロピー）の操作上の意味を確立する定理である。1948年のクロード・シャノンの論文『通信の数学的理論』で発表された。シャノンの第二基本定理（通信路符号化定理）に対してシャノンの第一基本定理とも言う。

情報源符号化定理によれば、（独立同分布(iid)の確率変数のデータの列の長さが無限大に近づくにつれて）、符号化率（記号1つ当たりの平均符号長）が情報源のシャノンエントロピーよりも小さいデータを、情報が失われることが事実上確実ではないように圧縮することは不可能である。しかし、損失の可能性が無視できる場合、符号化率を任意にシャノンエントロピーに近づけることは可能である。

シンボルコードの情報源符号化定理は、入力語（確率変数と見なされる）のエントロピーとターゲットアルファベットの大きさの関数として、符号語の可能な期待される長さに上限と下限を設定する。

提示

情報源符号化とは、情報源の記号（の列）からアルファベット記号（通常はビット）の列への写像である。情報源の記号は二進数ビットから正確に復元できる（可逆圧縮）か、何らかの歪みを伴って復元される（非可逆圧縮）。これが、データ圧縮の背後にあるコンセプトである。

情報源符号化定理

情報源符号化定理(Shannon 1948)は以下のように非形式的に提示されている(MacKay 2003, pg. 81, Cover:Chapter 5)。

情報量 テンプレート:Math を持つ テンプレート:Mvar 個の独立同分布の確率変数は、テンプレート:Mathのとき、無視できるほどの情報損失のリスクをもって テンプレート:Math ビット以上に圧縮できる。しかし、テンプレート:Math ビット以下に圧縮されたとき、情報が失われることは事実上確実である。

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

テンプレート:Math を2つの有限のアルファベットとし、テンプレート:Math と テンプレート:Math をそれぞれのアルファベットからの全ての有限語の集合とする。

テンプレート:Mvar を テンプレート:Math の値をとる確率変数とし、テンプレート:Math を テンプレート:Math から テンプレート:Math への一意復号可能な符号とする（ここで、テンプレート:Math）。テンプレート:Mvar を単語長 テンプレート:Math で与えられる確率変数とする。

テンプレート:Math が テンプレート:Mvar の最小単語長さという意味で最適であるとき、

$\frac{H(X)}{{\log }_{2}a}\le 𝔼S<\frac{H(X)}{{\log }_{2}a}+1$

である。(Shannon 1948)

証明

情報源符号化定理の証明

テンプレート:Mvar が独立同分布(iid)な情報源であるとき、その時系列 テンプレート:Math は、離散値の場合はエントロピー テンプレート:Math　、連続値の場合は差分エントロピーで独立同分布となる。情報源符号化定理によれば、情報源のエントロピーより大きい任意のレートの任意の テンプレート:Math に対して、十分に大きい テンプレート:Mvar と、情報源 テンプレート:Math の独立同分布な テンプレート:Mvar 個の複写をとり、これを テンプレート:Math この二進数ビットに写像するエンコーダがあり、それは、少なくとも テンプレート:Math の確率で、情報源記号 テンプレート:Math が二進数ビットから復元できる。

達成可能性の証明。 いくつかの テンプレート:Math を修正し、

$p(x_1,\dots ,x_n)=\mathrm{Pr}[X_1=x_1,\cdots ,X_n=x_n].$

とする。テンプレート:仮リンク テンプレート:Math は、以下のように定義される。

$A_n^{\epsilon }=\{(x_1,\cdots ,x_n):|-\frac{1}{n}\log p(x_1,\cdots ,x_n)-H_n(X)|<\epsilon \}$

テンプレート:仮リンク(AEP)が示すところによると、十分に大きい テンプレート:Mvar に対して、情報源によって生成された列が典型集合 テンプレート:Math に含まれる確率は 1 に近づく。特に、十分に大きい テンプレート:Mvar に対しては、$P((X_1,X_2,\cdots ,X_n)\in A_n^{\epsilon })$ は任意に 1 に近く、具体的には $1-\epsilon$ より大きくすることができる。

典型集合の定義は、典型集合にある列が以下を満足することを意味する。

$2^{-n(H(X)+\epsilon )}\le p(x_1,\cdots ,x_n)\le 2^{-n(H(X)-\epsilon )}$

注意:

• テンプレート:Mathから導かれる列 $(X_1,X_2,\cdots X_n)$ の確率は テンプレート:Math より大きい。
• $p(x_1,x_2,\cdots x_n)$ の左側（下限）からは $\left|A_n^{\epsilon }\right|\le 2^{n(H(X)+\epsilon )}$ となる。
• $p(x_1,x_2,\cdots x_n)$ の右側（上限）および全体集合 テンプレート:Math の全確率に対する下限からは $\left|A_n^{\epsilon }\right|\ge (1-\epsilon )2^{n(H(X)-\epsilon )}$ となる。

よって、$\left|A_n^{\epsilon }\right|\le 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon )$ ビットはこの集合の任意の文字列を指すのに十分である。

エンコードアルゴリズム : エンコーダは、入力列が典型集合内にあるかどうかをチェックする。そうであれば、典型集合内の入力列のインデックスを出力する。そうでなければ、エンコーダは任意の テンプレート:Math 桁の数を出力する。入力列が典型集合内にある限り（少なくとも テンプレート:Math の確率で）、エンコーダは何の誤りも生じない。従って、エンコーダの誤りの確率の上限は テンプレート:Mvar である。

逆の証明。その逆は、テンプレート:Math より小さいサイズの集合が 1 から離れる確率の集合をカバーすることを示すことで証明できる。

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

テンプレート:Math について、テンプレート:Math をそれぞれ可能な テンプレート:Math の語長とする。$q_i=a^{-s_i}/C$ と定義する。ここで、 テンプレート:Mvar は テンプレート:Math となるように選択される。

$\begin{array}{cc}H(X)& =-\sum _{i=1}^n{p}_i{\log }_2{p}_i\\ & \le -\sum _{i=1}^n{p}_i{\log }_2{q}_i\\ & =-\sum _{i=1}^n{p}_i{\log }_2{a}^{-s_i}+\sum _{i=1}^n{p}_i{\log }_{2}C\\ & =-\sum _{i=1}^n{p}_i{\log }_2{a}^{-s_i}+{\log }_{2}C\\ & \le -\sum _{i=1}^n-s_i{p}_i{\log }_{2}a\\ & \le 𝔼S{\log }_{2}a\\ \end{array}$

ここで、2行目はギブスの不等式に、5行目はクラフトの不等式による。

$C=\sum _{i=1}^n{a}^{-s_i}\le 1$

よって テンプレート:Math である。

2行目の不等式について、

$s_i=\lceil -{\log }_a{p}_i\rceil$

とすると、

$-{\log }_a{p}_i\le s_i<-{\log }_a{p}_i+1$

であり

$a^{-s_i}\le p_i$

であり

$\sum a^{-s_i}\le \sum p_i=1$

よって、クラフトの不等式には、これらの語長を持つ接頭辞のない符号が存在する。従って、最小の テンプレート:Mvar は以下を満たす。

$\begin{array}{cc}𝔼S& =\sum p_i{s}_i\\ & <\sum p_i(-{\log }_a{p}_i+1)\\ & =\sum -p_i\frac{{\log }_2{p}_i}{{\log }_{2}a}+1\\ & =\frac{H(X)}{{\log }_{2}a}+1\\ \end{array}$

非定常独立系への拡張

離散時間非定常独立情報源のための固定レート可逆情報源符号化

典型集合 テンプレート:Math を

$A_n^{\epsilon }=\{x_1^n:|-\frac{1}{n}\log p(X_1,\cdots ,X_n)-\overline{H_n}(X)|<\epsilon \}$

と定義する。

次に、与えられた テンプレート:Math に対して、 テンプレート:Mvar が十分に大きい場合、 テンプレート:Math である。あとは、典型集合の列をエンコードするだけであり。情報源符号化の通常の方法は、この集合の濃度が $2^{n(\overline{H_n}(X)+\epsilon )}$ であることを示す。 従って、テンプレート:Math より大きい確率で符号化するには、平均して テンプレート:Math ビットで十分である。ここで、テンプレート:Mvar を大きくすることによって、テンプレート:Mvar と テンプレート:Mvar を任意に小さくすることができる。

関連項目

• 通信路符号化
• シャノンの通信路符号化定理
• テンプレート:仮リンク
• テンプレート:仮リンク (AEP)