誤差指数

情報理論において、チャネル コードまたは情報源コードのブロック長に対する誤り指数は、コードのブロック長とともに誤り確率が指数的に減少する割合です。正式には、大きなブロック長に対する誤り確率の負の対数とコードのブロック長の極限比として定義されます。たとえば、デコーダの誤り確率が （ はブロック長）のときに低下する場合、誤り指数は です。この例では、が大きい に対して に近づきます。情報理論の定理の多くは漸近的な性質を持っています。たとえば、チャネル符号化定理では、チャネル容量よりも小さい任意のレートでは、ブロック長が無限大になるとチャネル コードの誤り確率を 0 にすることができますと述べられています。実際の状況では、通信の遅延には制限があり、ブロック長は有限でなければなりません。したがって、ブロック長が無限大になると誤り確率がどのように低下​​するかを研究することが重要です。 ${\displaystyle P_{\mathrm {error} }}$ ${\displaystyle e^{-n\alpha }}$ ${\displaystyle n}$ ${\displaystyle \alpha }$ ${\displaystyle {\frac {-\ln P_{\mathrm {error} }}{n}}}$ ${\displaystyle \alpha }$ ${\displaystyle n}$

チャネル符号化における誤差指数

時間不変DMCの場合

チャネル符号化定理は、任意の ε > 0 およびチャネル容量未満の任意のレートにおいて、十分に長いメッセージブロックXのブロック誤り確率がε > 0 未満となるように保証できる符号化および復号化方式が存在することを述べています。また、チャネル容量を超える任意のレートにおいて、ブロック長が無限大になるほど、受信側におけるブロック誤り確率は1に近づきます。

チャネル符号化の設定を以下のように仮定する：チャネルは、対応するコードワード（長さn ）を送信することで、任意のメッセージを送信できる。コードブックの各要素は、確率質量関数Qを持つ確率分布に従ってiid に抽出される。復号側では、最尤復号法が実行される。 ${\displaystyle M=2^{nR}\;}$

をコードブック内の 番目のランダムコードワードとします。ここで、はから まで変化します。最初のメッセージが選択されたと仮定すると、コードワードが送信されます。 が受信された場合、コードワードが のように誤って検出される確率は、次のようになります。 ${\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個のメッセージがあり、コードブックのエントリは独立同値であるため、他のメッセージと混同される確率は上記の式の積となります。和集合の境界を用いると、任意のメッセージと混同される確率は次のように制限されます。 ${\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 }.}$

上記の式で 2 つの合計を選択して組み合わせます。${\displaystyle s=1-s\rho }$ ${\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.\;}$

ソースコーディングにおける誤差指数

時間不変離散記憶なし情報源の場合

情報源符号化定理は、 およびなどの任意の離散時間 iid 情報源について、情報源のエントロピー未満の任意のレートに対して、十分に大きい および が存在し、情報源の iid 繰り返し を受け取り、それをバイナリ ビットにマッピングして、少なくとも の確率でバイナリ ビットから情報源シンボルを復元できるエンコーダが存在することを述べています。 ${\displaystyle \varepsilon >0}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle X^{1:n}}$ ${\displaystyle n.(H(X)+\varepsilon )}$ ${\displaystyle X^{1:n}}$ ${\displaystyle 1-\varepsilon }$

可能性のあるメッセージの総数を とします。次に、可能性のあるソース出力シーケンスのそれぞれを、一様分布を使用して、他のすべてとは独立してランダムにメッセージの 1 つにマッピングします。ソースが生成されると、対応するメッセージが宛先に送信されます。メッセージは、可能性のあるソース文字列の 1 つにデコードされます。エラーの確率を最小化するために、デコーダーは を最大化するソースシーケンスにデコードします。ここで、はメッセージが送信されたイベントを表します。このルールは、 を最大化するメッセージにマッピングされるソースシーケンスの集合の中からソースシーケンスを見つけることと同じです。この削減は、メッセージが他のすべてとは独立してランダムに割り当てられたという事実から生じます。 ${\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})\,}$

をソースシーケンスがソースシーケンスと同じメッセージにマッピングされたイベントとするとします。したがって、を2つのソースシーケンスとが同じメッセージにマッピングされ たイベントとすると、${\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'}\,}$ ${\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 }\,.}$

ここで、不等式はUnion Boundの変形から導かれます。最後に、この上限を の和に適用すると、次のようになります。 ${\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].\,}$

参照

• ソースコーディング
• チャネル符号化

参考文献

R.ギャラガー『情報理論と信頼性の高い通信』、ワイリー、1968年