ハミング符号をPythonで実装する｜メモリのECCが1ビット誤りを直すしくみ

サーバーのメモリには、宇宙線などでビットが勝手に反転することがあります。それを自動で直すのが ECC（誤り訂正符号）、その代表が ハミング符号。1ビットの誤りを検出するだけでなく訂正までできます。Pythonで実装して仕組みを理解します。

しくみ：パリティで位置を特定

ハミング符号は、データにいくつかのパリティビットを混ぜます。誤りが起きると、複数のパリティが同時に崩れ、その組み合わせから何ビット目が化けたかが特定できます。だから訂正できるのです。

準備

Python標準機能だけ。

① (7,4)ハミング符号：4ビットを7ビットに

4ビットのデータに3つのパリティを足して7ビットにします。

def encode(data):
    d1, d2, d3, d4 = data
    p1 = d1 ^ d2 ^ d4          # パリティ1
    p2 = d1 ^ d3 ^ d4          # パリティ2
    p3 = d2 ^ d3 ^ d4          # パリティ3
    return [p1, p2, d1, p3, d2, d3, d4]   # 位置1..7

code = encode([1, 0, 1, 1])
print("符号語:", code)

② 誤りを訂正する

受け取った符号語のパリティを再計算し、崩れ方から誤り位置を割り出します。

def decode(code):
    p1, p2, d1, p3, d2, d3, d4 = code
    # シンドローム：どのパリティが合わないか
    s1 = p1 ^ d1 ^ d2 ^ d4
    s2 = p2 ^ d1 ^ d3 ^ d4
    s3 = p3 ^ d2 ^ d3 ^ d4
    error_pos = s1 * 1 + s2 * 2 + s3 * 4   # 2進で誤り位置
    if error_pos:
        print(f"  {error_pos}ビット目に誤り → 訂正")
        code = code.copy()
        code[error_pos - 1] ^= 1            # そのビットを反転して直す
    return [code[2], code[4], code[5], code[6]]   # データ部を取り出す

# エラーなし
print("正常:", decode(encode([1, 0, 1, 1])))

# 5ビット目をわざと反転
bad = encode([1, 0, 1, 1]); bad[4] ^= 1
print("訂正:", decode(bad))

出力:

正常: [1, 0, 1, 1]
  5ビット目に誤り → 訂正
訂正: [1, 0, 1, 1]

5ビット目が化けても、シンドロームから位置を特定して自動訂正。元のデータ 1011 がちゃんと復元できました。

まとめ

• ハミング符号はパリティビットで1ビット誤りを検出・訂正する
• 複数パリティの崩れ方（シンドローム）から誤り位置を特定
• (7,4)は4ビットに3パリティ。1ビットを自動訂正できる
• 実用はSECDED。信頼性と容量のトレードオフで使い分ける

もう少し詳しく（背景と理論）

ハミング符号は Richard Hamming が1950年に発表した、誤りを訂正できる最初期の誤り訂正符号です¹。鍵となる概念がハミング距離——2つの符号語で異なるビット数のことで、符号語間の最小距離 d があれば「d−1 個の誤り検出」または「⌊(d−1)/2⌋ 個の誤り訂正」ができます²。ハミング符号はパリティビットを賢く配置して最小距離3を確保し、1ビット誤りの訂正を実現します。さらにパリティを1つ足した SECDED（Single Error Correction, Double Error Detection）は、1ビット訂正＋2ビット検出ができ、サーバーの ECCメモリ で標準的に使われています³。宇宙・通信・ストレージなど、誤りが避けられない現場を支える基礎技術です。

次の一歩 🌸

誤り検出のみのCRCチェックサム、2進数の基礎は2進数と2の補数、メモリはAIチップとHBMへどうぞ。

Footnotes

1. Hamming, R. (1950). "Error Detecting and Error Correcting Codes." Bell System Technical Journal. 実用的な誤り訂正符号の先駆け。 ↩

2. ハミング距離は異なるビット数。最小距離 d の符号は d−1 誤り検出、または ⌊(d−1)/2⌋ 誤り訂正が可能。符号設計の基本指標。 ↩

3. SECDED は最小距離4で1ビット訂正＋2ビット検出。DRAM の ECC メモリで広く採用され、ソフトエラー（宇宙線等）からデータを守る。 ↩