← すべての記事

ハミング符号：コンピュータが自らの誤りを検出する仕組み

2分で読めます

データは脆弱です。宇宙線がRAMのビットを反転させます。電気ノイズが信号を破損させます。傷がディスクを損傷させます。たった1ビットの反転でシステムがクラッシュしたりファイルが破損したりする世界で、コンピュータはどうやって動き続けているのでしょうか？

その答えは、コンピュータサイエンスで最もエレガントなアイデアの一つ、誤り訂正符号です。

重要なポイント

  • ハミング符号は戦略的な冗長性を追加する — パリティビットを2のべき乗の位置に配置することで、符号は単一ビットエラーを自動的に検出し、かつ訂正できます。
  • シンドロームがエラー位置を直接指し示す — すべての「1」ビットの位置をXORすると、任意の単一ビットエラーの正確な位置が明らかになり、再送信なしで訂正が可能になります。
  • 7ビットで4ビットのデータを運ぶ — Hamming(7,4)はわずか3つの追加ビットで4データビットを保護し、完全な単一エラー訂正を提供しながら57%の効率を達成します。
  • この数学はあらゆる場所にある — ECC RAM、QRコード、深宇宙通信、RAIDストレージ、Bluetoothはすべて、Hammingの洞察のバリエーションを使用しています。
  • 情報には基本的な限界がある — Claude Shannonは、どれだけの誤り訂正が可能かには理論的な最大値があることを証明しました。ハミング符号はこの限界にエレガントに近づいています。

なぜデータを2回送るだけではダメなのか？

誤り訂正への素朴なアプローチは反復です。すべてのビットを3回送る：0は000に、1は111になります。010を受信したら、多数決でおそらく0だと判断します。

これは機能しますが、無駄が多いのです。4ビットの情報を送るのに、12ビットを送信することになります。効率はわずか33%です。

1950年にベル研究所で働いていたRichard Hammingは、より良い質問を投げかけました：エラーを検出するだけでなく訂正するために必要な最小限の冗長性は何か？

彼の答えはコンピューティングを永遠に変えました。

Hamming(7,4)符号はどのように機能するか？

Hammingの洞察は幾何学的でした。力任せの反復の代わりに、パリティビットを戦略的な位置に配置し、二重の役割を果たせるようにしました：各パリティビットは同時に複数のデータ位置をチェックします。

Position:   1   2   3   4   5   6   7
Binary:    001 010 011 100 101 110 111
Type:       P1  P2  D1  P4  D2  D3  D4
            ↑   ↑       ↑
         Parity bits at powers of 2

魔法は：位置1、2、4がパリティビットです。各パリティビットは、その2進数表現に対応するビットがセットされているすべての位置をチェックします：

  • P1（位置1 = 001） は位置1、3、5、7をチェック（すべての奇数位置）
  • P2（位置2 = 010） は位置2、3、6、7をチェック
  • P4（位置4 = 100） は位置4、5、6、7をチェック

エラーが発生すると、各パリティチェックは合格（0）または不合格（1）になります。3つの結果が2進数を形成し、エラー位置を直接指し示します。

試してみよう：インタラクティブHammingシミュレータ

4つのデータビットを入力し、エンコードしてから、任意のビットをクリックしてエラーをシミュレートしてください。シンドローム検出が正確なエラー位置を特定する様子を観察できます。

なぜシンドロームがエラー位置を指し示すのか？

これが美しい部分です。1を含むすべての位置をXORすると、エラー位置が直接得られます。

位置5が反転したとしましょう。位置5は2進数で101です： - ビット0がセット → P1チェックが失敗 - ビット1がセットされていない → P2チェックが合格 - ビット2がセット → P4チェックが失敗

シンドローム = 101 = 5。エラーは位置5にあります。

これは偶然ではありません—Hammingは位置の2進数表現がこの情報をエンコードするように設計したのです。すべての位置には一意の2進数「署名」があり、パリティチェックがその署名を読み取ります。

2つのエラーがある場合はどうなるか？

Hamming(7,4)は： - ✓ 任意の単一ビットエラーを検出し訂正できる - ✓ 2ビットエラーを検出できる（ただし訂正はできない） - ✗ 3つ以上のエラーは誤訂正される可能性がある

より高い信頼性のために、SECDED（Single Error Correction, Double Error Detection：単一エラー訂正、二重エラー検出）と呼ばれる拡張版は、すべての位置をカバーするもう1つのパリティビットを追加します。あなたのコンピュータのECC RAMはこれを使用しています。

ハミング符号は今日どこで使用されているか？

アプリケーション なぜ重要か
ECC RAM 宇宙線は1GBあたり月に約1ビットを反転させます。ECCはそれを静かに訂正します。
QRコード QRコードの最大30%が損傷しても正しくスキャンできます。
深宇宙 Voyagerのデータは数十億マイルをReed-Solomon符号（Hammingの子孫）で横断します。
RAID 2 初期のRAIDシステムはディスクアレイ全体でハミング符号を使用していました。
Bluetooth 前方誤り訂正が無線干渉を処理します。

情報理論との関連

Hammingの研究は、Claude Shannonの情報理論に関する基礎的な論文（1948年）と同時期に行われました。Shannonは、任意のノイズのあるチャネルに対して、ある程度の効率低下を受け入れれば、任意に低いエラー確率でデータを送信できる誤り訂正符号が存在することを証明しました。

Shannon限界は理論的な最大値を定義します。ハミング符号はそこに到達しませんが、実用的で高速でエレガントです。ターボ符号やLDPC符号などの現代の符号はShannonの限界により近づき、4G/5Gセルラーから衛星テレビまであらゆるものを支えています。

洞察の背後にある洞察

Hammingの解決策を素晴らしいものにしているのは、単に機能するということだけではありません—エラー位置が構造から自然に現れるということです。パリティビットはエラーがどこにあるか「知っている」わけではありません。それらの関係が暗黙的にエンコードしているのです。

これは優れたエンジニアリングのパターンです：複雑な検出ロジックを構築しないでください。答えが数学から自然に導かれるようにシステムを設計してください。

よくある質問

ハミング符号とは何ですか？

ハミング符号は、特定の位置（2のべき乗）にパリティビットを追加して単一ビットエラーを検出・訂正する誤り訂正符号です。最も一般的なバージョンであるHamming(7,4)は、4データビットを合計7ビットにエンコードし、再送信なしで任意の単一ビットエラーを自動訂正できます。

シンドロームはどのようにエラー位置を特定するのですか？

各パリティビットは、そのパリティビットの位置で2進数表現に1がある位置をチェックします。ビットが反転すると、その位置をカバーするパリティチェックが失敗します。失敗したチェックの組み合わせがエラー位置と等しい2進数を形成します。これは各位置が一意の2進数「署名」を持っているため機能します。

ハミング符号は複数のエラーを修正できますか？

標準的なHamming(7,4)は単一ビットエラーのみを訂正できます。2ビットエラーは検出できますが訂正はできません。より高い信頼性のために、SECDED（Single Error Correction, Double Error Detection）は追加のパリティビットを加え、Reed-Solomonのようなより洗練された符号は複数のエラーを訂正できます。

なぜパリティビットは2のべき乗の位置に配置されるのですか？

位置1、2、4、8などは2進数で単一ビットに対応します（001、010、100、1000）。これにより、各パリティビットは符号語の重複しない「スライス」をチェックします。データ位置（3、5、6、7...）は2進数で複数のビットがセットされているため、複数のパリティビットによってチェックされ、誤り訂正に必要な冗長性が生まれます。

ECC RAMはどこで使用され、なぜ重要なのですか？

ECC（Error-Correcting Code）RAMは、サーバー、ワークステーション、ミッションクリティカルなシステムで使用されます。宇宙線と電気ノイズは1ギガバイトあたり月に約1回のビット反転を引き起こします。24時間365日稼働し、大量のRAMを持つシステムでは、訂正されないエラーはクラッシュやデータ破損を引き起こします。ECC RAMはSECDED符号を使用してこれらのエラーを静かに訂正します。

簡潔なまとめ

ハミング符号は、パリティビットを2のべき乗の位置に配置することで、最小限の冗長性で誤り訂正を解決します。各ビットは特定の位置のサブセットをチェックします。エラーが発生すると、失敗したパリティチェックがエラー位置を直接指し示す2進数を形成します—複雑なロジックは不要で、XOR演算だけです。1950年にRichard Hammingによって発明されたこのエレガントなアプローチは、ECCメモリからQRコード、深宇宙通信に至るまで、あらゆるものの基盤であり続けています。

さらに読む

  • The Art of Doing Science and Engineering by Richard Hamming — この投稿のインスピレーションとなった本
  • A Mathematical Theory of Communication by Claude Shannon (1948) — 情報理論の基礎
  • Interactive visualization of error-correcting codes — 3Blue1Brownの優れた動画

この投稿はインタラクティブ探求シリーズの一部で、コンウェイのライフゲームやルール110を含みます。コンピュータサイエンスの基礎についてさらに詳しくは、アーカイブをご覧ください。