Shannon–Hartleyの定理

同義語:Shannon-Hartleyの定理Shannon–Hartley theoremShannon-Hartley theorem

概要

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$ 倍の雑音密度という下限がある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 相互情報量, 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$ は自然対数とする。

離散時間の Gauss 通信路

Gauss 通信路と容量

$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)$ という。

Gauss 通信路の容量

$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 次式なので分散も有限である。

達成:Gauss 分布の乱択符号

情報密度の閾値で復号する

$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$ が送られた符号語に応じてどう分布していても使える。

$R< \frac12\log(1+P/N)$ は達成可能である(定理の「$\ge$」)

$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$ だけが閾値を超え、正しく復号される)。

  • (a) $\|\bar c_m\|^2>nP$(このときだけ $c_m\ne\bar c_m$)。
  • (b) $c_m=\bar c_m$ かつ $\imath_n(\bar c_m;\bar c_m+Z^n)\le\gamma$。
  • (c) ある $m'\ne m$ で $\imath_n(\bar c_{m'};Y^n)>\gamma$。
    符号の選び方について平均すると、各事象の確率は $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$ に近づく。

逆

Gauss 分布どうしの Kullback–Leibler ダイバージェンス

$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$

誤りの確率が $0$ に近づくなら $R\le\frac12\log(1+P/N)$(定理の「$\le$」)

電力の制約を満たす符号をとり、$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) $$
となる。

Shannon–Hartley の定理

帯域幅 $W$ に制限された入力に、電力密度が一定の白色の Gauss 雑音(帯域の中の電力 $N=N_0W$)が加わる連続時間の通信路の容量は、平均の電力の制約 $P$ のもとで $C=W\log(1+P/N)$ bit/s である(Sha48 Theorem 17)。

典拠と定式化

この形は Sha48 Theorem 17(pp. 639–640)で、PW25 §21.5 の式 (21.13)(p. 419)にも、厳密な定理の形にはしない主張として述べられている。上の計算は式の由来を示すが、証明ではない。帯域に制限された関数は有限の時間に収まらないので(標本化定理)、有限の時間で送る符号を考えるには定式化に工夫が要る(PW25 p. 419 の脚注)。定理は Shannon の翌年の論文(Sha49)でも扱われた。

帯域と電力の取引

帯域を広げたときの容量

$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 比が下がり、標本の数の増加と打ち消し合う。電力が限られると、帯域をいくら広げても容量は有限にとどまる。

Shannon の限界

速さ $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 の情報の量との比較

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$ となり、矛盾する。

関連項目

参考文献

[1]
Yury Polyanskiy; Yihong Wu, Information Theory: From Coding to Learning, Cambridge University Press, 2025, Theorem 3.12(p. 57)、Theorem 4.1(p. 67)、Theorem 20.11(p. 400)、§21.5(p. 419)
[2]
Claude E. Shannon, A mathematical theory of communication, Bell System Technical Journal 27 (1948), no. 4, pp. 623–656, 1948, Theorem 17(§24、pp. 639–640)
[3]
R. V. L. Hartley, Transmission of information, Bell System Technical Journal 7 (1928), no. 3, pp. 535–563, 1928, p. 535(要旨)、p. 540(式 (9)、(10))
[4]
Claude E. Shannon, Communication in the presence of noise, Proceedings of the IRE 37 (1949), no. 1, pp. 10–21, 1949

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する