誤差指数

チャネル符号化定理によれば、任意のε > 0およびチャネル容量より小さい任意のレートに対して、十分に長いメッセージブロックXにおいてブロック誤りの確率がε > 0未満となるように使用できる符号化および復号化方式が存在する。また、チャネル容量より大きい任意のレートに対しては、ブロック長が無限大に近づくにつれて、受信側でのブロック誤りの確率は1に近づく。

チャネルコーディング設定を以下のように仮定します。チャネルは、${\displaystyle M=2^{nR}\;}$メッセージを、対応する符号語（長さn）を送信することによって復号します。符号帳の各コンポーネントは、確率質量関数Qを持つ何らかの確率分布に従って独立同分布で抽出されます。復号側では、最尤復号が行われます。

させて${\displaystyle X_{i}^{n}}$になる${\displaystyle i}$コードブック内の 番目のランダムなコードワード、${\displaystyle i}$から${\displaystyle 1}$に${\displaystyle M}$最初のメッセージが選択されたと仮定すると、コードワードは${\displaystyle X_{1}^{n}}$が送信されます。$\displaystyle y_{1}^{n}}$が受信された場合、コードワードが誤って検出される確率は${\displaystyle X_{2}^{n}}$は：

${\displaystyle P_{\mathrm {error} \ 1\to 2}=\sum _{x_{2}^{n}}Q(x_{2}^{n})1(p(y_{1}^{n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n}))。}$

機能${\displaystyle 1(p(y_{1}^{n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n}))}$上限がある

${\displaystyle \left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}}$

のために${\displaystyle s>0\;}$したがって、

${\displaystyle P_{\mathrm {error} \ 1\to 2}\leq \sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}.}$

メッセージの総数はMであり、コードブックのエントリは iid であるため、${\displaystyle X_{1}^{n}}$他のメッセージと混同される${\displaystyle M}$上記の式を倍します。和集合境界を使用すると、混同する確率は${\displaystyle X_{1}^{n}}$いかなるメッセージも以下によって制限される：

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}\right)^{\rho }}$

いかなる場合でも${\displaystyle 0<\rho <1}$すべての組み合わせについて平均すると${\displaystyle x_{1}^{n},y_{1}^{n}}$:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{1-s\rho }\right)\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})[p(y_{1}^{n}\mid x_{2}^{n})]^{s}\right)^{\rho }.}$

選択する${\displaystyle s=1-s\rho }$そして2つの合計を合計すると${\displaystyle x_{1}^{n}}$上記の式において：

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{\frac {1}{1+\rho }}\right)^{1+\rho }.}$

符号語の要素の独立性と、チャネルの離散的で無記憶性を利用する。

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\prod _{i=1}^{n}\sum _{y_{i}}\left(\sum _{x_{i}}Q_{i}(x_{i})[p_{i}(y_{i}\mid x_{i})]^{\frac {1}{1+\rho }}\right)^{1+\rho }}$

符号語の各要素が同一の分布を持ち、したがって定常的であるという事実を利用する。

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{\frac {1}{1+\rho }}\right)^{1+\rho }\right)^{n}.}$

Mを^2nRに置き換えて定義する

${\displaystyle E_{o}(\rho ,Q)=-\ln \left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{1/(1+\rho )}\right)^{1+\rho }\right),}$

エラーの確率は

${\displaystyle P_{\mathrm {error} }\leq \exp(-n(E_{o}(\rho ,Q)-\rho R)).}$

Qと${\displaystyle \rho }$は、境界が最も厳しくなるように選択する必要があります。したがって、誤差指数は次のように定義できます。

${\displaystyle E_{r}(R)=\max _{Q}\max _{\rho \in [0,1]}E_{o}(\rho ,Q)-\rho R.\;}$

ソース符号化定理は、任意の${\displaystyle \varepsilon >0}$および、次のような任意の離散時間 iid ソース${\displaystyle X}$そして、ソースのエントロピーよりも小さい任意のレートに対しては、十分に大きな${\displaystyle n}$そしてエンコーダー${\displaystyle n}$ソースのiid繰り返し、${\displaystyle X^{1:n}}$、そしてそれをマッピングします${\displaystyle n.(H(X)+\varepsilon )}$ソースシンボルがバイナリビットになる${\displaystyle X^{1:n}}$バイナリビットから少なくとも確率で復元可能${\displaystyle 1-\varepsilon }$。

させて${\displaystyle M=e^{nR}\,\!}$を可能なメッセージの総数とする。次に、可能なソース出力シーケンスのそれぞれを、一様分布を使用してランダムに、かつ他のすべてとは独立に、いずれかのメッセージにマッピングする。ソースが生成されると、対応するメッセージが生成される。${\displaystyle M=m\,}$その後、宛先に送信されます。メッセージは、考えられるソース文字列のいずれかに復号されます。エラーの可能性を最小限に抑えるため、デコーダはソースシーケンスに復号します。${\displaystyle X_{1}^{n}}$最大化する${\displaystyle P(X_{1}^{n}\mid A_{m})}$、 どこ${\displaystyle A_{m}\,}$メッセージイベントを示します${\displaystyle m}$送信されました。このルールは、ソースシーケンスを見つけることと同等です。${\displaystyle X_{1}^{n}}$メッセージにマッピングされるソースシーケンスのセットの中で${\displaystyle m}$最大化する${\displaystyle P(X_{1}^{n})}$この削減は、メッセージがランダムに、かつ他のすべての要素とは独立して割り当てられたという事実から生じる。

したがって、エラーが発生する場合の例として、ソースシーケンスが${\displaystyle X_{1}^{n}(1)}$メッセージにマッピングされました${\displaystyle 1}$ソースシーケンスも同様でした${\displaystyle X_{1}^{n}(2)}$。 もし${\displaystyle X_{1}^{n}(1)\,}$ソースで生成されましたが、${\displaystyle P(X_{1}^{n}(2))>P(X_{1}^{n}(1))}$するとエラーが発生します。

させて${\displaystyle S_{i}\,}$ソースシーケンスが${\displaystyle X_{1}^{n}(i)}$ソースで生成されたため、${\displaystyle P(S_{i})=P(X_{1}^{n}(i))\,.}$すると、エラーの確率は次のように分解できます。${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\,.}$したがって、注意は上限を見つけることに集中できます。${\displaystyle P(E\mid S_{i})\,}$。

させて${\displaystyle A_{i'}\,}$ソースシーケンスが${\displaystyle X_{1}^{n}(i')}$ソースシーケンスと同じメッセージにマッピングされました${\displaystyle X_{1}^{n}(i)}$そしてそれは${\displaystyle P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))}$したがって、${\displaystyle X_{i,i'}\,}$2 つのソースシーケンスが${\displaystyle i\,}$そして${\displaystyle i'\,}$同じメッセージにマッピングすると、

${\displaystyle P(A_{i'})=P\left(X_{i,i'}\bigcap P(X_{1}^{n}(i')\right)\geq P(X_{1}^{n}(i)))\,}$

そして、${\displaystyle P(X_{i,i'})={\frac {1}{M}}\,}$そして他のすべてとは独立している

${\displaystyle P(A_{i'})={\frac {1}{M}}P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\,.}$

左辺の項の単純な上限は次のように定めることができる。

${\displaystyle \left[P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\right]\leq \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\,}$

任意の実数に対して${\displaystyle s>0\,.}$この上限は、以下の点に注目することで検証できます。${\displaystyle P(P(X_{1}^{n}(i'))>P(X_{1}^{n}(i)))\,}$どちらも等しい${\displaystyle 1\,}$または${\displaystyle 0\,}$なぜなら、与えられた入力シーケンスの確率は完全に決定論的だからである。したがって、もし${\displaystyle P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))\,,}$それから${\displaystyle {\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\geq 1\,}$そのため、その場合不等式が成り立ちます。他の場合も不等式が成り立つのは、

${\displaystyle \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\geq 0\,}$

すべての可能なソース文字列に対して。したがって、すべてを組み合わせ、いくつかの${\displaystyle \rho \in [0,1]\,}$それを持っています

${\displaystyle P(E\mid S_{i})\leq P(\bigcup _{i\neq i'}A_{i'})\leq \left(\sum _{i\neq i'}P(A_{i'})\right)^{\rho }\leq \left({\frac {1}{M}}\sum _{i\neq i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.}$

ここで、不等式は和集合の変形から導かれる。最後に、この上限を総和に適用すると、${\displaystyle P(E)\,}$それを持っている:

${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\leq \sum _{i}P(X_{1}^{n}(i))\left({\frac {1}{M}}\sum _{i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.}$

合計は今やすべてにわたって取ることができる${\displaystyle i'\,}$なぜなら、それは境界を増やすだけだからです。最終的には、

${\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\sum _{i}P(X_{1}^{n}(i))^{1-s\rho }\left(\sum _{i'}P(X_{1}^{n}(i'))^{s}\right)^{\rho }\,.}$

簡単にするために${\displaystyle 1-s\rho =s\,}$となることによって${\displaystyle s={\frac {1}{1+\rho }}\,.}$この新しい値を代入すると${\displaystyle s\,}$上記のエラー確率の上限に、${\displaystyle i'\,}$は単なるダミー変数であり、合計ではエラー確率の上限として以下が与えられます。

${\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\left(\sum _{i}P(X_{1}^{n}(i))^{\frac {1}{1+\rho }}\right)^{1+\rho }\,.}$

${\displaystyle M=e^{nR}\,\!}$そして各構成要素${\displaystyle X_{1}^{n}(i)\,}$は独立している。したがって、上記の式を簡略化すると、

${\displaystyle P(E)\leq \exp \left(-n\left[\rho R-\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\right]\right).}$

指数部の項は最大化されるべきである${\displaystyle \rho \,}$エラー確率の上限値を最大にするために。

賃貸${\displaystyle E_{0}(\rho )=\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\,,}$ソースコーディングの場合のエラー指数は次のとおりです。

${\displaystyle E_{r}(R)=\max _{\rho \in [0,1]}\left[\rho R-E_{0}(\rho )\right].\,}$