データベーススペシャリスト 2013年 午前2 問22

ハミング符号（ECC）【午前2解説】

正解の理由

解法ステップ

1. 各選択肢が「検出」「訂正」のどちらを提供するかを把握する。
2. 「1ビット訂正」かつ「2ビット検出」を同時に満たせる方式を探す。
3. ハミング符号の性質（最小距離、拡張によるSECDED）を当てはめて判定する。

選択肢別の誤答解説

• ア: 偶数パリティ
  偶数パリティはブロック全体のビット数の偶奇を保持するだけで、単一ビット誤りを検出できます（1ビットが反転すればパリティが崩れる）が、誤りの位置は分からず訂正はできません。またビット反転が偶数個（2ビットなど）だと検出できない場合があります。従って「1ビット訂正」を満たしません。
• イ: 垂直パリティ
  「垂直パリティ」はしばしば横・縦のパリティを組み合わせた方式（ブロックパリティ）や行単位のパリティを指しますが、単純な垂直パリティだけでは位置特定→訂正ができず、要件を満たしません。冗長配置（例えば行×列パリティ）で限定的に訂正を行う設計もありますが、問題文で求める一般的なECC（1ビット訂正＋2ビット検出）とは一致しません。
• ウ: チェックサム
  チェックサムはデータの誤り検出用であり、誤り位置を特定して訂正する機能はありません。誤り検出率はアルゴリズム次第で高められますが、1ビット訂正の能力はありません。
• エ: ハミング符号（正解）
  ハミング符号はパリティビットを配置して単一ビット誤りの訂正を行います。さらにメモリ向けの実装では全体パリティを追加した拡張ハミング（SECDED）を使い、1ビット誤りを訂正し、2ビット誤りを確実に検出するために用いられます。

よくある誤解

1. 偶数パリティは1ビット誤りを検出できないという誤解
   偶数パリティは1ビット誤りを検出できます。ただし位置特定や訂正はできません。また2ビットなど偶数個の誤りは見逃すことがあります。
2. 「ハミング符号は常に2ビット誤りを検出する」との誤解
   純粋な（非拡張）ハミング符号は理論的に最小距離3なので理論上は多くの2ビット誤りを非符号語に変えるため検出が可能ですが、デコーダの運用次第では2ビット誤りのパターンが単一ビット誤りと同じシンドロームを与え誤補正される危険があります。実務のECCではこの問題を避けるために全体パリティを追加した拡張ハミング（SECDED）を用い、2ビット誤りを確実に検出して訂正はしない（エラーとして報告する）ようにします。
3. チェック方式は同じ役割を果たすという誤解
   CRCやチェックサムは高い検出率を持ちますが、単純に誤りを特定して訂正する機能は持ちません。エラー訂正（ECC）とは目的が異なります。

補足コラム

• ハミングビットの個数の決定式
  データビット数を$m$、パリティビット数を$r$とすると、次を満たす最小の$r$が必要です。
  $2^r\ge m+r+1$
  例: データ4ビット($m=4$)の場合、$r=3$で $2^3=8\ge 4+3+1=8$ となり、Hamming(7,4)が作れます。
• Hamming(7,4)の簡単な動作例
  位置1,2,4をパリティビットとし、残りをデータとします。受信時にパリティ検査を行い得られたシンドロームは誤り位置（0なら誤りなし）を示します。拡張ハミングではさらに全体パリティを持ち、シンドロームと全体パリティの組合せで「単一訂正」「二重検出」「誤りなし」を区別します。

FAQ