AWGNの通信路は離散時間の事象の添え字
i
{\displaystyle i}
とする一連の出力
Y
i
{\displaystyle Y_{i}}
により表される。
Y
i
{\displaystyle Y_{i}}
は入力
X
i
{\displaystyle X_{i}}
と雑音
Z
i
{\displaystyle Z_{i}}
の和である。
Z
i
{\displaystyle Z_{i}}
は独立同分布 であり、平均0、分散
N
{\displaystyle N}
の正規分布 から得られるものである。さらに
Z
i
{\displaystyle Z_{i}}
は
X
i
{\displaystyle X_{i}}
と相関しないと仮定される。
Z
i
∼
N
(
0
,
N
)
{\displaystyle Z_{i}\sim {\mathcal {N}}(0,N)\,\!}
Y
i
=
X
i
+
Z
i
.
{\displaystyle Y_{i}=X_{i}+Z_{i}.\,\!}
雑音nが0ではなく、
X
i
{\displaystyle X_{i}}
が十分に制約されない限り、通信路の容量は無限である。入力に対する最も一般的な制約は、いわゆる「パワー」制約であり、通信路を介して送信されるコード名
(
x
1
,
x
2
,
…
,
x
k
)
{\displaystyle (x_{1},x_{2},\dots ,x_{k})}
に対して必要なものである。
1
k
∑
i
=
1
k
x
i
2
≤
P
,
{\displaystyle {\frac {1}{k}}\sum _{i=1}^{k}x_{i}^{2}\leq P,}
ここで
P
{\displaystyle P}
は最大の通信路容量を表す。よって、パワーが制限された通信路の容量は以下になる。
C
=
max
f
(
x
)
s.t.
E
(
X
2
)
≤
P
I
(
X
;
Y
)
{\displaystyle C=\max _{f(x){\text{ s.t. }}E\left(X^{2}\right)\leq P}I(X;Y)\,\!}
f
(
x
)
{\displaystyle f(x)}
は
X
{\displaystyle X}
の分布である。
I
(
X
;
Y
)
{\displaystyle I(X;Y)}
を展開し、微分エントロピー の観点から書くと以下の式になる。
I
(
X
;
Y
)
=
h
(
Y
)
−
h
(
Y
|
X
)
=
h
(
Y
)
−
h
(
X
+
Z
|
X
)
=
h
(
Y
)
−
h
(
Z
|
X
)
{\displaystyle {\begin{aligned}I(X;Y)=h(Y)-h(Y|X)&=h(Y)-h(X+Z|X)&=h(Y)-h(Z|X)\end{aligned}}\,\!}
しかし
X
{\displaystyle X}
と
Z
{\displaystyle Z}
は独立である。よって
I
(
X
;
Y
)
=
h
(
Y
)
−
h
(
Z
)
{\displaystyle I(X;Y)=h(Y)-h(Z)\,\!}
となる。ガウスの微分エントロピー を評価すると
h
(
Z
)
=
1
2
log
(
2
π
e
N
)
{\displaystyle h(Z)={\frac {1}{2}}\log(2\pi eN)\,\!}
となる。
X
{\displaystyle X}
と
Z
{\displaystyle Z}
は独立で、それらの和が
Y
{\displaystyle Y}
になるから、:
E
(
Y
2
)
=
E
(
(
X
+
Z
)
2
)
=
E
(
X
2
)
+
2
E
(
X
)
E
(
Z
)
+
E
(
Z
2
)
=
P
+
N
{\displaystyle E(Y^{2})=E((X+Z)^{2})=E(X^{2})+2E(X)E(Z)+E(Z^{2})=P+N\,\!}
この範囲より、微分エントロピーの性質を推測すると
h
(
Y
)
≤
1
2
log
(
2
π
e
(
P
+
N
)
)
{\displaystyle h(Y)\leq {\frac {1}{2}}\log(2\pi e(P+N))\,\!}
となる。よって通信路の容量は相互情報量 における達成可能な最大の境界で与えられ、
I
(
X
;
Y
)
≤
1
2
log
(
2
π
e
(
P
+
N
)
)
−
1
2
log
(
2
π
e
N
)
{\displaystyle I(X;Y)\leq {\frac {1}{2}}\log(2\pi e(P+N))-{\frac {1}{2}}\log(2\pi eN)\,\!}
I
(
X
;
Y
)
{\displaystyle I(X;Y)}
は
X
∼
N
(
0
,
P
)
{\displaystyle X\sim {\mathcal {N}}(0,P)\,\!}
のときに最大となり、このとき通信路容量
C
{\displaystyle C}
は以下となる。
C
=
1
2
log
(
1
+
P
N
)
{\displaystyle C={\frac {1}{2}}\log \left(1+{\frac {P}{N}}\right)\,\!}
1
{\displaystyle 1}
から
M
{\displaystyle M}
の範囲の指数を持つ通信路を介してメッセージを送るとする。この指数は識別が可能なメッセージの数を表している。
M
{\displaystyle M}
個のメッセージを
n
{\displaystyle n}
ビットにエンコードすると、レート
R
{\displaystyle R}
は次のように定義される。
R
=
log
M
n
{\displaystyle R={\frac {\log M}{n}}\,\!}
レートは、もし
n
{\displaystyle n}
が無限大に近づくにつれて誤差の最大確率が0になるようなコードの並びが存在すれば、実現できると考えられる。容量
C
{\displaystyle C}
は実現可能な最大のレートである。
雑音レベルが
N
{\displaystyle N}
のAWGNの通信路を通して送信された長さ
n
{\displaystyle n}
の符号を考える。受信したとき、符号ベクトルの分散は
N
{\displaystyle N}
であり、平均は送信された符号である。そのベクトルは送信された符号周りの半径
n
(
N
+
ϵ
)
{\displaystyle {\sqrt {n(N+\epsilon )}}}
の球に含まれる確率が非常に高い。受信した全てのメッセージをこの球を中心として符号に写像することによりデコードするとき、受信したベクトルが球の外にある場合エラーが発生するが、これはほとんど起こらないことである。
各符号ベクトルは、それに復号される受信符号ベクトルの関連する球を持ち、このような球は符号を一意に写像しなくてはならない。よって、これらの球は交差してはならないため、球充填 の問題に差し当たる。いくつの異なる符号が、
n
{\displaystyle n}
ビットの符号ベクトルに充填できるだろうか?受信されたベクトルは、最大エネルギー
n
(
P
+
N
)
{\displaystyle n(P+N)}
を有する。したがって半径が
n
(
P
+
N
)
{\displaystyle {\sqrt {n(P+N)}}}
の球を占有する必要がある。それぞれの符号の球の半径は
n
N
{\displaystyle {\sqrt {nN}}}
である。n 次元での球の体積は
r
n
{\displaystyle r^{n}}
に正比例するので、送信電力で我々の球に充填することができる、一意に復号可能な球体の最大数Pは
(
n
(
P
+
N
)
)
n
2
(
n
N
)
n
2
=
2
n
2
log
(
1
+
P
/
N
)
{\displaystyle {\frac {(n(P+N))^{\frac {n}{2}}}{(nN)^{\frac {n}{2}}}}=2^{{\frac {n}{2}}\log(1+P/N)}\,\!}
となる。この議論によりレートRは
1
2
log
(
1
+
P
/
N
)
{\displaystyle {\frac {1}{2}}\log(1+P/N)}
以下になる。
この節では最後の節からのレート上限の達成可能性について述べる。
エンコーダーにもデコーダーにも知られた暗号表は長さ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の符号が存在する。
ここで、容量
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}
のとき、前に導出した容量よりも幾分か小さい値でなくてはならない。