ハミング符号（1ビット誤り訂正）
複数のパリティビットで1ビットの誤りを検出・訂正できる符号
📌ハミング符号とは
ハミング符号とは、データビットの間に複数のパリティ（検査）ビットを挿入することで、1ビットの誤りを「検出」するだけでなく「どのビットが誤ったか特定して訂正」できる誤り訂正符号です。1950年にR. Hammingが考案しました。
通常のパリティチェックは「誤りが1個ある」ことしか分かりませんが、ハミング符号はパリティビットを位置1,2,4,8…（2のべき乗の位置）に複数置くのがポイントです。各パリティが「自分の位置の2進数ビットが立っている位置」だけを担当するため、複数のパリティの検査結果を組み合わせると誤りの位置がピンポイントで分かります。
身近な例えで言うと、複数人の目撃証言を突き合わせて犯人の居場所を絞り込むようなものです。証言（パリティ）が1つだけなら「誰かが嘘をついた」程度しか分かりませんが、複数の証言を交差させると「3番テーブルの人物」のように特定できます。上のツールでデータを変えたり誤り位置を注入したりすると、シンドローム（誤り位置を示す番号）が自動計算される様子を確認できます。
📐誤り訂正の仕組み
必要なパリティビット数 k は、データビット数 n に対して次の不等式を満たす最小の整数です。
2k ≥ n + k + 1
右辺の意味: k 個のパリティで作れる検査値（シンドローム）は 2k 通り。そのうち1つは「誤りなし(=0)」を表すので、残り 2k−1 通りで「全 n+k ビットのどこに誤りがあるか」を区別できなければなりません。よって 2^k − 1 ≥ n + k、つまり 2^k ≥ n+k+1 となります。
計算例（データ4ビット）:
k=2 → 2² = 4, n+k+1 = 4+2+1 = 7 → 4 ≥ 7 ✗
k=3 → 2³ = 8, n+k+1 = 4+3+1 = 8 → 8 ≥ 8 ✓
∴ パリティは 3 ビット必要（全長7ビット = ハミング(7,4)符号）
受信側では各パリティを再検査し、合わなかったパリティを2進数で並べた値がシンドロームです。
・シンドローム = 0: 誤りなし
・シンドローム = m（≠0）: 第m位のビットが誤り → そのビットを反転して訂正
・パリティ位置を2のべき乗にすることで、シンドロームの値がそのまま誤り位置になる
⚖️検出と訂正の違い
誤り制御には「検出（detection）」と「訂正（correction）」の2段階があります。検出は「誤りがあるかどうか分かる」だけ、訂正は「誤りを直して正しいデータを復元できる」ことを意味します。
| 方式 | 検出能力 | 訂正能力 | 追加ビット |
|---|---|---|---|
| パリティ（1ビット） | 1ビット誤り検出 | 不可 | 1ビット |
| ハミング符号 | 1ビット誤り検出 | 1ビット誤り訂正 | 複数（log₂規模） |
| CRC | 連続誤りに強い | 不可（再送が前提） | 多項式長 |
訂正は検出より多くの冗長ビットが必要です。位置を特定して直すには「誤りがあるかどうか」より多くの情報が要るからです。ハミング符号は1ビットの訂正ができますが、2ビット同時誤りは正しく訂正できません（誤訂正してしまう）。
関連するポイント:
・必要なパリティ数は 「2^k ≥ n+k+1」から求められる
・ハミング距離（符号語間で異なるビット数）が「2d+1」以上なら d ビット訂正可能
・検出のみなら再送（ARQ）、訂正まで行うなら前方誤り訂正（FEC）と対応する
🤔なぜパリティを2のべき乗の位置に置くのか
答えは「シンドローム（誤り位置を示す数）が、そのまま誤った位置番号になる」ように設計するためです。
仕組みを順に理解しましょう。各位置番号を2進数で表したとき、その2進数の各桁（1の位、2の位、4の位…）の値が「1」の位置を、対応するパリティが担当します。
・p1（位置1＝2進数 001）は「2進数の1の位が1」の位置（1,3,5,7…）を担当
・p2（位置2＝2進数 010）は「2進数の2の位が1」の位置（2,3,6,7…）を担当
・p4（位置4＝2進数 100）は「2進数の4の位が1」の位置（4,5,6,7…）を担当
例えば第5位（＝2進数 101）が誤ったとします。p1は失敗（1）、p2は成功（0）、p4は失敗（1）。シンドロームは 101₂ = 5。これは誤り位置の5と一致します。パリティを2のべき乗の位置に置くからこそ、シンドロームが誤り位置の2進数表現と一致するという設計になっているのです。
💡訂正するために必要な情報量
訂正は検出より多くのパリティビットを必要とします。なぜなら、「誤りがあるか」より「どこが誤りか」の方が、伝えなければならない情報が多いからです。
具体的に数えると:
・パリティ（1ビット）：「0=正常、1=異常」の2通りしか伝えられない。どこが誤りかは分からない
・ハミング符号（複数ビット）：k個のパリティで 2^k 通りの情報を伝えられる。「0=正常」以外の残り 2^k−1 通りで「どの位置が誤りか」を区別できる
身近な例えは「警報アラーム vs. GPS」の違いです。アラーム（検出のみ）は「何かがおかしい」と鳴るだけですが、GPS（訂正可）は「今どこにいるか」を正確に教えてくれます。GPSが多くの衛星（情報源）を必要とするように、訂正可能な符号も多くのパリティビット（情報源）が必要です。この「冗長ビットをどれだけ使えるか」と「誤り訂正の強さ」のトレードオフが、パリティ・ハミング・CRCの使い分けの根本です。
