誤り検出と訂正の基礎

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

📎 前提：シャノンの通信路符号化定理　|　次：線形符号とハミング符号

要点（BLUF）

ハミング距離 $d(a,b)$ は2つの符号語が異なるビット数。最小距離 $d_{\min}$ は符号語ペアの最小のハミング距離で、符号の誤り耐性を一手に決めます。
検出： $d_{\min}-1$ 個までの誤りを検出できる（別の符号語に化けないから）。訂正： $\lfloor(d_{\min}-1)/2\rfloor$ 個までを最近傍復号で訂正できる。
冗長ビットを足して符号語どうしを受信空間で離すのが誤り訂正の本質。離す＝率を下げるので、率と信頼性のトレードオフ（シャノンの通信路符号化定理）がここでも効きます。

1. ハミング距離と最小距離

長さ $n$ の2つの2進ベクトル $a,b$ の ハミング距離 は、異なる成分の個数 $d(a,b)=\sum_i [a_i\ne b_i]$ 。符号 $\mathcal C$ （符号語の集合）の 最小距離 は

d_{\min} = \min_{\substack{c,c'\in\mathcal C\\ c\ne c'}} d(c,c')

最小距離が大きいほど、符号語どうしが「遠く」に配置され、ノイズで隣の符号語に飛び移りにくくなります。送信した符号語 $c$ が $t$ ビット誤って $r$ になったとき、 $d(c,r)=t$ 。これが他のどの符号語より $c$ に近ければ、最近傍復号で正しく $c$ に戻せます。

2. 検出能力と訂正能力

誤り検出： $d_{\min}-1$ 個までの誤りなら、受信語は決して別の符号語に一致しません（最も近い符号語まで $d_{\min}$ あるから）。よって「符号語でない＝誤りあり」と検出できます。

誤り訂正：各符号語を中心に半径 $t=\lfloor(d_{\min}-1)/2\rfloor$ の球（ハミング球）を描くと、これらは重なりません。 $t$ 個までの誤りなら受信語は正しい符号語の球内に留まるので、最近傍復号で一意に訂正できます。

\text{検出可能} = d_{\min}-1, \qquad \text{訂正可能} = \left\lfloor \frac{d_{\min}-1}{2}\right\rfloor

例： $d_{\min}=3$ なら2個検出・1個訂正。 $d_{\min}=4$ なら3個検出・1個訂正（検出と訂正は同時には別枠）。

graph LR
  c0["符号語 000"] -.->|"d=3"| c1["符号語 111"]
  c0 --- s0["球: 000,001,010,100 を 000 に訂正"]
  c1 --- s1["球: 111,110,101,011 を 111 に訂正"]

3. コード：最小距離と訂正能力（反復符号(3,1)）

0→000、1→111 と各ビットを3回繰り返す反復符号（ $d_{\min}=3$ ）で、全ての1ビット誤りが訂正でき、2ビット誤りは誤訂正されることを確かめます。

import numpy as np
def hamming(a,b): return int(np.sum(np.asarray(a)!=np.asarray(b)))

# 反復符号(3,1): 0->000, 1->111。最小距離 d_min=3
codewords={0:np.array([0,0,0]),1:np.array([1,1,1])}
cws=list(codewords.values())
dmin=min(hamming(cws[i],cws[j]) for i in range(len(cws)) for j in range(i+1,len(cws)))
print(f"反復符号(3,1): 符号語 000,111")
print(f"最小ハミング距離 d_min = {dmin}")
print(f"検出可能な誤り数 = d_min-1 = {dmin-1}")
print(f"訂正可能な誤り数 = floor((d_min-1)/2) = {(dmin-1)//2}")
print("-"*46)
# 最近傍復号で1ビット誤りを全パターン訂正できるか確認
ok=True
for msg,cw in codewords.items():
    for epos in range(3):
        r=cw.copy(); r[epos]^=1
        dec=min(codewords, key=lambda m: hamming(r,codewords[m]))
        if dec!=msg: ok=False
print(f"全ての1ビット誤りを訂正できるか: {ok}")
r=np.array([1,1,0])
print(f"2ビット誤り 000->110: 最近傍は {min(codewords,key=lambda m:hamming(r,codewords[m]))} (誤訂正)")

出力：

反復符号(3,1): 符号語 000,111
最小ハミング距離 d_min = 3
検出可能な誤り数 = d_min-1 = 2
訂正可能な誤り数 = floor((d_min-1)/2) = 1
----------------------------------------------
全ての1ビット誤りを訂正できるか: True
2ビット誤り 000->110: 最近傍は 1 (誤訂正)

出力の意味：反復符号(3,1)は $d_{\min}=3$ なので、2ビットまで検出・1ビット訂正できます。実際に全ての1ビット誤り（000→001,010,100 と 111→110,101,011）が正しく訂正されました。一方、000 を2ビット反転した 110 は、111 の方が近い（距離1）ため誤って1と訂正されます——訂正能力 $\lfloor(3-1)/2\rfloor=1$ を超えた誤りはお手上げ。 $d_{\min}$ が符号の耐性を一手に決めている様子がはっきり見えます。より多くの誤りに耐えるには $d_{\min}$ を上げる＝もっと冗長ビットを足す必要があり、それは率を下げます。

4. 数式の直観的意味

誤り訂正は幾何学です。 $n$ 次元の超立方体（ $2^n$ 個の頂点）に、符号語を「互いに $d_{\min}$ 以上離して」配置する。各符号語のまわりに半径 $t$ の球を描き、球が重ならないように詰める——これが 球充填。球の体積 $\sum_{i=0}^{t}\binom{n}{i}$ と符号語数 $2^k$ の積が全空間 $2^n$ を超えられない、という ハミング限界 $2^k\sum_{i=0}^t\binom{n}{i}\le2^n$ が、訂正能力と冗長度の交換条件を与えます。シャノンの定理（シャノンの通信路符号化定理）は「 $n$ を大きくすればこの詰め込みを容量近くまで効率化できる」と言っていたわけです。次のノートの線形符号は、この配置を線形代数で系統的に作る方法です。

⚠️ よくある誤解

「検出と訂正は同時にフルにできる」ではない： $d_{\min}=3$ なら「1訂正」か「2検出」のどちらか。訂正に振ると検出余力は減ります（用途で設計を選ぶ）。
「 $d_{\min}$ が大きいほど常に良い」ではない： $d_{\min}$ を上げるには冗長ビットが要り、率が下がります。通信路のノイズに見合った $d_{\min}$ を選ぶのが設計。
「最近傍復号はいつも最適」ではない：BSC のように誤りが少数ビットで一様なら最近傍（最小ハミング距離）が最尤復号と一致しますが、通信路によっては最尤≠最近傍です。
「誤り訂正と暗号は同じ」ではない：誤り訂正はノイズへの冗長性、暗号は秘匿性。目的が逆（暗号はセキュリティ分野）。

対応シミュレーション

本文のコードで $d_{\min}$ と訂正能力、1ビット訂正の全数確認を実証済み。