符号化定理の逆
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/06 03:37 UTC 版)
「加算性白色ガウス雑音」の記事における「符号化定理の逆」の解説
ここで、容量 C = 1 2 log ( 1 + P N ) {\displaystyle C={\frac {1}{2}}\log(1+{\frac {P}{N}})} より上のレートは達成できないことを示す。 コードブックに対してパワー制約を満たし、さらにメッセージが一様分布に従うと仮定する。 W {\displaystyle W} を入力メッセージ、 W ^ {\displaystyle {\hat {W}}} を出力メッセージとする。すると、情報は以下のように流れる。 W ⟶ X ( n ) ( W ) ⟶ Y ( n ) ⟶ W ^ {\displaystyle W\longrightarrow X^{(n)}(W)\longrightarrow Y^{(n)}\longrightarrow {\hat {W}}} ファノの不等式を利用して H ( W | W ^ ) ≤ 1 + n R P e ( n ) = n ϵ n {\displaystyle H(W|{\hat {W}})\leq 1+nRP_{e}^{(n)}=n\epsilon _{n}} ここで ϵ n → 0 {\displaystyle \epsilon _{n}\rightarrow 0} のとき P e ( n ) → 0 {\displaystyle P_{e}^{(n)}\rightarrow 0} X i {\displaystyle X_{i}} を指数iのコード名の符号化されたメッセージとすると、 n R = H ( W ) = I ( W ; W ^ ) + H ( W | W ^ ) ≤ I ( W ; W ^ ) + n ϵ n ≤ I ( X ( n ) ; Y ( n ) ) + n ϵ n = h ( Y ( n ) ) − h ( Y ( n ) | X ( n ) ) + n ϵ n = h ( Y ( n ) ) − h ( Z ( n ) ) + n ϵ n ≤ ∑ i = 1 n h ( Y i ) − h ( Z ( n ) ) + n ϵ n ≤ ∑ i = 1 n I ( X i ; Y i ) + n ϵ n {\displaystyle {\begin{aligned}nR&=H(W)\\&=I(W;{\hat {W}})+H(W|{\hat {W}})\\&\leq I(W;{\hat {W}})+n\epsilon _{n}\\&\leq I(X^{(n)};Y^{(n)})+n\epsilon _{n}\\&=h(Y^{(n)})-h(Y^{(n)}|X^{(n)})+n\epsilon _{n}\\&=h(Y^{(n)})-h(Z^{(n)})+n\epsilon _{n}\\&\leq \sum _{i=1}^{n}h(Y_{i})-h(Z^{(n)})+n\epsilon _{n}\\&\leq \sum _{i=1}^{n}I(X_{i};Y_{i})+n\epsilon _{n}\end{aligned}}} P i {\displaystyle P_{i}} を指数iのコード名の平均パワーとすると、 P i = 1 2 n R ∑ w x i 2 ( w ) {\displaystyle P_{i}={\frac {1}{2^{nR}}}\sum _{w}x_{i}^{2}(w)\,\!} ここで合計は全ての入力メッセージ w {\displaystyle w} より大きい。 X i {\displaystyle X_{i}} と Z i {\displaystyle Z_{i}} は独立なので、 Y i {\displaystyle Y_{i}} のパワーの期待値は雑音レベルが N {\displaystyle N} のとき、 E ( Y i 2 ) = P i + N {\displaystyle E(Y_{i}^{2})=P_{i}+N\,\!} そして、もし Y i {\displaystyle Y_{i}} が正規分布とすると、以下の式を得る。 h ( Y i ) ≤ 1 2 log 2 π e ( P i + N ) {\displaystyle h(Y_{i})\leq {\frac {1}{2}}\log {2\pi e}(P_{i}+N)\,\!} よって n R ≤ ∑ ( h ( Y i ) − h ( Z i ) ) + n ϵ n ≤ ∑ ( 1 2 log ( 2 π e ( P i + N ) ) − 1 2 log ( 2 π e N ) ) + n ϵ n = ∑ 1 2 log ( 1 + P i N ) + n ϵ n {\displaystyle {\begin{aligned}nR&\leq \sum (h(Y_{i})-h(Z_{i}))+n\epsilon _{n}\\&\leq \sum \left({\frac {1}{2}}\log(2\pi e(P_{i}+N))-{\frac {1}{2}}\log(2\pi eN)\right)+n\epsilon _{n}\\&=\sum {\frac {1}{2}}\log(1+{\frac {P_{i}}{N}})+n\epsilon _{n}\end{aligned}}} xの凹（下向き）関数である log ( 1 + x ) {\displaystyle \log(1+x)} にジェンセンの等式を適用すると、以下の式が得られる。 1 n ∑ i = 1 n 1 2 log ( 1 + P i N ) ≤ 1 2 log ( 1 + 1 n ∑ i = 1 n P i N ) {\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}{\frac {1}{2}}\log \left(1+{\frac {P_{i}}{N}}\right)\leq {\frac {1}{2}}\log \left(1+{\frac {1}{n}}\sum _{i=1}^{n}{\frac {P_{i}}{N}}\right)\,\!} 各コード名はそれぞれパワー制約を満たすため、平均もパワー制約を満たす。上の不等式を簡単にすると、 1 2 log ( 1 + 1 n ∑ i = 1 n P i N ) ≤ 1 2 log ( 1 + P N ) {\displaystyle {\frac {1}{2}}\log \left(1+{\frac {1}{n}}\sum _{i=1}^{n}{\frac {P_{i}}{N}}\right)\leq {\frac {1}{2}}\log \left(1+{\frac {P}{N}}\right)\,\!} よって、全体を合わせると R ≤ 1 2 log ( 1 + P N ) + ϵ n {\displaystyle R\leq {\frac {1}{2}}\log \left(1+{\frac {P}{N}}\right)+\epsilon _{n}} となる。したがって R {\displaystyle R} は ϵ n → 0 {\displaystyle \epsilon _{n}\rightarrow 0} のとき、前に導出した容量よりも幾分か小さい値でなくてはならない。
※この「符号化定理の逆」の解説は、「加算性白色ガウス雑音」の解説の一部です。
「符号化定理の逆」を含む「加算性白色ガウス雑音」の記事については、「加算性白色ガウス雑音」の概要を参照ください。
- 符号化定理の逆のページへのリンク
