ハミング符号: コンピューターはどうやって自分のミスを見つけるのか
データは壊れやすいものです。宇宙線は RAM 内で少し反転します。電気ノイズは信号を破壊します。ディスクに傷がつきます。たった 1 つのビットが反転しただけでシステムがクラッシュしたり、ファイルが破損したりする可能性がある世界で、コンピューターはどうやって動作し続けるのでしょうか?
その答えは、コンピューター サイエンスにおける最も洗練されたアイデアの 1 つである エラー訂正コード です。
重要なポイント
- ハミング コードにより戦略的冗長性が追加 — パリティ ビットを 2 のべき乗の位置に配置することで、コードはシングル ビット エラーを自動的に検出し、修正できます。
- シンドロームはエラーを直接指します — すべての「1」ビットの位置の XOR 演算により、単一ビット エラーの正確な位置が明らかになり、再送信せずに訂正が可能になります。
- 7 ビットは 4 ビットのデータを伝送します — Hamming(7,4) は、4 データ ビットを保護するために 3 つの追加ビットのみを使用し、完全な単一エラー訂正を提供しながら 57% の効率を達成します。
- この計算はどこにでもあります — ECC RAM、QR コード、深宇宙通信、RAID ストレージ、Bluetooth はすべて、ハミングの洞察のバリエーションを使用しています。
- 情報には根本的な限界がある — クロード シャノンは、誤り訂正の可能性には理論上の上限があることを証明しました。ハミング コードはこの制限にエレガントにアプローチします。
データを 2 回送信できないのはなぜですか?
エラー修正への素朴なアプローチは反復です。すべてのビットを 3 回送信します。0 は 000 に、1 は 111 になります。 010 を受け取った場合、多数決ではおそらく 0 であると考えられます。
これは機能しますが、無駄です。 4 ビットの情報を送信するには、12 ビットを送信することになります。効率は 33% です。
1950 年にベル研究所で働いていたリチャード・ハミングは、より良い質問をしました: エラーを検出するだけでなく修正するために必要な最小限の冗長性は何ですか?
彼の答えはコンピューティングを永遠に変えました。
ハミング(7,4) コードはどのように機能するのでしょうか?
ハミングの洞察力は幾何学的なものでした。ブルートフォース反復の代わりに、二重の役割を果たせる戦略的な位置にパリティ ビットを配置します。各パリティ ビットは複数のデータ位置を同時にチェックします。
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 はパリティ ビットです。それぞれのバイナリ表現で対応するビットが設定されているすべての位置をチェックします。
- 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 進数を形成します。
試してみましょう: インタラクティブなハミング シミュレーター
4 つのデータ ビットを入力してエンコードし、任意のビットをクリックしてエラーをシミュレートします。シンドローム検出が正確なエラー位置を特定する様子を観察してください。
症候群がエラーを示しているのはなぜですか?
ここが美しい部分です。 1 を含むすべての位置の XOR を計算すると、エラー位置が直接得られます。
位置 5 が反転されたとします。 2 進数の 5 位は 101 です。
- ビット 0 が設定される → P1 チェックが失敗する
- ビット 1 が設定されていない → P2 チェックに合格
- ビット 2 がセットされる → P4 チェックが失敗する
症候群 = 101 = 5。エラーは位置 5 にあります。
これは偶然ではありません。ハミングはバイナリ表現でこの情報をエンコードできるように位置を設計しました。すべての位置には一意のバイナリ署名があり、パリティ チェックはその署名を読み取ります。
2 つのエラーがある場合はどうなりますか?
Hamming(7,4) は次のことができます。 - ✓ シングルビットエラーを検出して修正します。 - ✓ 2 ビット エラーを検出します (ただし正しくはありません)。 - ✗ 3 つ以上のエラーは誤って修正される可能性があります
信頼性を高めるため、SECDED (単一エラー訂正、二重エラー検出) と呼ばれる拡張バージョンでは、すべての位置をカバーするパリティ ビットが 1 つ追加されています。コンピュータの ECC RAM はこれを使用します。
ハミング コードは現在どこで使用されていますか?
| 応用 | なぜそれが重要なのか |
|---|---|
| ECC RAM | 宇宙線は毎月 GB あたり最大 1 ビットを反転します。 ECC はそれらをサイレントに修正します。 |
| QR コード | QR コードの最大 30% が破損しても、正しくスキャンできます。 |
| 深宇宙 | ボイジャーのデータは、リード・ソロモン符号 (ハミングの子孫) によって数十億マイルに渡ります。 |
| RAID 2 | 初期の RAID システムでは、ディスク アレイ全体でハミング コードが使用されていました。 |
| ブルートゥース | 前方誤り訂正は無線干渉を処理します。 |
情報理論のつながり
ハミングの研究は、情報理論に関するクロード シャノンの基礎論文 (1948 年) と並行して行われました。シャノンは、ノイズの多いチャネルに対して、ある程度の効率損失を許容できれば、任意に低いエラー確率でデータを送信できるエラー訂正コードが存在することを証明しました。
シャノン制限は理論上の最大値を定義します。ハミング コードはそれには到達しませんが、実用的で高速かつエレガントです。 ターボ コード や LDPC コード などの最新のコードはシャノンの限界に近づき、4G/5G 携帯電話から衛星テレビまであらゆるものに電力を供給します。
洞察の背後にある洞察
ハミングの解決策が優れているのは、単に機能するというだけではなく、エラーの位置が 構造から現れるということです。パリティ ビットはエラーがどこにあるのかを「認識」しません。彼らの関係はそれを暗黙のうちにエンコードしています。
これは優れたエンジニアリングのパターンです。複雑な検出ロジックを構築しないでください。答えが数学から外れるようにシステムを設計します。
よくある質問
What is a Hamming code?
A Hamming code is an error-correcting code that adds parity bits at specific positions (powers of 2) to detect and correct single-bit errors. The most common version, Hamming(7,4), encodes 4 data bits into 7 total bits, allowing automatic correction of any single-bit error without retransmission.
How does the syndrome identify the error position?
Each parity bit checks positions whose binary representation has a 1 in that parity bit's position. When a bit flips, the parity checks that cover that position fail. The combination of failed checks forms a binary number that equals the error position. This works because each position has a unique binary "signature."
Can Hamming codes fix multiple errors?
Standard Hamming(7,4) can only correct single-bit errors. It can detect (but not correct) two-bit errors. For higher reliability, SECDED (Single Error Correction, Double Error Detection) adds an extra parity bit, and more sophisticated codes like Reed-Solomon can correct multiple errors.
Why are parity bits placed at powers of 2?
Positions 1, 2, 4, 8, etc. correspond to single bits in binary (001, 010, 100, 1000). This ensures each parity bit checks a non-overlapping "slice" of the codeword. The data positions (3, 5, 6, 7...) have multiple bits set in binary, so they're checked by multiple parity bits, creating the redundancy needed for error correction.
Where is ECC RAM used and why does it matter?
ECC (Error-Correcting Code) RAM is used in servers, workstations, and mission-critical systems. Cosmic rays and electrical noise cause roughly one bit flip per gigabyte per month. For systems running 24/7 with large amounts of RAM, uncorrected errors would cause crashes and data corruption. ECC RAM uses SECDED codes to silently correct these errors.
簡単な概要
ハミング コードは、パリティ ビットを 2 のべき乗に配置することで最小限の冗長性でエラー訂正を解決します。各ビットは位置の特定のサブセットをチェックします。エラーが発生すると、失敗したパリティ チェックがエラーを直接指す 2 進数を形成します。複雑なロジックは必要なく、XOR 演算だけで済みます。 1950 年に Richard Hamming によって発明されたこのエレガントなアプローチは、ECC メモリから QR コード、深宇宙通信に至るまで、あらゆるものの基礎となっています。
さらに読む
- The Art of Doing Science and Engineering (リチャード・ハミング著) — この投稿のきっかけとなった本
- コミュニケーションの数学理論 クロード・シャノン著 (1948) — 情報理論の基礎
- Interactive visualization of error-correcting codes — 3Blue1Brown の素晴らしいビデオ
*この投稿は、アルゴリズムが視覚的な直感と出会う Interactive Explorations シリーズの一部です。ここで検討したのと同じ「構造からの出現」パターンが Reynolds’ boids algorithm にも現れており、そこでは 3 つの単純なルールが集中管理なしで群れを生み出します。また、multi-agent AI systems では、グローバル プランではなくローカル ルールを通じて調整されます。