達成可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/06 03:37 UTC 版)
「加算性白色ガウス雑音」の記事における「達成可能性」の解説
この節では最後の節からのレート上限の達成可能性について述べる。 エンコーダーにもデコーダーにも知られた暗号表は長さn、独立同一分布で正規分布、分散 P − ϵ {\displaystyle P-\epsilon } 平均0の符号を選ぶことにより生成される。nが大きくなると、コードブックの実験的な分散はその分布の分散に非常に近くなり、それにより確率的にパワー制約を破るのを回避する。 受け取られたメッセージは、コードブックに書かれている一意に結びついた典型的なメッセージへと復号される。 もし、そのようなメッセージが存在しない、もしくは、パワー制約に違反する場合、複合エラーが宣言される。 X n ( i ) {\displaystyle X^{n}(i)} はメッセージ i {\displaystyle i} のコード名、 Y n {\displaystyle Y^{n}} は is, as before the received vector.3つの出来事を定義する。 出来事 U {\displaystyle U} :受け取ったメッセージのパワーが P {\displaystyle P} よりも大きい。 出来事 V {\displaystyle V} :送受信されたコード名は結びついて典型的なものではない。 出来事 E j {\displaystyle E_{j}} : ( X n ( j ) , Y n ) {\displaystyle (X^{n}(j),Y^{n})} は A ϵ ( n ) {\displaystyle A_{\epsilon }^{(n)}} の中にあり, i ≠ j {\displaystyle i\neq j} となる典型的なセット、つまり、間違ったコード名が受信したベクトルと結びついて典型的である。 したがって、エラーは U {\displaystyle U} 、 V {\displaystyle V} 、 E i {\displaystyle E_{i}} のいずれかが起きた時に生じる。多数のものを扱う法則により、nが無限に近づくにつれて P ( U ) {\displaystyle P(U)} は0に収束し、漸近等分割性を結びつけることにより、 P ( V ) {\displaystyle P(V)} に同じものが適用できる。よって十分に大きい n {\displaystyle n} では、 P ( U ) {\displaystyle P(U)} と P ( V ) {\displaystyle P(V)} はともに ϵ {\displaystyle \epsilon } より小さくなる。 i ≠ j {\displaystyle i\neq j} において、 X n ( i ) {\displaystyle X^{n}(i)} and X n ( j ) {\displaystyle X^{n}(j)} が独立であるので、 X n ( i ) {\displaystyle X^{n}(i)} と Y n {\displaystyle Y^{n}} も独立であるとわかる。よって漸近等分割性を結びつけることにより、 P ( E j ) = 2 − n ( I ( X ; Y ) − 3 ϵ ) {\displaystyle P(E_{j})=2^{-n(I(X;Y)-3\epsilon )}} となる。これにより、エラー確率 P e ( n ) {\displaystyle P_{e}^{(n)}} が計算でき、 P e ( n ) ≤ P ( U ) + P ( V ) + ∑ j ≠ i P ( E j ) ≤ ϵ + ϵ + ∑ j ≠ i 2 − n ( I ( X ; Y ) − 3 ϵ ) ≤ 2 ϵ + ( 2 n R − 1 ) 2 − n ( I ( X ; Y ) − 3 ϵ ) ≤ 2 ϵ + ( 2 3 n ϵ ) 2 − n ( I ( X ; Y ) − R ) ≤ 3 ϵ {\displaystyle {\begin{aligned}P_{e}^{(n)}&\leq P(U)+P(V)+\sum _{j\neq i}P(E_{j})\\&\leq \epsilon +\epsilon +\sum _{j\neq i}2^{-n(I(X;Y)-3\epsilon )}\\&\leq 2\epsilon +(2^{nR}-1)2^{-n(I(X;Y)-3\epsilon )}\\&\leq 2\epsilon +(2^{3n\epsilon })2^{-n(I(X;Y)-R)}\\&\leq 3\epsilon \end{aligned}}} となる。よって、nが無限大に近づくことにより、 P e ( n ) {\displaystyle P_{e}^{(n)}} は0に収束し、 R < I ( X ; Y ) − 3 ϵ {\displaystyle R<I(X;Y)-3\epsilon } となる。それゆえ、前に導出した容量に任意に近いレートRの符号が存在する。
※この「達成可能性」の解説は、「加算性白色ガウス雑音」の解説の一部です。
「達成可能性」を含む「加算性白色ガウス雑音」の記事については、「加算性白色ガウス雑音」の概要を参照ください。
- 達成可能性のページへのリンク
