離散無記憶通信路

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：相互情報量　|　次：通信路容量

要点（BLUF）

離散無記憶通信路（DMC） は、入力 $x$ に対し出力 $y$ が確率 $p(y\mid x)$ で出る装置。「無記憶」＝各使用が独立（過去の入出力に依らない）。
代表例：2元対称通信路 BSC（確率 $f$ でビット反転）、2元消失通信路 BEC（確率 $e$ で「？」になり、それ以外は正しく届く）。
通信路の性能は、入力分布 $p(x)$ を与えたときの相互情報量 $I(X;Y)$ で測ります。これを最大化したのが容量（通信路容量）。

1. 通信路の定義：遷移確率

通信路は入力アルファベット $\mathcal X$ 、出力アルファベット $\mathcal Y$ 、そして 遷移確率 $p(y\mid x)$ （行列）で完全に決まります。送り手が入力分布 $p(x)$ を選ぶと、出力の分布は $p(y)=\sum_x p(x)p(y\mid x)$ 。通信路自体は $p(y\mid x)$ で固定され、送り手が変えられるのは入力分布だけ、という非対称な構図です。

2元対称通信路（BSC） は反転確率 $f$ で

p(y\mid x)=\begin{pmatrix} 1-f & f \\ f & 1-f \end{pmatrix}

0 も 1 も対称に確率 $f$ で反転します。2元消失通信路（BEC） は消失確率 $e$ で、出力は $\{0,1,?\}$ 。届けば必ず正しく、届かないとき（確率 $e$ ）だけ「？」になり、どちらのビットだったかは分かりません。

graph LR
  x0["入力 0"] -->|"1-f"| y0["出力 0"]
  x0 -->|"f"| y1["出力 1"]
  x1["入力 1"] -->|"f"| y0
  x1 -->|"1-f"| y1

2. 通信路を通した相互情報量

入力分布 $p(x)$ を与えると、 $I(X;Y)=H(Y)-H(Y\mid X)$ で「1回の使用で平均何 bit 伝わるか」が決まります。 $H(Y\mid X)=\sum_x p(x)H(p(\cdot\mid x))$ はノイズが持ち込む不確かさ。BSC なら各行のエントロピーは $H(f)$ なので $H(Y\mid X)=H(f)$ 、よって $I(X;Y)=H(Y)-H(f)$ 。出力 $Y$ をできるだけ不確かに（一様に）すると $I$ が最大になります。

3. コード：BSC と BEC の相互情報量（底2, bit）

import numpy as np
def H(p):
    p=np.asarray(p,float).ravel(); p=p[p>0]; return -np.sum(p*np.log2(p))
def MI(px, Py_x):
    # px: 入力分布, Py_x[x,y]=p(y|x)
    Pxy = Py_x*px[:,None]
    py = Pxy.sum(0)
    return H(py) - sum(px[x]*H(Py_x[x]) for x in range(len(px)))

# 2元対称通信路 BSC, ビット反転確率 f
f=0.1
BSC=np.array([[1-f,f],[f,1-f]])
print(f"BSC (f={f}):")
for px0 in [0.5,0.3,0.9]:
    px=np.array([px0,1-px0])
    print(f"  入力分布 p(0)={px0}: I(X;Y)={MI(px,BSC):.4f} bit")
print(f"  一様入力での I = 1 - H(f) = {1-H([f,1-f]):.4f} bit (理論)")
print("-"*46)
# 2元消失通信路 BEC, 消失確率 e。出力 {0,1,?}
e=0.2
BEC=np.array([[1-e,0,e],[0,1-e,e]])
for px0 in [0.5,0.3]:
    px=np.array([px0,1-px0])
    print(f"BEC (e={e}) 入力 p(0)={px0}: I(X;Y)={MI(px,BEC):.4f} bit")
print(f"  一様入力での I = 1 - e = {1-e:.4f} bit (理論)")

出力：

BSC (f=0.1):
  入力分布 p(0)=0.5: I(X;Y)=0.5310 bit
  入力分布 p(0)=0.3: I(X;Y)=0.4558 bit
  入力分布 p(0)=0.9: I(X;Y)=0.2111 bit
  一様入力での I = 1 - H(f) = 0.5310 bit (理論)
----------------------------------------------
BEC (e=0.2) 入力 p(0)=0.5: I(X;Y)=0.8000 bit
BEC (e=0.2) 入力 p(0)=0.3: I(X;Y)=0.7050 bit
  一様入力での I = 1 - e = 0.8000 bit (理論)

出力の意味：BSC では一様入力 $p(0)=0.5$ のとき $I=0.5310$ bit で最大、偏らせる（ $0.3$ や $0.9$ ）と減ります。これは理論値 $1-H(f)=1-H(0.1)=0.5310$ と一致——対称通信路は一様入力が最適。BEC でも一様入力で $I=0.8=1-e$ が最大。消失確率 $e=0.2$ なら平均して 8 割のビットが無傷で届くので、容量も $0.8$ bit という直観どおりです。これらの最大値こそが次のノートの通信路容量です。

4. 数式の直観的意味

通信路を「相互情報量を生み出す装置」と見ると、 $I(X;Y)$ は「1回使うと受信側が送信ビットについて平均何 bit 知れるか」。ノイズ $f$ が大きいほど $H(Y\mid X)=H(f)$ が大きく、伝わる情報が削られます。 $f=0.5$ （完全にランダム反転）なら $H(f)=1$ で $I=0$ ——出力が入力と無関係になり、通信路は使い物になりません。逆に $f=0$ なら $I=1$ bit/使用でロスなし。BEC は「届くか消えるか」がはっきりしている分、扱いやすく、誤り訂正（誤り検出と訂正の基礎）でも基本モデルになります。

⚠️ よくある誤解

「無記憶＝ノイズがない」ではない：無記憶は「各使用が独立」という意味で、ノイズはあります。記憶のある通信路（バースト誤り）は別モデル。
「BSC の $f$ と $1-f$ は同じ通信路」ではない： $f$ と $1-f$ は容量は同じ（対称）ですが、 $f>0.5$ なら出力を反転して読めばよく、実質 $1-f$ の通信路として使います。 $f=0.5$ が最悪。
「相互情報量は通信路だけで決まる」ではない： $I(X;Y)$ は入力分布にも依存します。通信路で固定なのは $p(y\mid x)$ 、最大化のために入力を選ぶのが容量の話。
「消失と誤りは同じ」ではない：BEC の消失は「どこが壊れたか分かる」ので訂正が楽。BSC の反転は「どこが壊れたか分からない」ので難しい。

対応シミュレーション

本文のコードで BSC・BEC の相互情報量と入力分布依存を実証済み。