ハミング符号（Hammingコード）とは？仕組み・実装・応用を徹底解説

2025年12月11日 最終更新日時 : 2025年12月11日 エバープレイ編集部

概要

ハミング符号（Hamming code）は、Richard W. Hamming が1940年代末に提案した線形誤り訂正符号の一種で、1ビット誤りの検出と訂正（Single Error Correction, SEC）を効率よく行うために設計されています。最もよく知られているのが二進（GF(2)）のハミング符号で、短い符号長と低オーバーヘッドで単一ビット誤りを訂正し、メモリのECCや通信の基礎的な誤り制御として広く使われています。

基本原理と数学的性質

ハミング符号は線形符号であり、パリティビット（検査ビット）を情報ビットに付加して符号語を作ります。r 個のパリティビットを用いるとき、符号長 n と情報長 k は次の関係を満たします。

  • n = 2^r - 1
  • k = n - r

この式は、r 個のパリティビットで 2^r - 1 個の非ゼロシンドローム（すなわち誤りパターン）を識別でき、各シンドロームが1つの誤ったビット位置に対応するため成立します。ハミング符号の最小ハミング距離は 3 で、1ビットの誤りを検出・訂正でき、2ビット誤りを検出できる（必ずしも訂正できない）という性質を持ちます。

ハミング(7,4) の具体例

最も代表的な例が Hamming(7,4) です。ここでは r=3、n=7、k=4 です。ビット位置は1から7まで番号を付け、パリティビットは 1, 2, 4 の位置（2の累乗）に置きます。各パリティビットは、その位置のビットインデックスの2進表現において該当ビットが1である位置の情報ビットと自身を含めたパリティを取ります。具体的には次のようなカバー関係になります。

  • p1（位置1）: ビット位置 1,3,5,7
  • p2（位置2）: ビット位置 2,3,6,7
  • p4（位置4）: ビット位置 4,5,6,7

例えば情報ビットを b3,b5,b6,b7 に割り当て、各 p を偶数パリティで設定すれば符号語が出来上がります。

エンコード手順（一般論）

1. 情報ビットを k 個用意し、符号長 n のうちパリティ位置に空欄を作って配置する（通常は系統的符号として情報ビットを残す配置にする）。2. 各パリティビットは、パリティ検査行列 H の行に対応するビット集合を XOR（GF(2)の和）して設定する。3. 出力は n ビットの符号語。数学的には生成行列 G を用いて c = uG（u は情報ビット列）と表される。

デコードとシンドロームによる誤り訂正

受信側では受け取った n ビット c' に対してパリティ検査行列 H を用いてシンドローム s = H c'^T を計算します。s がゼロベクトルなら誤りなし、非ゼロならそのパターンは1ビット誤り位置のインデックスを示します（H の列が各位置の2進表現を表すように設計されているため）。シンドロームで得られた位置のビットを反転すれば訂正が完了します。Hamming(7,4) の場合は 3 ビットのシンドロームで 1〜7 のいずれかを特定できます。

拡張ハミング符号と SECDED

標準ハミング符号は 1 ビット訂正、2 ビット検出が限界ですが、1 ビットの全体パリティビットを追加することで拡張ハミング符号（Extended Hamming code）になり、Single Error Correction, Double Error Detection（SECDED）を実現できます。例えば Hamming(7,4) にパリティを1ビット追加すると Hamming(8,4) となり、受信時に全体パリティチェックを行うことで2ビット誤りを検出可能になりますが、2ビット誤りの訂正はできません。

実装上の注意点と効率化

実装ではパリティ検査を逐次XORで行うのが基本ですが、ハードウェアやソフトウェアで効率的に行うために次の工夫が用いられます。

  • テーブルルックアップ: 小さなブロック単位で事前計算したシンドロームテーブルを利用する。
  • SIMDやビット演算の活用: ワード単位でXORを一括して計算することで高速化。
  • 並列化: ハードウェア実装では並列回路で1クロックで複数のパリティを計算する。

また、ビット順序やパリティの奇偶（偶数パリティか奇数パリティか）を実装者間で統一することが重要です。表現や符号化規約が違うと、互換性が失われることがあります。

用途と限界

用途としては、メモリ（ECCメモリ）での単一ビット誤り訂正、低遅延でのデータ保護が求められる組み込み機器や古典的な通信システムなどが挙げられます。利点は計算量が比較的小さく、回路実装が容易である点です。一方で限界は、連続するビット（バースト誤り）や多数ビットの誤りに弱いこと、冗長率が大きな符号長では効率的でないことです。バースト誤りや高い誤り率が予想される場合は、BCH符号やリード・ソロモン符号、LDPC符号などより強力な誤り訂正符号が用いられます。

実用例と現代での位置付け

ハミング符号は今でも多くの場面で使われています。例えばサーバー用ECCメモリの一部仕様、ワイヤレス通信の一部低レイヤプロトコル、衛星通信の補助的な用途、あるいは学術教育での誤り制御の基本原理の学習教材としても広く用いられます。現代では性能要求に応じてより高性能な符号と組み合わせることが多く、単体での用途は限定的ながら基礎理論としての重要性は変わりません。

まとめ

ハミング符号は、少ない追加ビットで単一ビット誤りの訂正を実現する効率的な線形符号です。設計原理はパリティビットを冪乗位置に配置することと、パリティ検査行列を用いたシンドローム解析に集約されます。実装は比較的簡単で、組み込み機器やECCメモリなど低オーバーヘッドでの信頼性向上に適しています。一方、性能限界を理解し、必要に応じて拡張ハミング（SECDED）やより高度な符号を検討することが重要です。

参考文献

カテゴリー
IT
前の記事
IT人材の現状と未来 — 需給・育成・キャリア戦略の徹底ガイド
2025年12月11日
次の記事
T-800完全解説：起源・設計・能力から文化的影響まで
2025年12月11日