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

ハミング符号（SEC‑DED）【午前2解説】

正解の理由

解法ステップ

1. 要求機能を整理：1ビット訂正（correct）かつ2ビット検出（detect）が必要。
2. 各選択肢の能力を思い出す：
   • 単純パリティ（偶数パリティ）は誤り検出のみ（奇数個の誤りを検出）、訂正不可。
   • チェックサムはブロック検出向けで訂正不可。
   • ハミング符号は単一訂正が基本。拡張（全体パリティ追加）で二重誤り検出を追加できる。
3. 要件に合致するのはハミング符号の拡張（SEC‑DED）であると判断し、エを選ぶ。

選択肢別の誤答解説

• ア: 偶数パリティ
  偶数パリティはビット列のパリティ（ビット1の個数が偶数かどうか）を保持し、誤りが発生してビット1の個数が奇数になれば検出できます。したがって「奇数個（例：1ビット）の誤りは検出できる」が、誤りの位置が分からないため訂正は不可能です。2ビット誤り（偶数個）はパリティが変わらないことがあり検出できない場合がある点にも注意。
• イ: 垂直パリティ
  「垂直パリティ」は一般に各ビット位置（例えば各バイトの同じビット位置）ごとのパリティを指しますが、単独では誤り位置を確定して1ビット訂正するのは難しいです。行と列の両方でパリティを取る2次元パリティ（縦横パリティ）なら単一ビットの訂正が可能な場合がありますが、それでも拡張ハミングのように全ての2ビット誤りを確実に検出する保証はありません。また問題文は単に「垂直パリティ」としており、それだけでSEC‑DEDを満たすとは言えません。
• ウ: チェックサム
  チェックサム（和を取る方式）はブロック伝送やストレージの誤り検出に使われますが、誤りの訂正機能はありません。複数ビットの誤りを検出できる場合もありますが、全ての2ビット誤りを必ず検出するとは限らず、また訂正はできません。

よくある誤解

• 「ハミング符号は2ビット誤りも検出できる」
  → 標準ハミング符号は主に単一ビット訂正（SEC）を目的としています。全ての2ビット誤りを確実に検出するためには全体パリティを追加した拡張ハミング（SEC‑DED）が必要です。
• 「偶数パリティは1ビット誤りの検出が限定的」
  → 誤った表現です。偶数パリティは1ビット（奇数個の誤り）を確実に検出できますが、誤りの位置が分からないため訂正はできません。偶数個の誤り（例：2ビット）は検出できない場合があります。
• 「チェックサムで訂正できる」
  → チェックサムは検出用途であり、訂正機構は含まれません。訂正が必要なら別途冗長情報と復号手順が要ります。

補足コラム

• ハミング符号の必要なパリティビット数の目安は、データビット数 $m$ に対して次を満たす最小の $r$：
  $$2^r\ge m+r+1$$
  です。これは単一誤り（$m+r$ ビット中どのビットか）を識別するための組み合わせ数の条件です。拡張ハミング（SEC‑DED）ではさらに全体パリティビットを1つ追加するため、ECCでよく使われる設定の例として「64ビットデータに対して7個のチェックビット（Hamming）＋1個の全体パリティ＝合計8ビットの冗長で64ビットを保護（計72ビット）」という実装が一般的です。
• 拡張ハミングの振る舞い（概念）
  • シンドローム（parity-check結果）が 0 かつ全体パリティが偶数：エラー無し
  • シンドロームが非ゼロかつ全体パリティが奇数：単一ビット誤り（シンドロームで位置特定→訂正）
  • シンドロームが非ゼロかつ全体パリティが偶数：二重ビット誤り（検出のみ、訂正不可）
  • シンドロームが 0 かつ全体パリティが奇数：パリティビット単独の誤り（訂正可）

FAQ