シャノンのソース符号化定理

情報理論において、シャノンのソース符号化定理（または無雑音符号化定理）は、ソースが独立同分布の確率変数であるデータに対するデータ圧縮の統計的限界と、シャノンエントロピーの操作的意味を確立する。

クロード・シャノンにちなんで名付けられたソース符号化定理は、独立同分布（iid）ランダム変数（iid）データのストリームの長さが無限大に近づく極限において、符号化率（シンボルあたりの平均ビット数）がソースのシャノンエントロピーよりも小さくなるようにデータを圧縮することは、情報が失われることがほぼ確実であることを示しています。しかし、符号化率をシャノンエントロピーに任意に近づけることは可能であり、その場合、情報の損失確率は無視できるほど小さくなります。

記号符号のソース符号化定理は、入力語のエントロピー（確率変数とみなされる）と目標アルファベットのサイズの関数として、符号語の最小期待長の上限と下限を規定する。

なお、依存関係が多いデータ（そのソースが独立同分布のランダム変数ではないデータ）の場合、オブジェクトの最小記述長を定量化するコルモゴロフ複雑度の方が、データ圧縮の限界を記述するのに適しています。シャノンエントロピーは頻度規則性のみを考慮しますが、コルモゴロフ複雑度はすべてのアルゴリズム規則性を考慮するため、一般的に後者の方が小さくなります。一方、オブジェクトがランダムプロセスによって生成され、頻度規則性のみを持つ場合、エントロピーは高い確率で複雑度に近くなります（Shen et al. 2017）。^{[ 1 ]}

ソース符号化とは、情報源からの記号列をアルファベット記号列（通常はビット）にマッピングする方式であり、ソース記号をアルファベット記号から完全に復元できる（可逆ソース符号化）か、あるいは多少の歪みを伴って復元できる（非可逆ソース符号化）ようにするものです。これはデータ圧縮の手法の一つです。

Xがiidソースである場合、その時系列X ₁、 ...、X _{n は}、離散値の場合はエントロピーH ( X )の iid であり、連続値の場合は微分エントロピーの iid です。ソース符号化定理は、任意のε > 0、つまりソースのエントロピーよりも大きい任意のレートH ( X ) + εに対して、十分に大きなnとエンコーダが存在し、ソースのn回の iid 繰り返しX ^{1: n}を受け取り、それをn ( H ( X ) + ε )バイナリ ビットにマッピングして、ソース シンボルX ^{1: n}が少なくとも1 − εの確率でバイナリ ビットから復元可能であることを示しています。

達成可能性の証明。あるε > 0を固定し、

${\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].}$

典型的な集合A ε ⁿ_は次のように定義されます。

${\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\}.}

漸近等分配特性（AEP）は、 nが十分に大きい場合、ソースによって生成されたシーケンスが、定義された典型的なセットA ^ε _nに含まれる確率が1に近づくことを示しています。特に、nが十分に大きい場合、${\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })}$は任意に 1 に近づけることができ、具体的には より大きくすることができる。${\displaystyle 1-\varepsilon }$（ 証明についてはAEPを参照のこと。）

典型集合の定義は、典型集合に含まれる数列が以下の条件を満たすことを意味する。

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}}$

• シーケンスの確率${\displaystyle (X_{1},X_{2},\cdots X_{n})}$Aから抽出される^ε _nは1 − εより大きい。
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}}$これは、左辺（下限）から導かれる。${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$。
• ${\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}}$これは、の上限から導かれる。${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$そして、全集合A ^ε _n の総確率の下限。

以来${\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n(H(X)+\varepsilon )}$ビット数が多いほど、このセット内の任意の文字列を指すことができます。

符号化アルゴリズム：エンコーダは入力シーケンスが典型的なセットに含まれているかどうかをチェックします。含まれている場合は、典型的なセット内での入力シーケンスのインデックスを出力します。含まれていない場合は、任意のn ( H ( X ) + ε )桁の数値を出力します。入力シーケンスが典型的なセットに含まれている限り（少なくとも1 − εの確率で）、エンコーダはエラーを起こしません。したがって、エンコーダのエラー確率はεで上限が定められます。

逆の証明：逆は、 A ^ε _n (指数の意味で)より小さい任意の集合が、1から離れた確率の集合を覆うことを示すことによって証明されます。

1 ≤ i ≤ nに対して、 s _{i を}各可能なx _iの単語長とする。${\displaystyle q_{i}=a^{-s_{i}}/C}$ここで、Cはq ₁ + ... + q _n = 1となるように選択される。すると

${\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\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\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&=\mathbb {E} S\log _{2}a\\\end{aligned}}}$

ここで、2行目はギブスの不等式から導かれ、5行目はクラフトの不等式から導かれる。

${\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}$

したがって、log C ≤ 0 です。

2番目の不等式については、次のように設定できます。

${\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }$

となることによって

${\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}$

など

${\displaystyle a^{-s_{i}}\leq p_{i}}$

そして

${\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}$

したがって、クラフトの不等式により、これらの語長を持つ接頭辞フリー符号が存在する。したがって、最小のSは以下を満たす。

${\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}}}$

• チャネルコーディング
• 誤差指数
• 雑音チャネル符号化定理