線形符号とハミング符号

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

📎 前提：誤り検出と訂正の基礎　|　次：代表的な符号の概観

要点（BLUF）

線形符号 $(n,k)$ は、符号語の集合が GF(2) 上の $k$ 次元線形部分空間になる符号。生成行列 $G$ （ $k\times n$ ）で $c=mG$ と符号化します。
検査行列 $H$ （ $(n-k)\times n$ ）は全符号語で $Hc^\top=0$ 。受信語 $r$ の シンドローム $s=Hr^\top$ が0なら誤りなし、非0なら誤りパターンを教えます。
ハミング(7,4)符号： $H$ の列を $1$ 〜 $7$ の2進表現にすると、シンドロームが誤り位置をそのまま指す。 $d_{\min}=3$ で全1ビット誤りを訂正（実証）。

1. 線形符号：符号語は部分空間

線形符号では、2つの符号語の（GF(2) での）和もまた符号語。だから符号は線形部分空間で、最小距離＝最小重み（非ゼロ符号語の1の個数の最小）に等しくなります（ $d(c,c')=w(c-c')$ で $c-c'$ も符号語）。 $k$ 個の情報ビット $m$ を、 $k\times n$ の 生成行列 $G$ で

c = mG \pmod 2

と符号語に写します。系統的（systematic）な形 $G=[I_k\mid P]$ なら、符号語は「元の $k$ ビット＋ $(n-k)$ 個の検査ビット」。線形性のおかげで符号化も復号も行列演算で済み、 $2^k$ 個の符号語を表で持つ必要がありません。

2. 検査行列とシンドローム復号

生成行列に対応する 検査行列 $H$ （ $(n-k)\times n$ ）は、 $GH^\top=0$ を満たすように作ります。すると全符号語で

Hc^\top = 0 \pmod 2

受信語 $r=c+e$ （ $e$ は誤りベクトル）について シンドローム を計算すると、 $s=Hr^\top=Hc^\top+He^\top=He^\top$ 。シンドロームは誤り $e$ だけに依存し、送った符号語には依りません。 $s=0$ なら（検出範囲で）誤りなし、 $s\ne0$ なら $s$ に対応する誤りパターンを引いて訂正します。

3. ハミング(7,4)符号

ハミング符号は「検査行列 $H$ の列を、 $1$ から $n$ までの2進表現にする」という美しい構成です。 $n=7,k=4$ なら $H$ は $3\times7$ で、各列が $001,010,011,100,101,110,111$ 。1ビット誤り $e$ が位置 $j$ にあると、 $He^\top=$ （ $H$ の第 $j$ 列） $=$ $j$ の2進表現。つまり シンドロームを10進で読むと、それが誤りビットの位置。位置が分かれば反転して訂正、という即時復号ができます。 $d_{\min}=3$ なので1ビット訂正可能、率は $4/7\approx0.57$ 。

4. コード：ハミング(7,4)のシンドローム復号（GF(2)）

検査行列 $H$ から符号語集合（16個）を求め、 $d_{\min}=3$ を確認、全ての1ビット誤りをシンドローム復号で訂正できることを確かめます。

import numpy as np
from itertools import product
# 検査行列 H (3x7)。各列 j の (H[0],H[1],H[2]) を2進数にすると位置1..7
H=np.array([[0,0,0,1,1,1,1],
            [0,1,1,0,0,1,1],
            [1,0,1,0,1,0,1]])
# H c^T = 0 を満たす語が符号語（2^4=16個）
cws=[np.array(b) for b in product([0,1],repeat=7) if np.all((H@np.array(b))%2==0)]
print(f"ハミング(7,4): 符号語数 = {len(cws)} (=2^4)")
dmin=min(int(np.sum((a+b)%2)) for i,a in enumerate(cws) for b in cws[i+1:])
print(f"最小距離 d_min = {dmin}  -> 1ビット訂正可能")
print("-"*46)
# 各列の2進値（=その列が表す位置）
col_val=[H[0,j]*4+H[1,j]*2+H[2,j] for j in range(7)]
ok=0; tot=0
for c in cws:
    for epos in range(7):                 # 1ビット誤りを位置epos に
        r=c.copy(); r[epos]^=1
        s=(H@r)%2
        synd=s[0]*4+s[1]*2+s[2]           # シンドロームの10進値
        loc=col_val.index(synd)           # それが指す誤り位置
        corrected=r.copy(); corrected[loc]^=1
        tot+=1; ok+= int(np.array_equal(corrected,c))
print(f"1ビット誤りの訂正成功: {ok}/{tot} = {ok/tot:.3f}")

出力：

ハミング(7,4): 符号語数 = 16 (=2^4)
最小距離 d_min = 3  -> 1ビット訂正可能
----------------------------------------------
1ビット誤りの訂正成功: 112/112 = 1.000

出力の意味： $Hc^\top=0$ を満たす語はちょうど16個（ $=2^4$ ）——これが情報4ビットを符号化した符号語です。最小距離は3なので1ビット訂正可能。そして16符号語 × 7位置 = 112通りの全ての1ビット誤りについて、シンドロームから誤り位置を特定し100%訂正成功。シンドローム $s$ を10進で読むだけで誤りビットが分かるので、表引きすら不要の超軽量な復号です。冗長は3ビットだけ（7ビット中4ビットが情報）で、これだけの訂正力が出るのが線形符号の威力です。

5. 数式の直観的意味

シンドローム復号の本質は「誤り $e$ を、 $2^n$ 通りの受信語からではなく、 $2^{n-k}$ 通りのシンドロームから引き当てる」点。 $2^{n-k}$ 個のシンドローム値それぞれに「最も軽い誤りパターン」を対応させておけば（標準アレイ）、復号は表引き1回。ハミング符号はこの表が「シンドローム＝誤り位置」という最も単純な形になる特別な符号です。線形符号は誤り検出と訂正の基礎の球充填を線形代数で実現したもので、シンドロームが誤りの「住所」を圧縮して持っているとも言えます。この枠組みはリードソロモンや LDPC（代表的な符号の概観）まで一貫します。

⚠️ よくある誤解

「シンドロームは送った符号語に依存する」ではない： $s=He^\top$ は誤りだけの関数。だからどの符号語を送ったか知らなくても復号できます。
「ハミング符号は何ビットでも訂正できる」ではない： $d_{\min}=3$ なので1ビットのみ訂正。2ビット誤りはシンドロームが別の1ビット誤りと衝突し誤訂正します。
「生成行列・検査行列は一意」ではない：行基本変形で別の等価な $G,H$ が作れます（同じ符号、別の表現）。系統的形は便利な一例。
「線形符号は非線形符号より常に良い」ではない：実装と解析が容易なので主流ですが、最適性が保証されるわけではありません。実用では非線形・連接符号も使われます。

対応シミュレーション

本文のコードでハミング(7,4)の符号語・ $d_{\min}$ ・全1ビット誤りのシンドローム訂正を実証済み。