Shannon–Hartleyの定理(Shannon–Hartley theorem)とは、帯域幅 $W$ の通信路に白色の Gauss 雑音が加わるとき、平均の送信電力 $P$、帯域の中の雑音の電力 $N$ のもとで誤りの確率をいくらでも小さくして送れる速さの上限が 1 秒あたり $W\log_2(1+P/N)$ ビットであるという定理である。離散時間の Gauss 通信路の容量 $\frac12\log_2(1+P/N)$ を 1 秒あたり $2W$ 回使うことにあたる。帯域を広げても容量は $P/(N_0\ln2)$ を超えず、1 bit あたりのエネルギーには $\ln2$ 倍の雑音密度という下限がある。
前提知識: 相互情報量, Shannonの通信路符号化定理, 正規分布
Shannon–Hartleyの定理(Shannon–Hartley theorem)は、白色の Gauss 雑音が加わる帯域幅 $W$ Hz の通信路で、平均の送信電力が $P$、雑音の電力密度が $N_0$ のとき、誤りの確率をいくらでも小さくして送れる速さの上限(通信路容量)が
$$
C=W\log_2\Bigl(1+\frac{P}{N_0W}\Bigr)\quad\text{bit/s}
$$
であるという定理である。$P/(N_0W)$ は帯域の中の信号と雑音の電力の比(SN 比)である。式は C. E. Shannon の 1948 年の論文の定理 17 にある(Sha48 Theorem 17)。名前の Hartley は、送れる情報の量が帯域幅と時間の積に比例するという R. V. L. Hartley の 1928 年の議論(Har28)による。
この記事では、まず離散時間の Gauss 通信路について、1 回あたりの容量が $\frac12\log_2(1+P/N)$ であることを、達成と逆の両方について完全に証明する。連続時間の式は、離散時間の式に 1 秒あたり $2W$ 個の標本を当てはめたものとして導く。標本化で帯域制限の通信路が離散時間の通信路に帰着することの厳密な証明は扱わず、連続時間の式は Sha48 の定理として述べる。そのうえで、帯域を広げても容量は $P/(N_0\ln2)$ を超えないこと、1 bit あたりのエネルギーに $\ln2$ という下限があること(Shannon の限界)を示す。以下 $\log$ は 2 を底とし、$\ln$ は自然対数とする。
$P,N>0$ とする。Gauss 通信路 は、実数の入力 $x_i$ に対し $Y_i=x_i+Z_i$ を出力する通信路で、$Z_1,Z_2,\dots$ は独立で $N(0,N)$ に従う。長さ $n$、メッセージ数 $M$ の 符号 とは、符号語 $c_1,\dots,c_M\in\mathbb R^n$ と、可測な復号 $g\colon\mathbb R^n\to\{1,\dots,M\}$ の組で、各符号語が 電力の制約
$$
\|c_m\|^2=\sum_{i=1}^nc_{m,i}^2\le nP
$$
を満たすものをいう。メッセージ $M'$ を一様に選び $Y^n=c_{M'}+Z^n$ を送るときの $P_e:=P(g(Y^n)\ne M')$ を誤りの確率という。速さ $R\ge0$ が 達成可能 であるとは、各 $n$ で $M\ge2^{nR}$ の符号がとれ $P_e\to0$ となることをいい、達成可能な速さの上限を 容量 $C(P,N)$ という。
$C(P,N)=\dfrac12\log\Bigl(1+\dfrac PN\Bigr)$ である。
「$\ge$」は節「達成:Gauss 分布の乱択符号」の prf-sh-achieve で、「$\le$」は節「逆」の prf-sh-converse で証明する。
この形は PW25 Theorem 20.11(p. 400)にもある。$P/N=15$ なら 1 回あたり $2$ bit である。
$\varphi_s(t):=(2\pi s)^{-1/2}e^{-t^2/(2s)}$ を $N(0,s)$ の密度とし、$x,y\in\mathbb R$ と $0< P'$ に対し
$$
\imath(x;y):=\log\frac{\varphi_N(y-x)}{\varphi_{P'+N}(y)}=\frac12\log\frac{P'+N}{N}+\frac{\log e}2\Bigl(\frac{y^2}{P'+N}-\frac{(y-x)^2}N\Bigr)
$$
とおく(情報密度)。$X\sim N(0,P')$ と独立な $Z\sim N(0,N)$ で $Y=X+Z$ とすると、$Y\sim N(0,P'+N)$ で、$E[Y^2]=P'+N$、$E[(Y-X)^2]=N$ だから
$$
E[\imath(X;Y)]=\frac12\log\Bigl(1+\frac{P'}N\Bigr)
$$
である。$\imath(X;Y)$ は Gauss の変数の 2 次式なので分散も有限である。
$y\in\mathbb R^n$ を固定し、$\bar X^n$ を成分が独立に $N(0,P')$ に従う確率変数とする。$\imath_n(x^n;y^n):=\sum_{i=1}^n\imath(x_i;y_i)$ とおくと、任意の実数 $\gamma$ に対し $P(\imath_n(\bar X^n;y)>\gamma)\le2^{-\gamma}$ である。
$f(x):=\prod_i\varphi_{P'}(x_i)$、$q(y):=\prod_i\varphi_{P'+N}(y_i)$、$\ell(x):=\prod_i\varphi_N(y_i-x_i)$ とおく。独立な Gauss の変数の和はまた Gauss なので $\int\varphi_{P'}(x)\varphi_N(t-x)\,dx=\varphi_{P'+N}(t)$ で、$\int f(x)\ell(x)\,dx=q(y)$ である。$\imath_n(x;y)>\gamma$ は $\ell(x)>2^\gamma q(y)$ と同値なので
$$
P(\imath_n(\bar X^n;y)>\gamma)=\int f(x)\,\mathbf 1\{\ell(x)>2^\gamma q(y)\}\,dx\le\int f(x)\frac{\ell(x)}{2^\gamma q(y)}\,dx=2^{-\gamma}
$$
である。$\square$
この評価は $y$ ごとに成り立つので、$y$ が送られた符号語に応じてどう分布していても使える。
$0< P'< P$ を $R< \frac12\log(1+P'/N)=:I'$ ととり、$\delta:=(I'-R)/3$ とおく。$M:=\lceil2^{nR}\rceil$、$\gamma:=\log M+n\delta$ とする。
1. 符号の作り方。 $\bar c_1,\dots,\bar c_M\in\mathbb R^n$ を、全成分が独立に $N(0,P')$ に従うように選ぶ。$\|\bar c_m\|^2\le nP$ なら $c_m:=\bar c_m$、そうでなければ $c_m:=0$ とする。どの $c_m$ も電力の制約を満たす。復号は、$\imath_n(\bar c_m;y)>\gamma$ を満たす $m$ がただ 1 つならそれを、そうでなければ $1$ を出す。
2. 誤りの分解。 メッセージ $m$ を送ると $Y^n=c_m+Z^n$ で、$Z^n$ は符号と独立である。誤りが起きるのは、次のどれかが起きるときに限る(どれも起きなければ $m$ だけが閾値を超え、正しく復号される)。
3. 各項の評価。 (a) $\|\bar c_m\|^2/n$ は平均 $P'$ の独立同分布の変数の標本平均なので、大数の法則 により $P(\|\bar c_m\|^2>nP)\to0$ である。(b) $\imath_n(\bar c_m;\bar c_m+Z^n)$ は上の $\imath(X;Y)$ と同じ分布の独立な $n$ 個の和で、平均は $nI'$、分散は $n$ に比例する。$\gamma\le nR+1+n\delta\le n(I'-\delta)$($n\ge1/\delta$)なので、Chebyshevの不等式 から (b) の確率は $0$ に近づく。(c) $m'\ne m$ の $\bar c_{m'}$ は $Y^n=c_m+Z^n$ と独立なので、$Y^n$ の値を固定して lem-sh-threshold を使い、$Y^n$ について平均すると $P(\imath_n(\bar c_{m'};Y^n)>\gamma)\le2^{-\gamma}$ である。$M-1$ 個を足して (c) の確率は $M2^{-\gamma}=2^{-n\delta}$ 以下である。
4. 結論。 平均した誤りの確率が $0$ に近づくので、各 $n$ で誤りの確率がその平均以下の符号がある。よって $R$ は達成可能である。$P'< P$ は $\frac12\log(1+P'/N)>R$ の範囲で自由なので、$R< \frac12\log(1+P/N)$ がすべて達成可能である。$\square$
電力の制約を満たさない符号語を $0$ に置き換えたのは、Gauss の分布がどんな大きな値もとりうるからである。平均の電力を $P'< P$ にしておけば、置き換えの起こる確率は大数の法則で $0$ に近づく。
$a\in\mathbb R$、$s,t>0$ に対し $D(N(a,s)\,\|\,N(0,t))=\dfrac12\log\dfrac ts+\dfrac{\log e}2\Bigl(\dfrac{s+a^2}t-1\Bigr)$ である。
$Y\sim N(a,s)$ とすると $\log\dfrac{\varphi_s(Y-a)}{\varphi_t(Y)}=\dfrac12\log\dfrac ts+\dfrac{\log e}2\Bigl(\dfrac{Y^2}t-\dfrac{(Y-a)^2}s\Bigr)$ で、$E[Y^2]=s+a^2$、$E[(Y-a)^2]=s$ を代入すればよい。$\square$
電力の制約を満たす符号をとり、$M'$ を一様なメッセージ、$Y^n:=c_{M'}+Z^n$ とする。
1. Fano の不等式。 $M'\to Y^n\to g(Y^n)$ に Fano の不等式を使うと、$M'$ の各値の確率は $1/M$ なので
$$
I(M';Y^n)\ge(1-P_e)\log M-h(P_e)\ge(1-P_e)\log M-1
$$
である(PW25 Theorem 3.12 の式 (3.19)、p. 57。$h$ は 2 値エントロピー関数)。
2. 相互情報量の上界。 任意の分布 $Q$ に対し $I(M';Y^n)=D(P_{Y^n\mid M'}\|Q\mid P_{M'})-D(P_{Y^n}\|Q)\le D(P_{Y^n\mid M'}\|Q\mid P_{M'})$ である(PW25 Theorem 4.1、p. 67。右辺は Kullback–Leiblerダイバージェンス の条件つきの平均)。$Q$ を成分が独立に $N(0,P+N)$ に従う分布とする。$M'=m$ のとき $Y^n$ の成分は独立に $N(c_{m,i},N)$ に従うので、密度の比の対数は成分ごとの和になり、lem-sh-kl から
$$
D(P_{Y^n\mid M'=m}\|Q)=\frac n2\log\Bigl(1+\frac PN\Bigr)+\frac{\log e}2\Bigl(\frac{nN+\|c_m\|^2}{P+N}-n\Bigr)\le\frac n2\log\Bigl(1+\frac PN\Bigr)
$$
である(最後に $\|c_m\|^2\le nP$ を使った)。$m$ について平均して $I(M';Y^n)\le\frac n2\log(1+P/N)$ を得る。
3. 結論。 1 と 2 から $(1-P_e)\log M\le\frac n2\log(1+P/N)+1$ である。$M\ge2^{nR}$ で $P_e\to0$ なら、両辺を $n$ で割って $R\le\frac12\log(1+P/N)$ を得る。$\square$
段 2 で $Q$ を出力の分布の候補 $N(0,P+N)$ にとったところで電力の制約が使われ、雑音が Gauss であることは $D$ の計算に使われる。
帯域幅 $W$ Hz の信号は、標本化定理 により 1 秒あたり $2W$ 個の標本で決まる。電力密度 $N_0/2$ の 白色雑音 を帯域に制限すると、各標本の雑音は独立な $N(0,N_0/2)$ に従うとみなせる。時間 $T$ の間の信号のエネルギー $PT$ を $2WT$ 個の標本に分けると、1 標本あたりの電力は $P/(2W)$ で、SN 比は $\frac{P/(2W)}{N_0/2}=\frac P{N_0W}$ である。1 秒あたりに thm-sh-discrete の容量を $2W$ 回使うと
$$
2W\cdot\frac12\log\Bigl(1+\frac P{N_0W}\Bigr)=W\log\Bigl(1+\frac P{N_0W}\Bigr)
$$
となる。
帯域幅 $W$ に制限された入力に、電力密度が一定の白色の Gauss 雑音(帯域の中の電力 $N=N_0W$)が加わる連続時間の通信路の容量は、平均の電力の制約 $P$ のもとで $C=W\log(1+P/N)$ bit/s である(Sha48 Theorem 17)。
$P,N_0>0$ を固定し $C(W):=W\log(1+\frac P{N_0W})$ とおく。$C(W)$ は $W>0$ について狭義に増加し、$W\to\infty$ で $\dfrac P{N_0\ln2}$ に収束する。特に $C(W)< \dfrac P{N_0\ln2}$ である。
$s:=P/(N_0W)$ とおくと $C(W)=\frac P{N_0\ln2}\cdot\frac{\ln(1+s)}s$ で、
$$
\frac{\ln(1+s)}s=\int_0^1\frac{dt}{1+st}
$$
は $s>0$ について狭義に減少し、$s\to0$ で $1$ に収束する。$W$ が増えると $s$ は減るので、主張が従う。$\square$
帯域を広げると 1 標本あたりの SN 比が下がり、標本の数の増加と打ち消し合う。電力が限られると、帯域をいくら広げても容量は有限にとどまる。
速さ $R>0$ で 1 Hz あたりの速さ $\eta:=R/W$、1 bit あたりのエネルギー $E_b:=P/R$ とする。$R\le C$ なら
$$
\frac{E_b}{N_0}\ge\frac{2^\eta-1}\eta>\ln2\approx0.693
$$
である。右の値は $\eta\to0$ で $\ln2$ に近づく。
$P=E_b\eta W$ なので $R\le C$ は $\eta\le\log(1+\eta E_b/N_0)$、すなわち $E_b/N_0\ge(2^\eta-1)/\eta$ と同値である。$\frac{2^\eta-1}\eta=\ln2\int_0^12^{\eta t}\,dt$ は $\eta>0$ について狭義に増加し、$\eta\to0$ で $\ln2$ に収束する。$\square$
$\ln2$ をデシベルで書くと約 $-1.59$ dB である。これより少ないエネルギーで、誤りの確率をいくらでも小さくして 1 bit ずつ送る方法はない。$\eta=1$ では $E_b/N_0\ge1$、$\eta=2$ では $E_b/N_0\ge1.5$ が要る。
帯域幅 $W=3000$ Hz、SN 比 $P/N=1000$(30 dB)の通信路の容量は
$$
C=3000\log_2 1001\approx29{,}902\ \text{bit/s}
$$
である。SN 比を 2 倍にしても容量は 1 秒あたり約 $3000$ bit しか増えないが、帯域を 2 倍にすると($N_0$ を一定として SN 比は半分になり)容量は約 $53{,}800$ bit/s になる。
$P/N_0=10^4$ とする。prop-sh-band の $C(W)$ は、$W=10^3$ で約 $3459$、$W=10^4$ でちょうど $10^4$、$W=10^5$ で約 $13{,}750$、$W=10^6$ で約 $14{,}355$ bit/s で、上限 $10^4/\ln2\approx14{,}427$ bit/s に近づく。
Hartley は、$s$ 種類の記号から $n$ 回選んで送る列の情報の量を $H=n\log s=\log s^n$ と定めた(Har28 p. 540 の式 (9)、(10))。この量は帯域幅と時間の積に比例すると論じている(Har28 p. 535 の要旨)。雑音は含まれていない。
thm-sh-main はこれを次のように読める。1 秒に $2W$ 個の標本を送り、雑音のもとで見分けられる振幅の段階が $s=\sqrt{1+P/N}$ 個程度あるとすると、$2W\log\sqrt{1+P/N}=W\log(1+P/N)$ となる。ただし、これは式の形を説明する読み方で、thm-sh-discrete の証明は振幅の段階を区切る符号ではなく、長い列で $\mathbb R^n$ の点を選ぶ符号を使っている。
thm-sh-discrete の等式 $C(P,N)=\frac12\log(1+P/N)$ について、仮定を 1 つずつ外した反例を挙げる。
| 外す仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 雑音が時刻ごとに独立 | 全時刻で同じ雑音 $Z_i=Z_1\sim N(0,N)$ | 容量の式(どの $R$ も達成可能) |
| 電力の制約 | 制約を課さない | 容量の式(どの $R$ も達成可能) |
| 誤りの確率が $0$ に近づけばよい | 誤りを全く許さない | 容量の式(全く誤らない符号は $M=1$ に限り、容量は $0$) |
1 行目。 $n\ge2$ とし、$c_{m,1}:=0$、$c_{m,2}:=\sqrt{nP}\,(m-1)/M$、他の成分を $0$ とする($\|c_m\|^2\le nP$)。受信者は $Z_1=y_1$ を知り、$y_2-y_1=c_{m,2}$ から $m$ を誤りなく求める。$M$ はいくらでも大きくとれる。
2 行目。 $c_m:=(L(m-1),0,\dots,0)$ とし、$y_1$ に最も近い $L(m-1)$ を選ぶと、誤りの確率は $P(|Z_1|\ge L/2)$ 以下である。$M:=\lceil2^{nR}\rceil$ に対し $L$ を十分大きくとれば、誤りの確率はいくらでも小さい。
3 行目。 $M\ge2$ とする。復号が誤らないには、各 $m$ で $P(c_m+Z^n\notin g^{-1}(m))=0$ が要る。$Z^n$ の密度は至るところ正なので、$g^{-1}(m)$ の補集合は Lebesgue 測度 $0$ である。$g^{-1}(1)$ と $g^{-1}(2)$ は交わらないので、$g^{-1}(1)$ は $g^{-1}(2)$ の補集合に含まれ測度 $0$ となり、矛盾する。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する