シャノンの通信路符号化定理

← 情報理論一覧

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：通信路容量、情報不等式とデータ処理不等式　|　次：誤り検出と訂正の基礎

要点（BLUF）

シャノンの通信路符号化定理：符号化率 $R<C$ （容量）なら、ブロック長 $n$ を伸ばすことで誤り確率を任意に0へ近づける符号が存在する。 $R>C$ では誤り確率を0にできない。
達成可能性はランダム符号化と AEP（漸近等分割性とAEP）で、逆定理は Fano の不等式で証明されます。容量は通信の鋭い閾値。
衝撃的なのは「ノイズがあっても、率を容量未満に保てばほぼ完全な通信ができる」こと。冗長性を上手に足せば、率を犠牲にせず信頼性を上げられる——反復符号のような素朴なやり方は非効率です。

1. 符号化率と定理の主張

長さ $n$ のブロックで $M$ 個のメッセージを送るとき、符号化率 は $R=\frac{\log_2 M}{n}$ bit/通信路使用。定理は2つの主張からなります。

達成可能（順定理）：任意の $R<C$ に対し、 $n\to\infty$ で最大誤り確率 $\to0$ となる符号列が存在する。
不可能（逆定理）： $R>C$ なら、どんな符号でも誤り確率は0より大きく、 $n$ を伸ばすと1に近づく（強逆定理）。

つまり $C$ は「これ未満なら必ず届く、これを超えたら必ず壊れる」という臨界速度です。

2. 達成可能性：ランダム符号化と AEP

シャノンの証明は天才的に間接的です。符号を1つ賢く設計するのではなく、符号語をランダムに $2^{nR}$ 個生成し、その平均誤り確率を評価する。受信語 $y^n$ に対し「 $y^n$ と同時典型な符号語」を探す復号を使うと、(a) 送った符号語は高確率で同時典型、(b) 別の符号語が偶然同時典型になる確率は約 $2^{-n(I(X;Y)-R)}$ 。符号語が $2^{nR}$ 個なので誤り確率は約 $2^{nR}\cdot2^{-nI}=2^{-n(I-R)}\to0$ （ $R<I\le C$ のとき）。平均が小さいので、少なくとも1つは良い符号がある——AEP（漸近等分割性とAEP）が骨格です。

3. 逆定理：Fano の不等式

「 $R>C$ では不可能」は Fano の不等式 から出ます。送信メッセージ $W$ （ $M$ 通り）を受信から推定した結果を $\hat W$ 、誤り確率 $P_e=\Pr[\hat W\ne W]$ とすると、

H(W\mid \hat W) \le H(P_e) + P_e\log_2(M-1)

「誤り確率が小さければ、受信後に残るメッセージの不確かさも小さい」。これとデータ処理不等式（情報不等式とデータ処理不等式） $I(W;\hat W)\le nC$ を組み合わせると、 $R>C$ では $P_e$ を0にできないことが導けます。Fano は「低い誤り確率は低い条件付きエントロピーを要求する」という橋渡しです。

4. コード：反復符号の率と信頼性、Fano 上界（底2, bit）

BSC（ $f=0.1$ 、容量 $C=0.531$ ）で、反復符号（多数決）が信頼性を上げる代わりに率を犠牲にすることを見て、Fano の上界も確認します。

import numpy as np
def H2(p):
    if p<=0 or p>=1: return 0.0
    return -p*np.log2(p)-(1-p)*np.log2(1-p)

f=0.1
C=1-H2(f)
print(f"BSC f={f}: 通信路容量 C=1-H(f)={C:.4f} bit/通信路使用")
print("反復符号(1ビットをn回送り多数決): 信頼性は上がるが符号化率 R=1/n は下がる")
rng=np.random.default_rng(0)
N=2_000_000
print(f"{'n(反復)':>8}{'符号化率R':>10}{'ビット誤り率':>14}")
for n in [1,3,5,7,11]:
    bits=rng.integers(0,2,size=N)
    flips=(rng.random((N,n))<f).astype(int)
    received=bits[:,None]^flips
    decoded=(received.sum(1) > n/2).astype(int)
    pe=np.mean(decoded!=bits)
    print(f"{n:>8}{1/n:>10.3f}{pe:>14.6f}")
print(f"\n反復符号は R->0 にしないと誤り->0 にできない（非効率）")
print(f"定理: R<C={C:.4f} なら R を保ったまま誤り率を0に近づける符号が存在する")
print("-"*54)
# Fano の不等式： H(W|hatW) <= H(Pe) + Pe*log2(M-1)
M=4
for Pe in [0.0,0.05,0.2]:
    bound=H2(Pe)+Pe*np.log2(M-1)
    print(f"|W|={M}, Pe={Pe}: Fano上界 H(W|hatW) <= {bound:.4f} bit")

出力：

BSC f=0.1: 通信路容量 C=1-H(f)=0.5310 bit/通信路使用
反復符号(1ビットをn回送り多数決): 信頼性は上がるが符号化率 R=1/n は下がる
   n(反復)     符号化率R        ビット誤り率
       1     1.000      0.099701
       3     0.333      0.028074
       5     0.200      0.008492
       7     0.143      0.002704
      11     0.091      0.000282

反復符号は R->0 にしないと誤り->0 にできない（非効率）
定理: R<C=0.5310 なら R を保ったまま誤り率を0に近づける符号が存在する
------------------------------------------------------
|W|=4, Pe=0.0: Fano上界 H(W|hatW) <= 0.0000 bit
|W|=4, Pe=0.05: Fano上界 H(W|hatW) <= 0.3656 bit
|W|=4, Pe=0.2: Fano上界 H(W|hatW) <= 1.0389 bit

出力の意味：反復符号は $n$ を増やすほど誤り率が $0.0997\to0.0003$ と下がりますが、その代償に符号化率が $1.0\to0.09$ と通信路使用あたりの情報がどんどん減ります——信頼性を率の犠牲で買っている。このやり方では誤りを0にするには $R\to0$ にするしかなく、容量 $0.531$ をまったく活かせません。シャノンの定理の驚きは、「 $R=0.5<C$ を保ったまま、ブロック長を伸ばせば誤り率を0に近づけられる」と保証する点です（反復ではなく賢い符号で。第5章へ）。下段の Fano 上界は、誤り確率 $P_e$ が0なら残る不確かさも0、 $P_e$ が増えると上界も緩む様子を示し、逆定理の道具立てを数値で確認できます。

5. 数式の直観的意味

通信路符号化定理は情報理論で最も反直観的な結果です。素朴には「ノイズがある以上、長く送れば誤りは累積する」と思えますが、実際は逆——冗長性を構造的に足せば、長くするほど信頼性が上がり、しかも率は容量近くに保てる。鍵は「メッセージ空間 $2^{nR}$ を、受信空間で重ならないように散りばめる」こと。容量 $C$ は受信空間が許す「区別可能なメッセージ数の対数 ÷ $n$ 」の上限です。実際に容量へ迫る符号（LDPC・ポーラ符号）は半世紀かけて見つかりました（代表的な符号の概観）。情報源符号化定理（シャノンの情報源符号化定理）と合わせ、「圧縮の限界＝エントロピー、通信の限界＝容量」という情報理論の二本柱が完成します。

⚠️ よくある誤解

「容量未満なら誤りはゼロ」ではない：有限の $n$ では誤りは残ります。「 $n\to\infty$ で任意に小さくできる」が正確。
「反復符号で十分」ではない：反復は率を犠牲にする非効率な符号。定理が約束するのは率を保ったままの信頼性で、それには構造的な符号が要ります。
「フィードバックがあれば容量を超えられる」ではない：離散無記憶通信路では、フィードバックは容量を増やしません（誤り訂正は楽になります）。
「定理は具体的な符号を与える」ではない：シャノンの証明は存在証明（ランダム符号化）。実際に作れる良い符号の発見は別問題で、第5章のテーマです。

対応シミュレーション

本文のコードで反復符号の率-信頼性トレードオフと Fano 上界を実証済み。