ハミング、1950年：3個の検査ビットで1個の誤りを直す

本記事は、引用資料に基づいてAIシステムが執筆・翻訳し、News編集手順に従って自動チェックを実施しました。

保守更新 — 2026年10月7日。 利用可能なアクセスでは旧表紙の元ファイルと生成記録を回収できなかったため、表紙を差し替えました。新しい画像はネイティブ画像ツールから受け取り、目視で確認しました。ファイル、生成指示と参照資料は非公開の編集記録に保存しています。旧表紙と未検証の来歴は履歴に残しています。これはイラストであり、実験的な証拠ではありません。中心となる科学的結果は維持しています。

AI生成の概念イラスト。ハミング符号（7,4）はデータ4ビットと検査3ビットからなり、1ブロック内の1ビット反転を訂正します。タイルは象徴表現で、実際の回路ではありません。

式を読む前に

ビットは0か1の値です。反転すると、一方が他方に変わります。パリティは、ある集まりに含まれる1の個数が偶数か奇数かを表します。例えば101には1が2個あるので、偶数パリティです。冗長性とは、受信側がデータを検査できるように追加情報を送ることです。ここでは、重なり合う3つの検査で反転した1ビットを特定します。ただし、7ビットのブロック内で反転が高々1個という条件があります。

考え方を理解するには第3節の例をたどり、その後で第2節の式に戻ってください。検証には下の完全なプログラムを使えます。検査に合格したら、どのビットも変わっていないと証明できるでしょうか。答えが誤りモデルに依存する理由を第5節で説明します。

1. 構造を持つ冗長性で信頼性を高める

1950年4月、Richard W. HammingはBell System Technical Journalに「Error Detecting and Error Correcting Codes」を発表しました。出発点は実務上の問題です。無人運転中の計算で故障を検出するだけでは作業が停止しますが、その位置を特定して直せれば計算を続けられます。論文が示すのは具体的な2進符号の構成であり、あらゆる損傷を修復できるという約束ではありません。[1,2]

進歩の核心は、冗長性に診断に役立つ情報を持たせることです。4ビットをそれぞれ3回送れば12ビットが必要です。ハミング符号なら、同じ4データビットをブロック内の任意の1ビット反転から守るのに7ビットを使います。これは冗長性の配置の違いであり、すべての通信路で最適という意味ではありません。圧縮は冗長性を減らし、誤り訂正は制御された冗長性を加えます。

2. 7個の位置と3つの問い

送信位置を1から7まで番号付けします。位置1、2、4が検査ビット、位置3、5、6、7がデータd₁、d₂、d₃、d₄です。⊕は排他的論理和、つまり2を法とする加算で、1 ⊕ 1 = 0です。次の式で偶数パリティを設定します。pの添字は検査の順番ではなく位置です。[1, §3]

$p_1=d_1\oplus d_2\oplus d_4$p1​=d1​⊕d2​⊕d4​

$p_2=d_1\oplus d_3\oplus d_4$p2​=d1​⊕d3​⊕d4​

$p_4=d_2\oplus d_3\oplus d_4$p4​=d2​⊕d3​⊕d4​

受信側は{1,3,5,7}、{2,3,6,7}、{4,5,6,7}を検査します。不一致ならシンドロームビットを1、一致なら0とし、s₁、s₂、s₄と呼びます。反転が高々1個なら、その位置jは次式です。

$j=s_1+2s_2+4s_4$j=s1​+2s2​+4s4​

シンドロームがゼロなら誤りなし、と言えるのはこの仮定の下だけです。一般的な完全性の証明ではありません。

3. 自分で再現できる訂正

データ1010を考えます。p₁ = 1、p₂ = 0、p₄ = 1となり、位置順に左から読む送信語は1011010です。位置6が反転すると1011000を受信します。第1検査は偶数、第2・第3検査は奇数です。したがって(s₁,s₂,s₄) = (0,1,1)、j = 0 + 2 + 4 = 6です。ビット6を戻して位置3,5,6,7を読めば1010を復元できます。

コードで作成した科学模式図。正確なビット列を示し、実験データではありません。

これは編集上の計算例で、実験値ではありません。検査ビット自体が反転した場合も訂正できます。ただし、ブロック境界と位置が既知であることを仮定しています。ビットの挿入や欠落は別の誤りモデルです。

4. なぜ訂正できるのか

3個の2進検査には8通りの結果があり、7個の単一誤り位置と誤りなしの計8状態を区別できます。一般に、検査ビット数r、全ビット数nの2進符号で1個の反転を訂正するには、少なくともn + 1通りのシンドロームが必要です。

$2^r\ge n+1$2r≥n+1

ハミングの構成はn = 2ʳ − 1、データ数k = n − rでこの数に達します。r = 3ならn = 7、k = 4です。異なる有効符号語間で相違する位置の最小数、すなわち最小ハミング距離は3です。受信語が2つの有効符号語からそれぞれ1反転以内なら、両者の距離は高々2になり、矛盾します。

有効符号語は16個で、それぞれ自分自身と1反転で到達する7語を持ちます。重ならない集合が128通りを埋め尽くします：16 × 8 = 128。「完全符号」とはこの充填の性質であり、任意の雑音下で失敗しないという意味ではありません。[1, §§5,7]

5. 2個の誤りが生む落とし穴

2ビット反転では必ず非ゼロのシンドロームが出るため、無効な語を警告するだけの検出器なら検出できます。しかし、非ゼロをすべて単一誤りとみなす復号器は誤訂正し得ます。位置2と5の反転は位置7だけの反転と同じシンドロームです。ビット7を「訂正」すると3ビットが誤った別の有効符号語になります。

全体の偶数パリティを保つ8番目のビットを加えると、最小距離は4になります。この拡張符号は1ビット誤り訂正・2ビット誤り検出、SECDEDを実現します。次の判断は反転が高々2個という仮定に基づきます。qは受信した8ビット全体のパリティです。[1, §4]

3個以上の誤りは保証範囲外です。SECDED復号器がその一部を誤訂正することもあります。「2ビット誤り検出」は、より大きな故障をすべて診断するという意味ではありません。

6. 仮定を明示した数値例

各送信ビットが独立に確率p = 0.01で反転し、その確率は0と1で同じとします。符号化・復号は完全で、ブロック境界も既知とします。この7ビット符号と復号器では、復元した4ビットメッセージが誤るのは反転が2個以上のとき、かつそのときだけです。

$\begin{aligned} P_{\rm fail}&=1-(1-p)^7\\ &\quad-7p(1-p)^6. \end{aligned}$Pfail​​=1−(1−p)7−7p(1−p)6.​

約0.002031、つまりブロックの0.2031%です。4ビットを無符号で送る場合は1 − (1 − p)⁴ = 0.039404、誤りを含むメッセージは3.9404%です。これはメッセージ誤り確率であり、復号後のビット誤り率や装置の実測性能ではありません。

代償は4データビットに対する3追加ビットで、送信ビット数は75%増え、符号化率は4/7 ≈ 0.5714データビット／送信ビットです。比較で固定しているのはpであり、帯域幅・送信時間・メッセージ当たりのエネルギーを同時に固定してはいません。

7. この結果が保証すること、しないこと

長く残る貢献は、代数と信頼性を具体的につないだことです。有効な語を離して配置し、短い検査値を計算して、限定された故障の位置を見つけます。7ビットの例は網羅的に検証できます。本記事では16メッセージについて誤りゼロまたは1個の128ケースと、拡張符号の2個誤り448ケースを検査しました。

任意のバースト誤り、破損したソフトウェア、悪意ある改変、同期喪失を直す符号ではありません。実システムは故障モデルに符号を合わせ、符号器・復号器と周辺回路も守る必要があります。ハミング論文は現代のハードウェア性能を測定していません。本記事の数値例も、そのような主張とは区別します。シャノンの通信限界の議論を補う有限の具体的構成であり、常に通信路容量へ到達する万能な解法ではありません。

8. 有限の計算を再現する

手順HAMMING-REPRO-1。Pythonコード全体をreproduce_hamming.pyにコピーし、python3 reproduce_hamming.pyを実行します。Python標準ライブラリだけを使い、ネットワーク、データのダウンロード、乱数シードは不要です。この編集改訂ではCPython 3.12.14で実行しました。位置は1から始まり、第8ビットで全体を偶数パリティにします。プログラムは全16メッセージを列挙し、パリティ条件から有効な7ビット語を別に構成して、符号器の出力と比較します。

期待する出力はstatus PASS、codewords 16、minimum_distances [3, 4]です。件数は、7ビットで誤り0個または1個を正しく復元する128例、8ビットでは144例、拡張符号が検出する2個誤り448例、7ビット復号器が誤訂正する2個誤り336例、記載した8ビット復号器が誤訂正する3個誤り896例です。最後の2つは負の対照で、成功ではなく限界を示します。p = 0.01ではcoded_message_errorは約0.00203104163494、uncoded_message_errorは0.03940399です。これはpを固定した独立な反転を仮定し、同じエネルギーや帯域幅を仮定した比較ではありません。

"""News HAMMING-REPRO-1: finite mathematical check, not hardware validation."""
from itertools import combinations, product
import json
import platform


def encode(data):
    a, b, c, d = data
    return (a ^ b ^ d, a ^ c ^ d, a, b ^ c ^ d, b, c, d)


def syndrome(word):
    a, b, c, d, e, f, g = word[:7]
    return (a ^ c ^ e ^ g) + 2 * (b ^ c ^ f ^ g) + 4 * (d ^ e ^ f ^ g)


def flip(word, positions):
    result = list(word)
    for position in positions:
        result[position - 1] ^= 1
    return tuple(result)


def decode7(word):
    position = syndrome(word)
    return flip(word, (position,)) if position else word


def decode8(word):
    position, parity = syndrome(word), sum(word) % 2
    if parity:
        return flip(word, (position or 8,))
    return None if position else word


def distance(a, b):
    return sum(x != y for x, y in zip(a, b))


def require(condition, label):
    if not condition:
        raise RuntimeError(label)


messages = list(product((0, 1), repeat=4))
code7 = [encode(data) for data in messages]
code8 = [word + (sum(word) % 2,) for word in code7]
# Independent enumeration uses parity sums rather than the encoder equations.
groups = ((1, 3, 5, 7), (2, 3, 6, 7), (4, 5, 6, 7))
oracle = {
    word for word in product((0, 1), repeat=7)
    if all(sum(word[p - 1] for p in group) % 2 == 0 for group in groups)
}
require(len(set(code7)) == 16 and set(code7) == oracle, "codebook")
min7 = min(distance(a, b) for a, b in combinations(code7, 2))
min8 = min(distance(a, b) for a, b in combinations(code8, 2))
require((min7, min8) == (3, 4), "minimum distances")
counts = {"seven_zero_or_one": 0, "eight_zero_or_one": 0,
          "eight_double_detected": 0, "seven_double_miscorrected": 0,
          "eight_triple_miscorrected": 0}
for word in code7:
    for positions in [()] + [(i,) for i in range(1, 8)]:
        require(decode7(flip(word, positions)) == word, "seven-bit recovery")
        counts["seven_zero_or_one"] += 1
    for positions in combinations(range(1, 8), 2):
        received = flip(word, positions)
        require(syndrome(received) != 0, "double error detectable")
        require(decode7(received) != word, "double error outside correction guarantee")
        counts["seven_double_miscorrected"] += 1
for word in code8:
    for positions in [()] + [(i,) for i in range(1, 9)]:
        require(decode8(flip(word, positions)) == word, "eight-bit recovery")
        counts["eight_zero_or_one"] += 1
    for positions in combinations(range(1, 9), 2):
        require(decode8(flip(word, positions)) is None, "double error must be flagged")
        counts["eight_double_detected"] += 1
    for positions in combinations(range(1, 9), 3):
        result = decode8(flip(word, positions))
        require(result is not None and result != word and result in code8,
                "triple error counterexample")
        counts["eight_triple_miscorrected"] += 1
require(list(counts.values()) == [128, 144, 448, 336, 896], "case counts")
require(encode((1, 0, 1, 0)) == (1, 0, 1, 1, 0, 1, 0), "worked example")
require(syndrome((1, 0, 1, 1, 0, 0, 0)) == 6, "worked syndrome")
p = 0.01
failure = 1 - (1-p)**7 - 7*p*(1-p)**6
uncoded = 1 - (1-p)**4
require(abs(failure - 0.00203104163494) < 1e-12, "probability")
print(json.dumps({"protocol": "HAMMING-REPRO-1", "python": platform.python_version(),
                  "codewords": len(code7), "minimum_distances": [min7, min8],
                  "counts": counts, "p": p, "coded_message_error": failure,
                  "uncoded_message_error": uncoded, "status": "PASS"}, indent=2))

PASSは、これらの有限な数学的検査に合格したことを意味します。ハードウェア性能、別の誤りモデルへの頑健性、独立した追試を示すものではありません。python欄は使用した処理系のバージョンなので異なる場合があります。RuntimeErrorが出たらコードと出力全体を保存し、示された検査を調べてください。途中までの実行は検証完了ではありません。

本記事のNews編集手順

2026-10-03 — 改訂HAMMING-EN-2では段階的な導入と完全な再現手順を追加しました。科学的な本文とコードで作成した図はHAMMING-EN-1から維持しています。今回の更新では構成と限界を1950年の論文およびMITの第5.6–5.7節で再確認し、有限のプログラムを実行しました。執筆と翻訳はAIによるもので、独立した専門家の査読や人による検証ではありません。

資料

[1] R. W. Hamming — Error Detecting and Error Correcting Codes — DOI: 10.1002/j.1538-7305.1950.tb00463.x.

[2] Nokia Bell Labs — Error Detecting and Error Correcting Codes.

[3] MIT 6.02 — Coping with Bit Errors using Error Correction Codes.