シャノンの情報源符号化定理
p ( x 1 , x 2 , ⋯ x n ) {\displaystyle p(x_{1},x_{2},\cdots x_{n})} の右側(上限)および全体集合 Aεn の全確率に対する下限からは | A n ε | ≥ ( 1 − ε ) 2 n ( H ( X ) − ε ) {\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}} となる。
よって、 | A n ε | ≤ 2 n ( H ( X ) + ε ) , n . ( H ( X ) + ε ) {\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n.(H(X)+\varepsilon )} ビットはこの集合の任意の文字列を指すのに十分である。
エンコードアルゴリズム : エンコーダは、入力列が典型集合内にあるかどうかをチェックする。そうであれば、典型集合内の入力列のインデックスを出力する。そうでなければ、エンコーダは任意の n(H(X) + ε) 桁の数を出力する。入力列が典型集合内にある限り(少なくとも 1 − ε の確率で)、エンコーダは何の誤りも生じない。従って、エンコーダの誤りの確率の上限は ε である。
逆の証明。その逆は、Aεn より小さいサイズの集合が 1 から離れる確率の集合をカバーすることを示すことで証明できる。
典型集合 Aεn を
A n ε = { x 1 n : | − 1 n log  p ( X 1 , ⋯ , X n ) − H n ̄ ( X ) | < ε } {\displaystyle A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}}
と定義する。
次に、与えられた δ > 0 に対して、 n が十分に大きい場合、 Pr(Aεn) > 1 − δ である。あとは、典型集合の列をエンコードするだけであり。情報源符号化の通常の方法は、この集合の濃度が 2 n ( H n ̄ ( X ) + ε ) {\displaystyle 2^{n({\overline {H_{n}}}(X)+\varepsilon )}} であることを示す。 従って、1 − δ より大きい確率で符号化するには、平均して Hn(X) + ε ビットで十分である。ここで、n を大きくすることによって、ε と δ を任意に小さくすることができる。
情報源符号化とは、情報源の記号(の列)からアルファベット記号(通常はビット)の列への写像である。情報源の記号は二進数ビットから正確に復元できる(可逆圧縮)か、何らかの歪みを伴って復元される(非可逆圧縮)。これが、データ圧縮の背後にあるコンセプトである。
情報源符号化定理(Shannon 1948)は以下のように非形式的に提示されている(MacKay 2003, pg. 81, Cover:Chapter 5)。
情報量 H(X) を持つ N 個の独立同分布の確率変数は、N → ∞のとき、無視できるほどの情報損失のリスクをもって N H(X) ビット以上に圧縮できる。しかし、N H(X) ビット以下に圧縮されたとき、情報が失われることは事実上確実である。
であり
a − s i ≤ p i {\displaystyle a^{-s_{i}}\leq p_{i}}
であり
∑ a − s i ≤ ∑ p i = 1 {\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}
よって、クラフトの不等式には、これらの語長を持つ接頭辞のない符号が存在する。従って、最小の S は以下を満たす。
E S = ∑ p i s i < ∑ p i ( − log a  p i + 1 ) = ∑ − p i log 2  p i log 2  a + 1 = H ( X ) log 2  a + 1 {\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}
X が独立同分布(iid)な情報源であるとき、その時系列 X1, ..., Xn は、離散値の場合はエントロピー H(X) 、連続値の場合は差分エントロピーで独立同分布となる。情報源符号化定理によれば、情報源のエントロピーより大きい任意のレートの任意の ε > 0 に対して、十分に大きい n と、情報源 X の独立同分布な n 個の複写をとり、これを n(H(X) + ε) この二進数ビットに写像するエンコーダがあり、それは、少なくとも 1 − ε の確率で、情報源記号 X が二進数ビットから復元できる。
達成可能性の証明。 いくつかの ε > 0 を修正し、
p ( x 1 , ... , x n ) = Pr [ X 1 = x 1 , ⋯ , X n = x n ] . {\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].}
とする。典型集合(英語版) Aεn は、以下のように定義される。
A n ε = { ( x 1 , ⋯ , x n ) : | − 1 n log  p ( x 1 , ⋯ , x n ) − H n ( X ) | < ε } {\displaystyle A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}}