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

情報理論において、シャノンの情報源符号化定理（またはノイズレス符号化定理）は、独立した同一分布のランダム変数を情報源とするデータの可能なデータ圧縮の統計的限界と、シャノンエントロピーの操作上の意味を確立します。

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

シンボル コードのソースコーディング定理は、入力ワードのエントロピー(ランダム変数と見なされる) とターゲット アルファベットのサイズの 関数として、コードワードの予想される最小の長さに上限と下限を設定します。

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

ソース コーディングとは、情報ソースのシンボル (シーケンス) をアルファベット シンボル (通常はビット) のシーケンスにマッピングすることです。これにより、ソース シンボルはバイナリ ビットから正確に復元されるか (ロスレス ソース コーディング)、またはある程度の歪み内で復元されます (ロスのあるソース コーディング)。これは、データ圧縮の 1 つの方法です。

情報理論において、情報源符号化定理（シャノン1948）^[2]は非公式に次のように述べている（マケイ2003、81ページ、^[3]カバー2006、第5章^[4]）。

エントロピーH ( X )を持つN個のi.idランダム変数は、 N →∞のとき、情報損失のリスクが無視できるほど小さいN H ( X )ビット以上に圧縮できます。しかし逆に、 N H ( X )ビット未満に圧縮された場合、情報が失われることはほぼ確実です。

符号化されたシーケンスは、デコーダーがソースを知っているという仮定の下で、圧縮されたメッセージを双一義的に表現します。実用的な観点からは、この仮説は常に正しいとは限りません。その結果、エントロピー符号化が適用されると、送信されるメッセージは になります。通常、ソースを特徴付ける情報は、送信されるメッセージの先頭に挿入されます。 ${\displaystyle NH(X)}$${\displaystyle NH(X)+(inf.source)}$

Σ ₁、Σ _{2 が}2 つの有限のアルファベットを表すものとし、 Σとします。^∗
₁そしてΣ^∗
₂それぞれのアルファベットからのすべての有限単語の集合を表します。

XはΣ1_の範囲内の値を取るランダム変数であり、fはΣから一意にデコード可能なコードであるとする。  ^∗
₁Σに^∗
₂ここで|Σ ₂ | = aです。Sはコードワードf  ( X )の長さによって与えられるランダム変数を表します。  

f がXの期待語長が最小であるという意味で最適である場合、(Shannon 1948)は次のようになります。   

${\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} [S]<{\frac {H(X)}{\log _{2}a}}+1}$

ここで、期待値演算子を表します。 ${\displaystyle \mathbb {E} }$

X がiidソースであるとすると、その時系列 X ₁、...、X _{n は}、離散値の場合はエントロピー H ( X ) 、連続値の場合は微分エントロピーを持つ 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^εn
_​は次のように定義されます。

${\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の場合、は 1 に任意に近くすることができ、具体的には よりも大きくなります( 証明については AEP を参照)。${\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })}$${\displaystyle 1-\varepsilon }$

典型集合の定義は、典型集合に含まれるシーケンスが次の条件を満たすことを意味します。

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

• Aから数列が抽出される確率${\displaystyle (X_{1},X_{2},\cdots X_{n})}$^ε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 )}}$であり、これは の上限と、集合A 全体の確率の下限から導かれる。${\displaystyle p(x_{1},x_{2},\cdots x_{n})}$^ε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の語長を表すものとする。 を定義する。ここでC はq ₁ + ... + q _n = 1となるように選択される。すると ${\displaystyle q_{i}=a^{-s_{i}}/C}$

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

典型的なセットAを定義する^εn
_​として：

${\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 − δ。ここでは、典型的なセット内のシーケンスをエンコードするだけですが、ソースコーディングの通常の方法では、このセットの濃度が より小さいことが示されています。したがって、平均すると、1 − δ を超える確率でエンコードするには、 H _n ( X ) + εビットで十分です。ここで、n を大きくすることで、 εとδ を任意に小さくすることができます。 ${\displaystyle 2^{n({\overline {H_{n}}}(X)+\varepsilon )}}$

• チャネルコーディング
• 誤差指数
• 雑音のある通信路の符号化定理