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

1ビットが壊れても、メッセージ全体を失うとは限りません。ハミングの構成では、4個のデータビットに3個の検査ビットを加え、どの位置の単一ビット反転でも特定して訂正できます。ただし、7ビットの符号だけでは1個の誤りと2個の誤りを確実に区別できません。

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

AI生成の概念イラスト：乱れた流れに検査で秩序を戻す表現です。実際の回路や無制限の誤り訂正の証拠ではありません。

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$

$p_2=d_1\oplus d_3\oplus d_4$

$p_4=d_2\oplus d_3\oplus d_4$

受信側は{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$

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

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$

ハミングの構成は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]

シンドローム j	パリティ q	仮定の下での処理
0	0	誤りなし
0	1	ビット8を訂正
非ゼロ	1	ビットjを訂正
非ゼロ	0	2個の誤りを警告し、訂正しない

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}$

約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ケースを検査しました。

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

本記事のNews編集手順

参照改訂：HAMMING-EN-1。1950年の一次論文をアーカイブのスキャンとOCRで全文読解し、構成とSECDEDの分類はスキャン画像でも確認しました。出版社の記録で書誌上の日付を確認しました。MIT講義ノートは現代的な記法の比較に用いました。再現可能なスクリプトで数値計算と有限符号の検査を実行しました。執筆と7言語への翻訳はAIによるもので、独立した専門家の査読や人による検証ではありません。模式図はコードで作成し、各言語に対応させています。表紙はAI生成の概念イラストであり、写真、装置、実測グラフではありません。