Shannonの通信路符号化定理(Shannon's channel coding theorem)とは、入出力が有限で雑音が回ごとに独立な(無記憶な)通信路について、入力と出力の相互情報量の最大値である通信路容量 $C$ を境に、$C$ 未満の速さなら長い符号で誤りの確率をいくらでも小さくでき、$C$ を超える速さではどの符号でも正しく届く確率が 0 に近づくことを述べる定理である。たとえば各ビットが確率 0.1 で反転する通信路の容量は約 0.531 bit で、反復のように速さを 0 に近づけなくても誤りを減らせる。2 値対称通信路では、無作為に選んだ符号の平均を評価する達成の証明と、出力の個数を数える強い逆の証明が初等的に書ける。容量の計算は通信の設計の基準になる。
前提知識: エントロピー, 相互情報量, 情報理論, Chebyshevの不等式
0 と 1 の列を、各ビットが確率 $0.1$ で反転する通信路で送るとする。同じビットを 3 回送って多数決で読めば、誤りの確率は $0.1$ から $0.028$ に下がるが、1 回の送信で運べる情報は $\frac13$ bit に減る。誤りをさらに小さくしようと反復を増やせば、運べる情報は $0$ に近づくように見える。Shannon の通信路符号化定理(Shannon's channel coding theorem)は、これが誤りであることを示す。この通信路では、1 回あたり約 $0.531$ bit より小さい速さなら、長い符号を使えば誤りの確率をいくらでも小さくでき、それより大きい速さではどう工夫しても正しく届く確率が $0$ に近づく。境目の数 $0.531$ が通信路容量であり、入力と出力の相互情報量の最大値として計算できる。
この記事では、通信路・符号・速さ・誤りの確率・通信路容量を定義して定理を述べ、容量の計算の公式と手順をまとめる。中心の証明は 2 値対称通信路の場合で、容量未満の速さが達成できること(無作為に選んだ符号の平均を評価する方法)と、容量を超える速さでは正しく届く確率が $0$ に近づくこと(強い逆)を、どちらも完全に示す。一般の通信路の場合の証明は文献の所在を示す。
図: 2 値対称通信路の容量 C(ε)=1−h₂(ε) を、反転の確率 ε を横軸、速さ(bit)を縦軸にとって描いた曲線。ε=0 と 1 で 1、ε=0.5 で 0 になる下に凸の曲線で、ε=0.1 の点に約 0.531 と注記がある。高さ 4/7 の破線(Hamming(7,4) 符号の速さ)と高さ 1/3 の破線(3 回反復の速さ)が引かれ、曲線の下が塗られている。
以下、$\log$ は自然対数(単位 nat)で、$\log2$ で割ると bit になる。$h(t):=-t\log t-(1-t)\log(1-t)$($0\le t\le1$、$0\log0:=0$)とおく。$h$ は $[0,\frac12]$ で増加し、$h(\frac12)=\log2$ である。2 つの列 $u,v\in\{0,1\}^n$ の Hamming 距離 $d(u,v)$ を、成分が異なる位置の個数とする。
有限集合 $\mathcal X$(入力)・$\mathcal Y$(出力)と、$W(y\mid x)\ge0$、$\sum_yW(y\mid x)=1$ を満たす数の族 $W$ を通信路という。通信路を $n$ 回使うとき、入力の列 $x^n=(x_1,\dots,x_n)$ に対して出力の列 $y^n$ が確率
$$
W^n(y^n\mid x^n)=\prod_{i=1}^nW(y_i\mid x_i)
$$
で出るとき、通信路は 無記憶 であるという。$\mathcal X=\mathcal Y=\{0,1\}$、$W(y\mid x)=1-\varepsilon$($y=x$)、$W(y\mid x)=\varepsilon$($y\ne x$)の通信路を 2 値対称通信路(binary symmetric channel、BSC。2元対称通信路)といい、$\mathrm{BSC}(\varepsilon)$ と書く。
$\mathrm{BSC}(\varepsilon)$ を $n$ 回使うことは、$Z_1,\dots,Z_n$ を互いに独立で $P(Z_i=1)=\varepsilon$ の確率変数とし、$Y_i:=X_i+Z_i\bmod2$ とすることと同じである。とくに $W^n(y^n\mid x^n)=\varepsilon^{d}(1-\varepsilon)^{n-d}$($d=d(x^n,y^n)$)であり、送った列からの距離 $d(X^n,Y^n)$ は二項分布 $\mathrm{Bin}(n,\varepsilon)$ に従う(二項分布)。
長さ $n$、メッセージ $M$ 個の 符号 とは、符号化の写像 $F\colon\{1,\dots,M\}\to\mathcal X^n$ と復号の写像 $g\colon\mathcal Y^n\to\{1,\dots,M\}$ の組である。$x_m:=F(m)$ を 符号語 という。
入力 $X$ の分布を $p$ とし、$P(X=x,Y=y)=p(x)W(y\mid x)$ で出力 $Y$ を定める。
$$
C:=\max_pI(X;Y)
$$
を通信路 $W$ の 通信路容量 という。速さ $R$ が 達成できる とは、任意の $\eta>0$ について、十分大きいすべての $n$ で、長さ $n$、メッセージ $M\ge e^{nR}$ 個、$P_{\max}\le\eta$ の符号があることをいう。
$I(X;Y)$ は $p$ の連続関数で、確率分布の全体は有界閉集合なので、最大値はある(情報理論 の定義「通信路と通信路容量」と同じ)。
使える条件:
入力・出力が有限集合の無記憶な通信路 $W$ の容量を $C$ とする。
この記事では、一般の通信路についての 1 と 2 は証明しない。容量が $\max_pI(X;Y)$ に等しいという形で 1 と「$R>C$ なら $\bar P_e$ は $0$ に近づかない」を合わせた主張は PW25 Theorem 19.9(p. 377。平均の誤りの確率で定めた容量についての定理で、最大の誤りの確率で定めても同じ値になることは同書 Corollary 19.5、p. 375)、2 は同書 Theorem 22.1(p. 422、強い逆)にある。2 の弱い形は 情報理論 の定理「通信路符号化定理の逆」で Fano の不等式から証明している。Mac03 §9.6(p. 152)にも言明があり、証明は同書 §10.1(p. 162)以降にある。下の 2 つの節では、2 値対称通信路について 1 と 2 を完全に証明する。
1 は「容量未満なら、長い符号でほとんど誤りなく送れる」、2 は「容量を超えると、どんな符号でもほとんど必ず誤る」ことを述べる。容量 $C$ は、符号を探す組合せの問題の答えを、1 回分の確率分布についての最大化という計算できる量で与える。
| 通信路 | 容量 $C$(nat) | 条件 | 根拠 |
|---|---|---|---|
| 雑音のない $m$ 値($W(y\mid x)=1$ iff $y=x$) | $\log m$ | $m\ge1$ | prop-cct-symmetric |
| $\mathrm{BSC}(\varepsilon)$ | $\log2-h(\varepsilon)$ | $0\le\varepsilon\le1$ | prop-cct-symmetric |
| 2 値消失通信路(確率 $\alpha$ で記号 $?$ に変わる) | $(1-\alpha)\log2$ | $0\le\alpha\le1$ | ex-cct-bec |
| 雑音のあるタイプライター($x\mapsto x$ か $x+1\bmod m$ が確率 $\frac12$ ずつ) | $\log\frac m2$ | $m\ge2$ | ex-cct-typewriter |
| 対称な通信路 | $\log\lvert\mathcal Y\rvert-H(\text{行})$ | prop-cct-symmetric の条件 | prop-cct-symmetric |
| 無記憶な通信路を $n$ 回 | $nC$ 以下($I(X^n;Y^n)\le nC$) | 無記憶 | 情報理論 の定理「通信路符号化定理の逆」の証明の段 4 |
行列 $(W(y\mid x))_{x,y}$ の各行が同じ数の組 $(r_1,\dots,r_k)$($k=\lvert\mathcal Y\rvert$)の並べ替えで、各列の和 $\sum_xW(y\mid x)$ が $y$ によらないとする。このとき $C=\log k-H(r)$ であり、入力の一様分布で達成される。ここで $H(r)=-\sum_jr_j\log r_j$ である。
$X=x$ のもとで $Y$ の分布は $(r_j)$ の並べ替えなので $H(Y\mid X=x)=H(r)$、よって $H(Y\mid X)=H(r)$ で、$I(X;Y)=H(Y)-H(r)\le\log k-H(r)$ である(エントロピー の定理「エントロピーの範囲」)。入力が一様なら $P(Y=y)=\frac1{\lvert\mathcal X\rvert}\sum_xW(y\mid x)$ は $y$ によらず、$Y$ は一様分布で $H(Y)=\log k$ となり、等号が成り立つ。雑音のない $m$ 値の通信路は $r=(1,0,\dots,0)$、$\mathrm{BSC}(\varepsilon)$ は $r=(1-\varepsilon,\varepsilon)$ の場合である。$\square$
$V(n,\rho):=\#\{v\in\{0,1\}^n\mid d(u,v)\le\rho\}=\sum_{k=0}^{\rho}\binom nk$ を、半径 $\rho$ の Hamming 球の要素の個数とする(中心 $u$ によらない)。
$0\le\rho\le\frac n2$ を満たす整数 $\rho$ について $V(n,\rho)\le e^{nh(\rho/n)}$ である。
$\lambda:=\rho/n\le\frac12$ とする。$\lambda=0$ なら $V=1=e^0$ である。$0< \lambda\le\frac12$ なら $\frac\lambda{1-\lambda}\le1$ なので、$k\le\rho=n\lambda$ について $\lambda^k(1-\lambda)^{n-k}=(1-\lambda)^n\bigl(\frac\lambda{1-\lambda}\bigr)^k\ge(1-\lambda)^n\bigl(\frac\lambda{1-\lambda}\bigr)^{n\lambda}=e^{-nh(\lambda)}$ である。二項定理により $1=\sum_{k=0}^n\binom nk\lambda^k(1-\lambda)^{n-k}\ge\sum_{k\le\rho}\binom nk\lambda^k(1-\lambda)^{n-k}\ge V(n,\rho)e^{-nh(\lambda)}$ である。$\square$
メッセージ $2M$ 個の符号の平均の誤りの確率が $\eta$ 以下なら、その符号語のうち $M$ 個を残し、復号を少し変えて、メッセージ $M$ 個・最大の誤りの確率 $2\eta$ 以下の符号が作れる。
$e_m>2\eta$ となる $m$ の個数を $k$ とすると、$k\cdot2\eta< \sum_me_m\le2M\eta$($k\ge1$ のとき)から $k< M$ なので、$e_m\le2\eta$ となる $m$ は $M$ 個以上ある。そのうち $M$ 個からなる集合 $S$ を残す。復号は、$g(y^n)\in S$ ならそのまま、そうでなければ $S$ の決まった元を返すように変える。$m\in S$ について「$g(y^n)=m$」となる $y^n$ では新しい復号も $m$ を返すので、$m$ の誤りの確率は増えない。$\square$
$0\le\varepsilon< \frac12$、$C=\log2-h(\varepsilon)$、$0< R< C$ とする。$\delta>0$ を $\varepsilon+\delta< \frac12$ かつ
$$
\gamma:=\log2-h(\varepsilon+\delta)-R>0
$$
となるようにとる。このとき各 $n\ge1$ について、$\mathrm{BSC}(\varepsilon)$ の長さ $n$、メッセージ $M_n:=\lceil e^{nR}\rceil$ 個の符号で
$$
P_{\max}\le2\Bigl(\frac{\varepsilon(1-\varepsilon)}{n\delta^2}+3e^{-n\gamma}\Bigr)
$$
を満たすものがある。右辺は $n\to\infty$ で $0$ に近づくので、速さ $R$ は達成できる。
$h$ は連続で $\log2-h(\varepsilon)-R=C-R>0$ なので、このような $\delta$ はある。
$n$ を固定し、$M':=2M_n$、$\rho:=\lfloor n(\varepsilon+\delta)\rfloor$ とおく。
1. 符号を無作為に選ぶ。 $X_1,\dots,X_{M'}$ を、$\{0,1\}^n$ の一様分布に従う互いに独立な確率変数とし、これを符号語とする(一致してもよい)。復号は、受け取った $y$ から距離 $\rho$ 以内にある符号語の番号が $m$ ただ 1 つなら $m$ を返し、そうでなければ $1$ を返す。符号語の組を決めるごとに 1 つの符号が決まり、その平均の誤りの確率を $\bar P_e$ と書く。$\bar P_e$ の、符号語の選び方についての期待値 $E[\bar P_e]$ を上から評価する。
2. 誤りの原因を 2 つに分ける。 メッセージ $m$ を送り、雑音を $Z=(Z_1,\dots,Z_n)$ とし、$Y=X_m+Z$ を受け取る。$Z$ は符号語と独立である。正しく復号されないなら、次のどちらかが起こる。
3. $A$ の確率。 $d(Y,X_m)$ は $Z$ の $1$ の個数で、$\mathrm{Bin}(n,\varepsilon)$ に従い、平均 $n\varepsilon$、分散 $n\varepsilon(1-\varepsilon)$ である。整数 $N$ について $N>\lfloor x\rfloor$ と $N>x$ は同値なので、$A$ は $d(Y,X_m)-n\varepsilon>n\delta$ と同じである。Chebyshevの不等式 により
$$
P(A)\le\frac{n\varepsilon(1-\varepsilon)}{(n\delta)^2}=\frac{\varepsilon(1-\varepsilon)}{n\delta^2}
$$
である。
4. $B_{m'}$ の確率。 $Y=X_m+Z$ は $(X_m,Z)$ だけで決まり、$X_{m'}$ はそれと独立で一様分布に従う。$Y=y$ のもとで $d(y,X_{m'})\le\rho$ となる確率は $V(n,\rho)/2^n$ で、$y$ によらない。$\rho/n\le\varepsilon+\delta< \frac12$ と $h$ が $[0,\frac12]$ で増加することから、lem-cct-ball により
$$
P(B_{m'})=\frac{V(n,\rho)}{2^n}\le e^{nh(\rho/n)-n\log2}\le e^{-n(\log2-h(\varepsilon+\delta))}
$$
である。$M'-1=2M_n-1\le2(e^{nR}+1)-1\le3e^{nR}$ なので
$$
\sum_{m'\ne m}P(B_{m'})\le3e^{nR}e^{-n(\log2-h(\varepsilon+\delta))}=3e^{-n\gamma}
$$
である。
5. 符号を 1 つ選ぶ。 2〜4 を $m$ について平均すると $E[\bar P_e]\le\eta_n:=\frac{\varepsilon(1-\varepsilon)}{n\delta^2}+3e^{-n\gamma}$ である。期待値が $\eta_n$ 以下なので、$\bar P_e\le\eta_n$ となる符号語の組が少なくとも 1 つある。この符号はメッセージ $M'=2M_n$ 個なので、lem-cct-expurgate により、メッセージ $M_n$ 個で $P_{\max}\le2\eta_n$ の符号が得られる。$M_n\ge e^{nR}$ であり、$\eta_n\to0$ なので、任意の $\eta>0$ について十分大きい $n$ で $P_{\max}\le\eta$ となる。$\square$
証明の要点は、符号を 1 つずつ調べる代わりに、無作為に選んだ符号の誤りの期待値を計算したことである。期待値が小さければ、良い符号が少なくとも 1 つある。証明は良い符号の存在を示すだけで、それを効率よく作る方法は与えない。
$0< \varepsilon< \frac12$、$C=\log2-h(\varepsilon)$、$a:=\log\frac{1-\varepsilon}\varepsilon>0$ とする。$\mathrm{BSC}(\varepsilon)$ の長さ $n$、メッセージ $M$ 個のどの符号についても、$0< \delta< \varepsilon$ ごとに
$$
P_c\le\frac{\varepsilon(1-\varepsilon)}{n\delta^2}+\frac{2^n}Me^{-n(h(\varepsilon)-\delta a)}
$$
である。とくに $R>C$ とし、$M\ge e^{nR}$ とする。$\delta:=\frac12\min\{\varepsilon,\frac{R-C}a\}$ とおくと
$$
P_c\le\frac{\varepsilon(1-\varepsilon)}{n\delta^2}+e^{-n(R-C-\delta a)}
$$
で、$R-C-\delta a\ge\frac{R-C}2>0$ なので、$P_c\to0$($n\to\infty$)である。
1. 復号の領域。 $D_m:=\{y\mid g(y)=m\}$ とおくと、$D_1,\dots,D_M$ は互いに交わらず、和は $\{0,1\}^n$ である。メッセージ $m$ が正しく復号される確率は
$$
1-e_m=\sum_{y\in D_m}\varepsilon^{d(y,x_m)}(1-\varepsilon)^{n-d(y,x_m)}
$$
である。
2. 近い出力と遠い出力に分ける。 $r:=n(\varepsilon-\delta)$ とおく(整数でなくてよい)。$D_m$ の元のうち $d(y,x_m)< r$ のものについての和は、$\{0,1\}^n$ 全体の $d(y,x_m)< r$ のものについての和以下で、それは $\mathrm{Bin}(n,\varepsilon)$ に従う $N$ について $P(N< r)$ である。$N< r$ なら $\lvert N-n\varepsilon\rvert>n\delta$ なので、Chebyshevの不等式 により $P(N< r)\le\frac{\varepsilon(1-\varepsilon)}{n\delta^2}$ である。
3. 遠い出力 1 つの確率は小さい。 実数 $t$ の関数 $\varepsilon^t(1-\varepsilon)^{n-t}=(1-\varepsilon)^n\bigl(\frac\varepsilon{1-\varepsilon}\bigr)^t$ は、$\frac\varepsilon{1-\varepsilon}< 1$ なので減少する。よって $d(y,x_m)\ge r$ なら
$$
\varepsilon^{d(y,x_m)}(1-\varepsilon)^{n-d(y,x_m)}\le\varepsilon^r(1-\varepsilon)^{n-r}=\exp\bigl(n[(\varepsilon-\delta)\log\varepsilon+(1-\varepsilon+\delta)\log(1-\varepsilon)]\bigr)=e^{-n(h(\varepsilon)-\delta a)}
$$
である。$D_m$ の遠い出力についての和は $\#D_m\cdot e^{-n(h(\varepsilon)-\delta a)}$ 以下である。
4. 平均する。 2・3 から $1-e_m\le\frac{\varepsilon(1-\varepsilon)}{n\delta^2}+\#D_m\,e^{-n(h(\varepsilon)-\delta a)}$ である。$m$ について平均し、$\sum_m\#D_m=2^n$ を使うと第 1 式を得る。
5. 速さが容量を超えるとき。 $M\ge e^{nR}$ なら $\frac{2^n}M\le e^{n(\log2-R)}$ なので、第 2 項は $e^{n(\log2-R-h(\varepsilon)+\delta a)}=e^{-n(R-C-\delta a)}$ 以下である。$\delta\le\frac{R-C}{2a}$ から $\delta a\le\frac{R-C}2$ であり、$\delta\le\frac\varepsilon2< \varepsilon$ なので第 1 式が使える。$\square$
thm-cct-bsc-achieve と thm-cct-bsc-strong を合わせると、$0< \varepsilon< \frac12$ の $\mathrm{BSC}(\varepsilon)$ では、メッセージ $e^{nR}$ 個以上の符号で達成できる最小の誤りの確率は、$R< C$ なら $0$ に、$R>C$ なら $1$ に近づく。容量 $C$ はこの急な切り替わりの位置である。$\varepsilon=\frac12$ なら出力は入力と独立で、どの符号でも $P_c=\frac1M$ であり、$C=0$ と合う。$\frac12< \varepsilon\le1$ なら、受け取った列の 0 と 1 を入れ替えると $\mathrm{BSC}(1-\varepsilon)$ になり、容量は同じ $\log2-h(\varepsilon)$ である。
問い:$\mathrm{BSC}(0.11)$ で 1 回あたり何 bit まで送れるか。
使う公式:prop-cct-symmetric($C=\log2-h(\varepsilon)$)。
答え:$h(0.11)\approx0.346515$ nat なので $C\approx0.346632$ nat、すなわち $C\approx0.500084$ bit。1 回あたりほぼ $\frac12$ bit であり、たとえば 1000 bit のデータは、長い符号を使えば約 2000 回の送信で、誤りの確率を小さくして送れる。
問い:$\mathrm{BSC}(0.1)$ で、3 回反復(多数決で復号)、5 回反復、Hamming(7,4) 符号(4 bit を 7 bit にして 1 か所の誤りを直す)の誤りの確率と速さを求め、容量と比べよ。
使う公式:独立な反転の個数が二項分布に従うこと。
答え:3 回反復は誤り $3\varepsilon^2(1-\varepsilon)+\varepsilon^3=0.028$、速さ $\frac13$ bit。5 回反復は誤り $0.00856$、速さ $\frac15$ bit。Hamming(7,4) は誤り(7 bit のうち 2 か所以上が反転する確率)$1-(0.9)^7-7(0.1)(0.9)^6\approx0.149694$、速さ $\frac47\approx0.571$ bit。容量は $C\approx0.531$ bit。
反復符号は速さを $\frac1k$ に下げることで誤りを減らしており、誤りを $0$ に近づけると速さも $0$ に近づく。thm-cct-bsc-achieve によれば、速さを $0.5$ bit に保ったままでも、符号長を伸ばせば誤りを $0$ に近づけられる。Hamming(7,4) の速さ $\frac47$ は容量を超えているので、thm-cct-bsc-strong により、速さ $\frac47$ を保ったまま符号長を伸ばすと、どんな符号でも誤りの確率は $1$ に近づく。長さ $7$ で誤りが約 $0.15$ にとどまっていることとは矛盾しない(定理は $n\to\infty$ の主張)。Hamming 符号の定義と復号は Hamming符号 にある。
問い:入力 $\{0,1\}$ が確率 $1-\alpha$ でそのまま、確率 $\alpha$ で消失記号 $?$ になって届く通信路の容量を求めよ。$\alpha=0.2$ では何 bit か。
使う公式:$I(X;Y)=H(X)-H(X\mid Y)$。
答え:$C=(1-\alpha)\log2$。$\alpha=0.2$ では $0.8$ bit。
$Y\in\{0,1\}$ なら $X=Y$ に決まるので $H(X\mid Y=y)=0$。$Y=?$ となる事象は $X$ と独立に確率 $\alpha$ で起こるので、$Y=?$ のもとで $X$ の分布はもとのままで $H(X\mid Y=?)=H(X)$。よって $H(X\mid Y)=\alpha H(X)$、$I(X;Y)=(1-\alpha)H(X)\le(1-\alpha)\log2$ で、一様な入力で等号。失われる割合 $\alpha$ の分だけ容量が減る、という直観どおりの値である。
問い:入力・出力が $\{0,1,2,3\}$ で、$x$ が確率 $\frac12$ ずつ $x$ か $x+1\bmod4$ になる通信路の容量と、容量を達成する符号を求めよ。
使う公式:prop-cct-symmetric(行は $(\frac12,\frac12,0,0)$ の並べ替え、各列の和は $1$)。
答え:$C=\log4-\log2=\log2$、すなわち $1$ bit。入力を $\{0,2\}$ に限ると出力は $\{0,1\}$ と $\{2,3\}$ に分かれ、1 回の送信で 1 bit を誤りなく送れる。
この例では長さ $1$ の符号で容量に届き、誤りも $0$ である。一般には、ex-cct-repetition のように、短い符号では容量に近い速さと小さな誤りを両立できない。
問い:$\mathrm{BSC}(0.1)$ で速さ $R=0.4$ bit($\approx0.277259$ nat)、$\delta=0.02$ として thm-cct-bsc-achieve の評価を使うとき、$P_{\max}\le0.01$ を保証する $n$ はどれくらいか。また、速さ $0.7$ bit では thm-cct-bsc-strong の評価から正しく届く確率はどこまで小さいか。
使う公式:thm-cct-bsc-achieve・thm-cct-bsc-strong の評価式。
答え:$h(0.12)\approx0.529361$ bit なので $\gamma\approx0.070639$ bit $\approx0.048963$ nat $>0$。第 1 項 $\frac{2\cdot0.09}{n\cdot0.0004}=\frac{450}n$ が主で、$n\ge45{,}001$ で $P_{\max}\le0.01$ が保証される(第 2 項 $6e^{-n\gamma}$ は無視できるほど小さい)。速さ $0.7$ bit では $a=\log9\approx2.197225$、$\delta\approx0.026656$、指数 $R-C-\delta a\approx0.058569$ nat で、$n=1000$ なら $P_c\le0.1267$、$n=10^4$ なら $P_c\le0.0127$。
Chebyshev の不等式による評価は $\frac1n$ の速さでしか減らないので、保証される長さは大きい。誤りの確率が実際には $n$ について指数的に減ることは、より精密な評価で示される(補足)。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 無記憶(雑音が回ごとに独立) | $Z\sim$ 確率 $0.1$ で $1$ の 1 個の確率変数を全回に共通に使い、$Y_i:=X_i+Z\bmod2$ | 1 回ずつ見ると $\mathrm{BSC}(0.1)$ で $C\approx0.531$ bit だが、1 回目に $0$ を送って $Z=Y_1$ を知れば、残り $n-1$ 回で $2^{n-1}$ 個のメッセージを誤りなく送れる。速さ $\frac{n-1}n$ bit $>C$($n\ge3$)で $P_c=1$ となり、thm-cct-bsc-strong の結論そのものが成り立たない |
| 誤りをブロックごとに数える | 符号化せずに 1 bit ずつ送る(速さ $1$ bit $>C$) | 各 bit の誤りの割合はつねに $0.1$ で $1$ に近づかない。ブロック全体が正しい確率 $0.9^n$ は $0$ に近づくので thm-cct-bsc-strong とは矛盾しない。「速さが容量を超えると何も伝わらない」という読み方は正しくない |
| メッセージが一様 | $P(U=1)=1-\theta$ で残りは等確率、復号はつねに $1$ を返す | 速さによらず正しく届く確率は $1-\theta$ で、$0$ に近づかない。thm-cct-bsc-strong の $P_c$(一様な重みの平均)の結論が、重みを変えると成り立たない |
| $\varepsilon< \frac12$(thm-cct-bsc-achieve の復号の仕方) | $\varepsilon=0.9$ で、距離 $n(\varepsilon+\delta)$ 以内の符号語を探す復号 | 半径が $\frac n2$ を超え、lem-cct-ball が使えず、無関係な符号語もほとんど半径内に入る。通らなくなるのは証明の論法で、定理の結論は出力を反転して $\mathrm{BSC}(0.1)$ に帰着すれば成り立つ |
1 行目では、雑音が全回で同じなので、1 回目の出力がその後の雑音をすべて教えてしまう。thm-cct-bsc-strong の証明の段 3 は、出力の列の確率が積 $\varepsilon^d(1-\varepsilon)^{n-d}$ で書けることを使っており、ここが成り立たない。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 容量未満なら有限の長さで誤りを $0$ にできる | 誤りは $n\to\infty$ で $0$ に近づく。固定した $n$ では一般に $0$ にならない | thm-cct-main は極限の主張。ex-cct-typewriter は特別な例 |
| bit と nat を混ぜて $R$ と $C$ を比べる | どちらかにそろえる。$C_{\text{bit}}=C_{\text{nat}}/\log2$ | $\mathrm{BSC}(0.1)$ は $0.368$ nat $=0.531$ bit |
| 速さが容量を超える Hamming(7,4) 符号は役に立たない | 長さ $7$ では誤り約 $0.15$。容量を超えて困るのは同じ速さで長さを伸ばすとき | ex-cct-repetition |
| 証明の無作為な符号がそのまま実用になる | 証明は良い符号の存在を示すだけで、復号は全探索になる | thm-cct-bsc-achieve の後の段落 |
| 誤りの確率が $\frac12$ を超える通信路は容量が小さい | $\mathrm{BSC}(\varepsilon)$ と $\mathrm{BSC}(1-\varepsilon)$ の容量は等しい。最悪は $\varepsilon=\frac12$ | 出力を反転すればよい |
一般の有限の無記憶な通信路では、thm-cct-bsc-achieve の「Hamming 球」の代わりに、入出力の組が同時に典型的であること(同時典型性)で復号する。入力を容量を達成する分布 $p$ に従って独立に選ぶと、正しい符号語の組は確率がほぼ $1$ で典型的になり、ほかの符号語が偶然典型的になる確率は約 $e^{-nI(X;Y)}$ になる。これが $I(X;Y)$ 未満の速さを達成できる理由で、2 値対称通信路の $\frac{V(n,\rho)}{2^n}\approx e^{-n(\log2-h(\varepsilon))}$ はその特別な場合である。誤りの確率が $n$ について指数的に $0$ や $1$ に近づく速さ(誤り指数)や、達成できる $\log M$ の $\sqrt n$ の次数までの精密化(通信路の分散)は PW25 第 22 章(p. 422 以降)で扱われている。
容量に近い速さで実際に復号できる符号の構成は符号理論の中心の問題であり、LDPC符号 はその代表である。通信路符号化と対になる圧縮の問題は、誤りなく圧縮する場合が Huffman符号 と エントロピー の圧縮の限界、歪みを許す場合が レート歪み理論 で扱われる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する