離散無記憶通信路の達成可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/09 22:52 UTC 版)
「シャノンの通信路符号化定理」の記事における「離散無記憶通信路の達成可能性」の解説
この達成可能性の証明は、漸近的等分配性（英語版）(AEP)を利用する証明のスタイルに従う。他のスタイルとして、誤り指数（英語版）を用いる情報理論の教科書もある。 どちらのタイプの証明でも、通信路を通じて使用される符号表がランダムに構成されているランダム符号化の論法を使う。これを用いることで解析が簡単になるが、それでもなお、通信路容量以下の任意のデータレートにおいて、誤り率が望むままに小さい符号が存在することを証明できる。 AEP関連の議論により、与えられた通信路について、長さ n {\displaystyle n} の情報源シンボル系列を X 1 n {\displaystyle X_{1}^{n}} 、長さ n {\displaystyle n} の通信路出力系列を Y 1 n {\displaystyle Y_{1}^{n}} とするとき、同時典型集合(jointly typical set)を以下のように定義できる。 A ε ( n ) = { ( x n , y n ) ∈ X n × Y n {\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}} 2 − n ( H ( X ) + ε ) ≤ p ( X 1 n ) ≤ 2 − n ( H ( X ) − ε ) {\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}} 2 − n ( H ( Y ) + ε ) ≤ p ( Y 1 n ) ≤ 2 − n ( H ( Y ) − ε ) {\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}} 2 − n ( H ( X , Y ) + ε ) ≤ p ( X 1 n , Y 1 n ) ≤ 2 − n ( H ( X , Y ) − ε ) } {\displaystyle {2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}} 2つの系列 X 1 n {\displaystyle {X_{1}^{n}}} と Y 1 n {\displaystyle Y_{1}^{n}} が上記で定義した同時典型集合の中にある場合、これらは同時典型(jointly typical)であるという。 ステップ ランダム符号化の論法では、確率分布 Q から長さ n の符号語を 2 n R {\displaystyle 2^{nR}} 個ランダムに生成する。 この符号は送信者と受信者に公開される。また、両者は通信路が使用している遷移行列 p ( y | x ) {\displaystyle p(y|x)} を知っているものと仮定する。 メッセージ W は、符号語の集合上の一様分布に従って選択される。その一様分布は、 P r ( W = w ) = 2 − n R , w = 1 , 2 , … , 2 n R {\displaystyle Pr(W=w)=2^{-nR},w=1,2,\dots ,2^{nR}} である。 メッセージ W は、通信路を通じて送信される。 受信者は、 P ( y n | x n ( w ) ) = ∏ i = 1 n p ( y i | x i ( w ) ) {\displaystyle P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))} に従って系列を受信する。 これらの符号語を通信路を通じて送信すると、 Y 1 n {\displaystyle Y_{1}^{n}} が受信され、Y に同時典型な符号語が丁度1個だけ存在するのであれば、何らかの情報源系列に復号される。同時典型な符号語が存在しない、あるいは2つ以上存在する場合は、誤りが宣言される。さらに、復号された符号語が元の符号語と一致しない場合にも誤りが発生する。これを典型集合復号(typical set decoding)という。 この枠組みにおける誤り率は、2つの部分に分けられる。 受信系列Yに対して同時典型な系列Xが存在しない場合、誤りが発生する可能性がある。 正しくない系列Xが受信系列Yと同時典型である場合、誤りが発生する可能性がある。 符号の構成がランダムであることから、符号全体で平均した平均誤り率は、送信されたメッセージ番号に依存しないと仮定できる。従って、一般性を失うことなく、 W = 1 と仮定して良い。 同時AEPから、n を大きくすると、同時典型な X が存在しない確率は0に近付く。この誤り率は、上界として ε {\displaystyle \varepsilon } に限定できる。 また、同時AEPから、ある特定の X 1 n ( i ) {\displaystyle X_{1}^{n}(i)} とメッセージW = 1 から得られた Y 1 n {\displaystyle Y_{1}^{n}} とが同時典型である確率は ≤ 2 − n ( I ( X ; Y ) − 3 ε ) {\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon )}} である。 メッセージ1が送信されたときの受信系列と、メッセージiとが同時典型である事象として、次のように事象 E i {\displaystyle E_{i}} を定義する。 定義: E i = { ( X 1 n ( i ) , Y 1 n ) ∈ A ε ( n ) } , i = 1 , 2 , … , 2 n R {\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}} P ( error ) = P ( error | W = 1 ) ≤ P ( E 1 c ) + ∑ i = 2 2 n R P ( E i ) ≤ P ( E 1 c ) + ( 2 n R − 1 ) 2 − n ( I ( X ; Y ) − 3 ε ) ≤ ε + 2 − n ( I ( X ; Y ) − R − 3 ε ) . {\displaystyle {\begin{aligned}P({\text{error}})&{}=P({\text{error}}|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})\\&{}\leq P(E_{1}^{c})+(2^{nR}-1)2^{-n(I(X;Y)-3\varepsilon )}\\&{}\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}.\end{aligned}}} 通信路に関して R < I ( X ; Y ) {\displaystyle R<I(X;Y)} であれば、 n {\displaystyle n} を無限大に持って行くと、誤り率は0に近付くことが分かる。 最終的に、平均的な符号表が「良好」であることが示されたわけだが、性能が平均よりも優れている符号表が存在することは明らかであるため、雑音のある通信路を通じて任意の小さな誤り率で通信するという要求を満たしている。
※この「離散無記憶通信路の達成可能性」の解説は、「シャノンの通信路符号化定理」の解説の一部です。
「離散無記憶通信路の達成可能性」を含む「シャノンの通信路符号化定理」の記事については、「シャノンの通信路符号化定理」の概要を参照ください。
- 離散無記憶通信路の達成可能性のページへのリンク
