シャノンの通信路符号化定理 証明の概要

ウィキペディア

シャノンの通信路符号化定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/13 17:16 UTC 版)

証明の概要

情報理論における他のいくつかの主要な結果と同様に、雑音のある通信路符号化定理の証明は、達成可能性の結果と、対応する逆定理の結果を含む。ここでの場合、これらの2つの構成要素は、雑音のある通信路を介して通信する際に可能なデータレートの集合の有界性を示す役割を果たし、また対応する逆定理は、これらの上下界がタイトであることを示している。

以下の概要は、情報理論の教科書で学習できる様々な証明スタイルのうちの一例に過ぎない。

離散無記憶通信路の達成可能性

この達成可能性の証明は、漸近的等分配性(AEP)を利用する証明のスタイルに従う。他のスタイルとして、誤り指数を用いる情報理論の教科書もある。

どちらのタイプの証明でも、通信路を通じて使用される符号表がランダムに構成されているランダム符号化の論法を使う。これを用いることで解析が簡単になるが、それでもなお、通信路容量以下の任意のデータレートにおいて、誤り率が望むままに小さい符号が存在することを証明できる。

AEP関連の議論により、与えられた通信路について、長さ $n$ の情報源シンボル系列を $X_{1}^{n}$ 、長さ $n$ の通信路出力系列を $Y_{1}^{n}$ とするとき、同時典型集合(jointly typical set)を以下のように定義できる。

$A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}$

$2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}$

$2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}$

${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}}$ と $Y_{1}^{n}$ が上記で定義した同時典型集合の中にある場合、これらは同時典型(jointly typical)であるという。

ステップ

1. ランダム符号化の論法では、確率分布 $Q$ から長さ $n$ の符号語を$2^{nR}$ 個ランダムに生成する。
2. この符号は送信者と受信者に公開される。また、両者は通信路が使用している遷移行列 $p(y|x)$ を知っているものと仮定する。
3. メッセージ W は、符号語の集合上の一様分布に従って選択される。その一様分布は、$Pr(W=w)=2^{-nR},w=1,2,\dots ,2^{nR}$ である。
4. メッセージ W は、通信路を通じて送信される。
5. 受信者は、 $P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))$ に従って系列を受信する。
6. これらの符号語を通信路を通じて送信すると、$Y_{1}^{n}$ が受信され、Y に同時典型な符号語が丁度1個だけ存在するのであれば、何らかの情報源系列に復号される。同時典型な符号語が存在しない、あるいは2つ以上存在する場合は、誤りが宣言される。さらに、復号された符号語が元の符号語と一致しない場合にも誤りが発生する。これを典型集合復号(typical set decoding)という。

この枠組みにおける誤り率は、2つの部分に分けられる。

1. 受信系列Yに対して同時典型な系列Xが存在しない場合、誤りが発生する可能性がある。
2. 正しくない系列Xが受信系列Yと同時典型である場合、誤りが発生する可能性がある。

• 符号の構成がランダムであることから、符号全体で平均した平均誤り率は、送信されたメッセージ番号に依存しないと仮定できる。従って、一般性を失うことなく、 $W=1$ と仮定して良い。
• 同時AEPから、$n$ を大きくすると、同時典型な X が存在しない確率は0に近付く。この誤り率は、上界として $\varepsilon$ に限定できる。
• また、同時AEPから、ある特定の $X_{1}^{n}(i)$ とメッセージ$W=1$ から得られた $Y_{1}^{n}$ とが同時典型である確率は $\leq 2^{-n(I(X;Y)-3\varepsilon )}$ である。

メッセージ1が送信されたときの受信系列と、メッセージiとが同時典型である事象として、次のように事象$E_{i}$を定義する。

定義: $E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}$

${\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)$ であれば、$n$ を無限大に持って行くと、誤り率は0に近付くことが分かる。

最終的に、平均的な符号表が「良好」であることが示されたわけだが、性能が平均よりも優れている符号表が存在することは明らかであるため、雑音のある通信路を通じて任意の小さな誤り率で通信するという要求を満たしている。

離散無記憶通信路の弱逆定理

$2^{nR}$個の符号語からなる符号について考える。$W$は、この集合から一様的に選んだ符号語の番号であるとする。$X^{n}$ および $Y^{n}$ は、それぞれ送出した符号語と受信した符号語であるとする。

1. $nR=H(W)=H(W|Y^{n})+I(W;Y^{n})$ （エントロピーと相互情報量に関する恒等式を用いて）
2. $\leq H(W|Y^{n})+I(X^{n}(W);Y^{n})$ （Xは$W$の関数であるため）
3. $\leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})$ （ファノの不等式を用いて）
4. $\leq 1+P_{e}^{(n)}nR+nC$ （通信路容量は、相互情報量を最大化したものであることから）

これらのステップの結果として、 $P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}$ が得られる。 R が C よりも大きい場合、ブロック長 $n$ を無限大に持って行くと、$P_{e}^{(n)}$ は0より大きな下界を持つことになる。任意に小さな誤り率を得ることができるのは、R が C より小さい場合に限られる。

離散無記憶通信路の強逆定理

ウォルフォウィッツ(Wolfowitz)が1957年に証明した強逆定理(strong converse theorem)では、任意の有限の正の定数 $A$ について、

$P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}$

であることを示している。弱逆定理では、$n$ を無限大に持って行くと、誤り率が0より大きな下界を持つことしか示していないのに対し、強逆定理では誤り率が1に近付くことを示している。このように、$C$ は、完全に信頼できる通信とまったく信頼できない通信とをはっきりと分ける境界点になっている。