2元対称通信路(binary symmetric channel)とは、0 か 1 を送るごとに確率 $\varepsilon$ でそれが反転し、反転が回ごとに独立に起こる通信路で、容量は $1-h_2(\varepsilon)$ bit($h_2$ は 2 値エントロピー)である。$\varepsilon< \frac12$ では最尤復号は Hamming 距離の最も近い符号語を選ぶ復号と一致し、距離 $d$ の 2 語の取り違えの確率は $(2\sqrt{\varepsilon(1-\varepsilon)})^d$ 以下で、2 つつなぐと再び 2元対称通信路になる。容量未満の速さは無作為な生成行列の線形符号で達成でき、誤りの確率は符号長について指数的に減る。
前提知識: 相互情報量, Shannonの通信路符号化定理, 線形符号
2元対称通信路(binary symmetric channel)は、0 か 1 を 1 つ送るごとに、確率 $\varepsilon$ でそれが反転し、確率 $1-\varepsilon$ でそのまま届き、反転が回ごとに独立に起こる通信路である。雑音のある通信路のうち最も単純なもので、誤り訂正符号の性能を比べる標準の模型として使われる。受け取った列は「送った列に、独立な反転の列を 2 を法として足したもの」になるので、確率の計算が Hamming 距離の計算に置き換わる。
この記事では、2元対称通信路の定義と容量の式を確かめたうえで、この通信路に固有の 3 つの事実を証明する。第 1 に、最も確からしい送信語を選ぶ復号(最尤復号)は、受け取った列に Hamming 距離が最も近い符号語を選ぶことと同じである。第 2 に、2 つの通信路をつなぐと再び 2元対称通信路になり、2元消失通信路を「劣化」させると 2元対称通信路が得られる。第 3 に(主定理)、容量未満の速さは 線形符号 で達成でき、誤りの確率は符号長について指数的に減る。容量の定義と、一般の通信路での符号化定理、容量を超える速さでの強い逆は Shannonの通信路符号化定理 で扱われている。
以下、$\log$ は自然対数とし、$h(t):=-t\log t-(1-t)\log(1-t)$($0\le t\le1$、$0\log0:=0$)、$h_2(t):=h(t)/\log2$(単位 bit)とおく。$\mathbb F_2=\{0,1\}$ を 2 元体とし、$u,v\in\mathbb F_2^n$ の Hamming 距離 $d(u,v)$ を成分の異なる位置の個数、重み $\mathrm{wt}(u):=d(u,0)$ を $1$ の個数とする。$d(u,v)=\mathrm{wt}(u+v)$ である。
$0\le\varepsilon\le1$ とする。入力と出力がともに $\{0,1\}$ で、遷移確率が
$$
W(y\mid x)=\begin{cases}1-\varepsilon&(y=x)\\ \varepsilon&(y\ne x)\end{cases}
$$
の通信路を、反転の確率 $\varepsilon$ の 2元対称通信路 といい、$\mathrm{BSC}(\varepsilon)$ と書く。$n$ 回使うときは無記憶とし、入力の列 $x\in\mathbb F_2^n$ から出力の列 $y$ が確率
$$
W^n(y\mid x)=\prod_{i=1}^nW(y_i\mid x_i)=\varepsilon^{d(x,y)}(1-\varepsilon)^{n-d(x,y)}
$$
で出るとする。
同じことを確率変数で書くと、$Z_1,\dots,Z_n$ を互いに独立で $P(Z_i=1)=\varepsilon$ の確率変数とし、入力と独立にとって
$$
Y=X+Z\qquad(\mathbb F_2^n\text{ での和})
$$
とすることである。$Z$ を 雑音の列 という。$d(X,Y)=\mathrm{wt}(Z)$ は二項分布 $\mathrm{Bin}(n,\varepsilon)$ に従う(二項分布)。
受け取った列のビットをすべて反転すれば $\mathrm{BSC}(\varepsilon)$ は $\mathrm{BSC}(1-\varepsilon)$ になるので、性能を論じるときは $0\le\varepsilon\le\frac12$ としてよい。$\varepsilon=\frac12$ では出力が入力と独立で、何も伝わらない。
2 つの反転の確率を合成する演算を
$$
a*b:=a(1-b)+(1-a)b
$$
と書く。$Z,Z'$ が独立で $P(Z=1)=a$、$P(Z'=1)=b$ なら $P(Z+Z'=1)=a*b$ であり、$1-2(a*b)=(1-2a)(1-2b)$ が成り立つ(展開すれば確かめられる)。
$\mathrm{BSC}(\varepsilon)$ の入力 $X$ を $P(X=1)=a$ とすると
$$
I(X;Y)=h(a*\varepsilon)-h(\varepsilon)
$$
である。とくに容量は $C(\varepsilon)=\log2-h(\varepsilon)$(bit では $1-h_2(\varepsilon)$)で、$\varepsilon\ne\frac12$ のとき、これを達成する入力の分布は一様分布だけである。$C$ は $[0,1]$ で凸、$[0,\frac12]$ で狭義に減少し、$C(\varepsilon)=C(1-\varepsilon)$ である。
$X=x$ のもとで $Y$ は確率 $\varepsilon$ で $x$ と異なるので $H(Y\mid X=x)=h(\varepsilon)$、よって $H(Y\mid X)=h(\varepsilon)$ である。$P(Y=1)=P(X+Z=1)=a*\varepsilon$ なので $H(Y)=h(a*\varepsilon)$ で、$I(X;Y)=H(Y)-H(Y\mid X)$ から式を得る(相互情報量)。$h$ は $t=\frac12$ でだけ最大値 $\log2$ をとる。$\varepsilon\ne\frac12$ なら $a\mapsto a*\varepsilon=\varepsilon+a(1-2\varepsilon)$ は単射な 1 次関数で、$a*\varepsilon=\frac12$ となるのは $a=\frac12$ のときだけなので、最大値 $\log2-h(\varepsilon)$ は一様分布でだけ達成される。$h$ は凹で $h(t)=h(1-t)$、$[0,\frac12]$ で狭義に増加するので、残りの性質が従う。$\square$
$\varepsilon=0.1$ では $h_2(0.1)\approx0.468996$ で、$C\approx0.531004$ bit である。
長さ $n$ の符号 $\mathcal C\subseteq\mathbb F_2^n$ の符号語の 1 つが送られ、$y$ を受け取ったとする。$W^n(y\mid c)$ を最大にする $c\in\mathcal C$ を選ぶ復号を 最尤復号、$d(y,c)$ を最小にする $c$ を選ぶ復号を 最小距離復号 という(どちらも、同点のときの選び方は固定しておく)。
$0< \varepsilon< \frac12$ とする。どの $y$ と $c,c'\in\mathcal C$ についても
$$
W^n(y\mid c)> W^n(y\mid c')\iff d(y,c)< d(y,c')
$$
である。よって最尤復号と最小距離復号は同じものである。符号語が等確率で送られるなら、これは受け取った $y$ のもとで送られた確率が最大の符号語を選ぶ復号とも一致する。
$W^n(y\mid c)=(1-\varepsilon)^n\theta^{d(y,c)}$、$\theta:=\frac\varepsilon{1-\varepsilon}$ と書ける。$0< \varepsilon< \frac12$ なので $0< \theta< 1$ で、$t\mapsto\theta^t$ は狭義に減少する。よって尤度の大小は距離の大小の逆である。等確率なら、Bayes の公式により送られた確率は $W^n(y\mid c)$ に比例するので、最後の主張も従う。$\square$
$\varepsilon>\frac12$ では $\theta>1$ となり、最尤復号は 最も遠い 符号語を選ぶ。$\varepsilon=\frac12$ ではすべての尤度が等しく、復号の規則は何も情報を使わない(GRS25 p. 122 の脚注 2 は、$\varepsilon\le\frac12$ で $\varepsilon^d(1-\varepsilon)^{n-d}$ が $d$ について減少することを注意している)。
距離が $d$ だけ離れた 2 つの符号語を取り違える確率は、次のように通信路の 1 つの数で上から抑えられる。
$0\le\varepsilon\le\frac12$、$\beta(\varepsilon):=2\sqrt{\varepsilon(1-\varepsilon)}$ とする。$c$ を送り、$d(c,c')=d\ge1$ の別の語 $c'$ について
$$
P\bigl(d(Y,c')\le d(Y,c)\bigr)\le\beta(\varepsilon)^d
$$
である。
$S$ を $c$ と $c'$ が異なる位置の集合($\lvert S\rvert=d$)とする。$S$ の外では $c,c'$ が一致するので、$d(Y,c')-d(Y,c)$ は $S$ の上の成分だけで決まり、$S$ のうち反転した位置の個数を $N$ とすると $d(Y,c)$ の $S$ の部分は $N$、$d(Y,c')$ の $S$ の部分は $d-N$ である。よって事象は $N\ge\frac d2$ と同じである。$N$ は $\mathrm{Bin}(d,\varepsilon)$ に従う。$\lambda:=\frac12\log\frac{1-\varepsilon}\varepsilon\ge0$ とおくと、$N\ge\frac d2$ のとき $e^{\lambda(2N-d)}\ge1$ なので
$$
P\Bigl(N\ge\frac d2\Bigr)\le E\bigl[e^{\lambda(2N-d)}\bigr]=\Bigl(e^{-\lambda}\bigl((1-\varepsilon)+\varepsilon e^{2\lambda}\bigr)\Bigr)^d
$$
である($N$ は独立な $d$ 個の Bernoulli 変数の和)。$e^{\lambda}=\sqrt{(1-\varepsilon)/\varepsilon}$ を代入すると括弧の中は $\sqrt{\varepsilon(1-\varepsilon)}+\sqrt{\varepsilon(1-\varepsilon)}=\beta(\varepsilon)$ となる($\varepsilon=0$ なら $N=0$ で左辺は $0$)。$\square$
$\beta(\varepsilon)$ を通信路の Bhattacharyya パラメータ という(Mac03 p. 215 の (13.24) は同じ量を、対の誤りの近似として導いている)。$\beta(0.1)=0.6$、$\beta(0.01)\approx0.199$ である。
$\mathcal C$ を 線形符号 とし、$A_w$ を重み $w$ の符号語の個数とする。$0\le\varepsilon\le\frac12$ で最小距離復号を使うと、どの符号語を送っても、復号の誤りの確率は $\sum_{w\ge1}A_w\beta(\varepsilon)^w$ 以下である(同点は誤りに数える)。
$c$ を送って誤るなら、$d(Y,c')\le d(Y,c)$ となる $c'\ne c$ がある。和の上界と prop-bsc-pairwise により、誤りの確率は $\sum_{c'\ne c}\beta^{d(c,c')}$ 以下である。$c'\mapsto c'+c$ は $\mathcal C\setminus\{c\}$ から $\mathcal C\setminus\{0\}$ への全単射で $d(c,c')=\mathrm{wt}(c'+c)$ なので、和は $\sum_{w\ge1}A_w\beta^w$ に等しい。$\square$
$\mathrm{BSC}(a)$ の出力をそのまま $\mathrm{BSC}(b)$ に入れた通信路(2 つの雑音は互いに独立)は $\mathrm{BSC}(a*b)$ である。とくに $\mathrm{BSC}(\varepsilon)$ を $m$ 個つないだ通信路は $\mathrm{BSC}(\varepsilon_m)$、$\varepsilon_m=\frac12\bigl(1-(1-2\varepsilon)^m\bigr)$ で、$0< \varepsilon< 1$ なら $m\to\infty$ で $\varepsilon_m\to\frac12$、容量は $0$ に近づく。
出力は $X+Z+Z'$ で、$Z+Z'$ は入力と独立、$P(Z+Z'=1)=a*b$ である。$m$ 個では帰納法で $1-2\varepsilon_m=(1-2\varepsilon)^m$ であり、$\lvert1-2\varepsilon\rvert< 1$ から $\varepsilon_m\to\frac12$ となる。$C$ は連続で $C(\frac12)=0$ である。$\square$
$\mathrm{BSC}(0.1)$ を 2 つつなぐと $\mathrm{BSC}(0.18)$ で、容量は $0.531$ bit から $0.320$ bit に下がる。中継のたびに 0 と 1 を判定し直して送るだけでは、容量は回数とともに急速に失われる。
通信路 $W'$ が $W$ の 劣化 であるとは、$W$ の出力にさらに別の通信路 $V$ を施したものが $W'$ になる($W'(t\mid x)=\sum_yV(t\mid y)W(y\mid x)$)ことをいう(PW25 Definition 33.15、p. 646)。このとき、どの入力の分布でも、$W'$ の出力を $T$ とすると $X\to Y\to T$ は Markov 連鎖なので、相互情報量 のデータ処理不等式により $I(X;T)\le I(X;Y)$ で、$W'$ の容量は $W$ の容量以下である。
2元消失通信路 $\mathrm{BEC}(\alpha)$ は、入力 $\{0,1\}$ が確率 $1-\alpha$ でそのまま、確率 $\alpha$ で消失記号 $?$ になって届く通信路で、容量は $(1-\alpha)\log2$ である(Shannonの通信路符号化定理 の例「2 値消失通信路」)。
$0\le\varepsilon\le\frac12$ とする。$\mathrm{BEC}(2\varepsilon)$ の出力のうち $?$ を、独立な一様なビットに置き換えた通信路は $\mathrm{BSC}(\varepsilon)$ である。とくに
$$
\log2-h(\varepsilon)\le(1-2\varepsilon)\log2,\qquad\text{すなわち}\quad h_2(\varepsilon)\ge2\varepsilon
$$
であり、等号は $\varepsilon\in\{0,\frac12\}$ のときに限る。
入力 $x$ のとき、確率 $1-2\varepsilon$ で $x$ がそのまま届き、確率 $2\varepsilon$ で $?$ になってから一様なビットに替わる。後者のうち半分は $x$ に、半分は $x+1$ になるので、出力が $x$ と異なる確率は $2\varepsilon\cdot\frac12=\varepsilon$ で、雑音は回ごとに独立である。よって $\mathrm{BSC}(\varepsilon)$ は $\mathrm{BEC}(2\varepsilon)$ の劣化であり、容量の不等式が従う。等号の条件は、$h_2$ が $[0,\frac12]$ で狭義に凹で、$h_2(0)=0$、$h_2(\frac12)=1$ なので、弦 $2\varepsilon$ と端点でだけ一致することによる。$\square$
Shannonの通信路符号化定理 は、符号語を互いに独立に一様に選ぶ無作為な符号で、容量未満の速さが達成できることを $\mathrm{BSC}$ について示している。そこでは平均の誤りの確率を評価したあと、悪い符号語を捨てて最大の誤りの確率に移る(同じ主張は GRS25 Theorem 6.3.1、p. 119 にもある)。線形符号に限っても容量に届くこと、しかも捨てる操作が不要で、誤りが指数的に減ることを示す(GRS25 Exercise 6.4、p. 129 は、線形符号で容量を達成することの証明を演習として求めている)。
$k\times n$ 行列 $G$ を生成行列とする符号 $\{uG\mid u\in\mathbb F_2^k\}$ で、メッセージ $u\in\mathbb F_2^k$ を $uG$ に符号化する。整数 $\rho\ge0$ を固定し、半径 $\rho$ の限定距離復号 を次で定める:受け取った $y$ から距離 $\rho$ 以内にある $uG$ の $u$ がただ 1 つならそれを返し、そうでなければ「失敗」を返す。失敗は誤りに数える。$V(n,\rho):=\sum_{j=0}^{\rho}\binom nj$ を半径 $\rho$ の Hamming 球の点の個数、$D(s\Vert t):=s\log\frac st+(1-s)\log\frac{1-s}{1-t}$ を 2 値分布の Kullback–Leibler情報量 とする。
$0< \varepsilon< s< 1$ とし、$N$ が $\mathrm{Bin}(n,\varepsilon)$ に従うとき $P(N\ge ns)\le e^{-nD(s\Vert\varepsilon)}$ である。
$\lambda>0$ について、Markovの不等式 と独立性から
$$
P(N\ge ns)\le e^{-\lambda ns}E[e^{\lambda N}]=\bigl(e^{-\lambda s}(1-\varepsilon+\varepsilon e^\lambda)\bigr)^n
$$
である。$e^\lambda:=\frac{s(1-\varepsilon)}{\varepsilon(1-s)}>1$ とおくと $1-\varepsilon+\varepsilon e^\lambda=\frac{1-\varepsilon}{1-s}$、$e^{-\lambda s}=\bigl(\frac\varepsilon s\bigr)^s\bigl(\frac{1-s}{1-\varepsilon}\bigr)^s$ なので、括弧の中は
$$
\Bigl(\frac\varepsilon s\Bigr)^s\Bigl(\frac{1-\varepsilon}{1-s}\Bigr)^{1-s}=e^{-D(s\Vert\varepsilon)}
$$
に等しい。$\square$
$0\le\varepsilon< \frac12$ とし、$\delta>0$ を $\varepsilon+\delta< \frac12$ となるようにとる。$\rho:=\lfloor n(\varepsilon+\delta)\rfloor$ とおく。このとき各 $n\ge1$、$k\ge1$ について $k\times n$ 行列 $G$ で、半径 $\rho$ の限定距離復号を使うと、どの メッセージ $u\in\mathbb F_2^k$ についても誤りの確率が
$$
P_e:=e^{-nD(\varepsilon+\delta\Vert\varepsilon)}+2^{\,k-n(1-h_2(\varepsilon+\delta))}
$$
以下になるものがある($\varepsilon=0$ では第 1 項を $0$ とする)。$P_e< 1$ なら、このような $G$ では $u\mapsto uG$ は単射で、符号語はちょうど $2^k$ 個ある。
とくに $0< R< 1-h_2(\varepsilon)$ なら、$1-h_2(\varepsilon+\delta)>R$ となる $\delta$ をとり $k:=\lceil nR\rceil$ とおくと、速さ $\frac kn\ge R$ bit の線形符号で、最大の誤りの確率が
$$
e^{-nD(\varepsilon+\delta\Vert\varepsilon)}+2\cdot2^{-n(1-h_2(\varepsilon+\delta)-R)}
$$
以下のものがあり、これは $n$ について指数的に $0$ に近づく。
1. 誤りはメッセージによらない。 $G$ を固定し、$u$ を送って雑音 $Z$ が加わり $Y=uG+Z$ を受け取るとする。$u'$ の符号語が距離 $\rho$ 以内にあることは $\mathrm{wt}(Z+(u+u')G)\le\rho$ と同じである。$v:=u+u'$ は $u'$ が全体を動くとき $\mathbb F_2^k$ 全体を動き、$u'=u$ は $v=0$ に当たる。よって復号が $u$ を返すのは
$$
\mathrm{wt}(Z)\le\rho\quad\text{かつ}\quad\text{すべての }v\ne0\text{ で }\mathrm{wt}(Z+vG)>\rho
$$
のときに限り、この条件は $u$ を含まない。したがって、どの $u$ の誤りの確率も
$$
e(G):=P\bigl(\mathrm{wt}(Z)>\rho\ \text{または}\ \text{ある }v\ne0\text{ で }\mathrm{wt}(Z+vG)\le\rho\bigr)
$$
に等しい。
2. 生成行列を無作為に選ぶ。 $G$ の $kn$ 個の成分を、互いに独立で $\{0,1\}$ の一様分布に従うようにとり、$Z$ と独立にする。$G$ の行を $g_1,\dots,g_k$ とする。$v\ne0$ を固定し、$v_i=1$ となる $i$ をとると $vG=g_i+\sum_{j\ne i}v_jg_j$ で、$g_i$ は $\mathbb F_2^n$ 上一様で残りの行と $Z$ に独立だから、$vG$ は $Z$ と独立で $\mathbb F_2^n$ 上一様である。よって $Z=z$ のもとで $z+vG$ も一様で
$$
P\bigl(\mathrm{wt}(Z+vG)\le\rho\bigr)=\frac{V(n,\rho)}{2^n}
$$
である。和の上界により
$$
E[e(G)]\le P\bigl(\mathrm{wt}(Z)>\rho\bigr)+(2^k-1)\frac{V(n,\rho)}{2^n}
$$
で、期待値以下の値をとる $G$ が少なくとも 1 つある。
3. 2 つの項の評価。 $\mathrm{wt}(Z)$ は整数なので、$\mathrm{wt}(Z)>\rho$ は $\mathrm{wt}(Z)\ge\rho+1$ と同じで、$\rho+1>n(\varepsilon+\delta)$ だから、lem-bsc-chernoff により第 1 項は $e^{-nD(\varepsilon+\delta\Vert\varepsilon)}$ 以下である($\varepsilon=0$ なら $Z=0$ で $0$)。$\rho/n\le\varepsilon+\delta< \frac12$ と、$h$ が $[0,\frac12]$ で増加することと、Hamming 球の大きさの評価 $V(n,\rho)\le e^{nh(\rho/n)}$(Shannonの通信路符号化定理 の補題「Hamming 球の大きさ」)から、$V(n,\rho)\le2^{nh_2(\varepsilon+\delta)}$ で、第 2 項は $2^{k-n(1-h_2(\varepsilon+\delta))}$ 以下である。
4. 単射であること。 ある $v\ne0$ で $vG=0$ なら、$\mathrm{wt}(Z)\le\rho$ のときも $\mathrm{wt}(Z+vG)=\mathrm{wt}(Z)\le\rho$ なので、つねに誤りで $e(G)=1$ である。よって $e(G)\le P_e< 1$ なら $G$ の定める写像は単射である。
5. 速さ $R$ の場合。 $k=\lceil nR\rceil< nR+1$ なので $2^{k-n(1-h_2(\varepsilon+\delta))}< 2\cdot2^{-n(1-h_2(\varepsilon+\delta)-R)}$ である。$\varepsilon+\delta>\varepsilon$ なので $D(\varepsilon+\delta\Vert\varepsilon)>0$($\varepsilon>0$ のとき)で、2 つの項はどちらも指数的に $0$ に近づく。$h_2$ は連続なので、$1-h_2(\varepsilon+\delta)>R$ となる $\delta>0$ はある。$\square$
証明の段 1 が線形性の効き目である。符号が加法で閉じているので、どの符号語から見ても他の符号語の配置は同じで、平均の誤りの確率と最大の誤りの確率が一致する。また段 2 では、無作為な符号語の組の代わりに、無作為な生成行列から来る「$v\ne0$ ごとに $vG$ が一様」という性質(2 つずつ独立であることの代用)だけを使っている。符号化は行列の積で済むが、復号は $2^k$ 個の符号語との比較であり、効率よく復号できる符号の構成は別の問題である(LDPC符号、Polar符号、Reed–Muller符号)。
$\varepsilon=0.1$、$\delta=0.02$ では $D(0.12\Vert0.1)\approx0.002102$ nat、$1-h_2(0.12)\approx0.470639$ で、速さ $0.4$ bit(容量 $0.531$ bit 未満)の線形符号について、thm-bsc-linear の上界は $n=1000$ で約 $0.122$、$n=5000$ で約 $2.7\times10^{-5}$、$n=20000$ で約 $5.5\times10^{-19}$ である(第 2 項は $n=1000$ ですでに $10^{-21}$ 程度で、第 1 項が支配する)。速さを容量より大きくすると、線形符号に限らずどの符号でも正しく届く確率は $0$ に近づく(Shannonの通信路符号化定理 の定理「2 値対称通信路での強い逆」)。
Hamming符号 の Hamming(7,4) 符号の重みの分布は $A_0=1$、$A_3=A_4=7$、$A_7=1$ である。cor-bsc-union の上界は $7\beta^3+7\beta^4+\beta^7$ で、$\varepsilon=0.01$($\beta\approx0.198997$)では約 $0.0662$ である。この符号は 1 か所の誤りをすべて直し 2 か所以上では最小距離復号が誤るので、実際の誤りの確率は $1-0.99^7-7\cdot0.01\cdot0.99^6\approx0.00203$ である。$\varepsilon=0.1$($\beta=0.6$)では上界は約 $2.45$ で $1$ を超え、何も言わない(実際は約 $0.150$)。和の評価は $\beta$ が小さいときに役立つ。
$\mathrm{BSC}(0.1)$ を $m$ 個つなぐと、prop-bsc-cascade により反転の確率は $\varepsilon_m=\frac12(1-0.8^m)$ で、容量(bit)は $m=1,2,5,10,20$ で $0.531,\ 0.320,\ 0.0789,\ 0.00833,\ 0.000096$ と減る。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $\varepsilon< \frac12$(prop-bsc-ml) | $\varepsilon=0.9$、符号 $\{000,111\}$、受信 $001$ | 尤度は $000$ が $0.1^2\cdot0.9=0.009$、$111$ が $0.9^2\cdot0.1=0.081$ で、最尤復号は距離の遠い $111$ を選ぶ。最尤復号と最小距離復号が一致しない |
| 2 つの雑音が独立(prop-bsc-cascade) | 同じ雑音 $Z$ を 2 回足す:$Y=X+Z+Z$ | $Z+Z=0$ なので合成は $\mathrm{BSC}(0)$ で、$\mathrm{BSC}(0.1*0.1)=\mathrm{BSC}(0.18)$ にならない |
| 消失確率が $2\varepsilon$ 以下(prop-bsc-bec) | $\mathrm{BEC}(0.5)$ と $\mathrm{BSC}(0.1)$ | 容量は $0.5$ bit と $0.531$ bit で、$\mathrm{BSC}(0.1)$ は $\mathrm{BEC}(0.5)$ の劣化でない(劣化なら容量は $0.5$ bit 以下) |
| 速さが容量未満(thm-bsc-linear) | $\mathrm{BSC}(0.1)$ で速さ $\frac47$ bit の線形符号の列 | $\frac47>0.531$ なので、長さを伸ばすとどの符号でも正しく届く確率は $0$ に近づき、誤りの確率が $0$ に近づく線形符号はない |
| 雑音が回ごとに独立(def-bsc) | 確率 $0.1$ で $1$ になる 1 個の $Z$ を全回に共通に足す | prop-bsc-pairwise の上界が成り立たない:距離 $d$ の 2 語の取り違えの確率は $d$ によらず $0.1$ で、$d=8$ では $0.1>\beta(0.1)^8=0.6^8\approx0.0168$ となる |
最後の行では、共通の雑音 $Z=1$ のときすべての位置が反転し、長さを $n$ とすると $d(Y,c)=n$、$d(Y,c')=n-d< n$ となる。$Z=0$ なら $d(Y,c)=0< d=d(Y,c')$ なので、取り違えの確率はちょうど $0.1$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する