応用情報技術者 2020年 秋期 午前2 問10

単一誤り訂正二重誤り検出【午前2解説】

正解の理由

解法ステップ

1. 問いの要件を整理する：1ビット訂正かつ2ビット検出であること。
2. 各方式の能力を簡単に確認する：
   • 単純なパリティ（奇数/偶数）は「奇数個の誤り」を検出するが訂正不可。
   • 行（水平）パリティは行単位の奇数誤り検出であり単独で1ビット訂正はできない。
   • チェックサムはブロック誤り検出に有効だが、2ビットの検出を完全に保証し訂正する仕組みではない。
   • ハミング符号は1ビット訂正を目的とした符号であり、拡張（全体パリティ追加）すれば2ビット検出も可能になる。
3. よって要件を満たすのはハミング符号（実務的に言えば拡張ハミング／SECDED）：エ を選ぶ。

選択肢別の誤答解説

• ア: 奇数パリティ
  奇数パリティはデータ全体のビット数を奇数に保つため、誤りが奇数個発生した場合に検出できます（1ビット、3ビット…）。しかし訂正機能はなく、2ビット（偶数個）の誤りは検出できない場合があるため要件を満たしません。
• イ: 水平パリティ
  「水平パリティ」は行ごとのパリティです。行単位で奇数個の誤りを検出できますが、単独では1ビットの自動訂正（位置特定して書き直す）はできません。2次元パリティ（行＋列）にすれば1ビット訂正が可能になるケースもありますが、設問の単体記述からは該当しません。
• ウ: チェックサム
  チェックサム（加算和など）は誤り検出に有効ですが、検出能力は方式とエラーの分布に依存し、任意の2ビット誤りを確実に検出する保証や訂正機能はありません。したがって要件を満たしません。
• エ: ハミング符号（エ）
  ハミング符号は元来「1ビット訂正（single-error correction）」を設計目的とした符号です。実務上は全体パリティを加えた拡張ハミング符号（SECDED）として実装され、これにより任意の2ビット誤りを検出しつつ1ビット誤りを訂正できます。よって要件に合致します。

よくある誤解

1. 「パリティは1ビットしか検出できない」
   → 誤りです。奇数（または偶数）パリティはビット反転の回数が奇数か偶数かを判定するため、任意の奇数個の誤り（1、3、5…ビット）を検出できます。ただし訂正はできません。
2. 「標準ハミングは2ビット誤りを検出できない」
   → 理論的にハミング符号（最小距離3）は最大2ビットまで検出可能です。しかし実装上は全体パリティを付加した拡張ハミング（SECDED）を使うことで、2ビット誤り検出と誤訂正の回避を確実にする点が重要です。試験では「ハミング符号＝SECDED を含む利用形態」を想定していることが多い点に注意してください。
3. 「チェックサムは常に多くの誤りを検出する」
   → 実際には誤り検出能力はチェックサムの方法と誤りパターンに依存します。特定の2つのビットが反転してもチェックサムが変わらない場合があり、任意の2ビット誤り検出は保証されません。

補足コラム

• パリティビット数 r はデータビット数 m に対して理論的には次式を満たす必要があります：
  $$2^r\ge m+r+1$$
  これは Hamming 符号が各ビット位置を一意に識別するための条件です。例えば Hamming(7,4) はデータ4ビットに対し3本のパリティビットを持ちます。これをさらに1ビットの全体パリティで拡張すると Hamming(8,4) のような SECDED 構成になります。
• 拡張ハミング（SECDED）の検出ロジック（概念）：
  • シンドローム（パリティ検査結果）がゼロ → エラーなし。
  • シンドロームが非ゼロで全体パリティが不整合 → 単一ビット誤り（位置がシンドロームで特定できる）→ 訂正可能。
  • シンドロームが非ゼロで全体パリティが整合 → 2ビット以上の誤り（特に2ビット誤り）の可能性 → 訂正せず検出のみ。

FAQ