応用情報技術者 2023年 秋期 午前2 問04

二次元パリティ【午前2解説】

正解の理由

解法ステップ

1. 行ごとのパリティ（各行のパリティビット）と列ごとのパリティ（各列のパリティビット）をチェックする。
2. パリティが不一致になっている行と列をそれぞれ特定する。
3. 不一致の行と不一致の列の交差セルが誤り位置になるため、そのビットを反転すれば訂正できる。
   この手順で確実に位置が一意に決まるのは「誤りが単一ビット」の場合のみです。

選択肢別の誤答解説

• ア（1）
  単一ビット誤りは行と列のパリティの交点で確定できるため訂正可能。正答。
• イ（2）
  2ビット誤りは一般に訂正できない。検出される場合もあるが、同じ行内の2ビット誤りや同じ列内の2ビット誤りでは行（または列）のパリティが変化しないため検出されないことがある。さらに、検出できても交差情報から一意に位置を特定できないため訂正不可。
• ウ（3）
  3ビット誤りでは行・列のパリティのパターンが複数の配置で同じになることがあり、訂正はできない。検出できる場合とできない場合の両方があるため誤り。
• エ（4）
  4ビット以上も同様に一般には訂正不能。特に特定パターン（後述）では検出すらされない場合があるため、4ビット訂正可能とはならない。

よくある誤解

1. 「行・列パリティは複数ビット誤りを必ず検出できる」
   → 誤りです。多くの複数ビット誤りは検出されますが、すべては検出できません。例えば長方形の四隅に当たる4ビット誤りは、各行と各列が2回ずつ反転するため行・列のパリティに変化が出ず検出されません。
2. 「検出できれば必ず訂正できる」
   → 誤りです。検出はできても、どのビットを反転すればよいか一意に決定できないケース（例えば2ビット誤りで異なる2行・2列が反転した場合）では訂正できません。

補足コラム

• 二次元パリティは実装が簡単で単一ビット誤りの訂正に有効です。耐故障性が求められる簡易なシステムでよく使われます。
• より高い訂正能力が必要ならばハミング符号（1ビット訂正＋2ビット検出など）や巡回冗長検査（CRC）・一般的な誤り訂正符号（Reed–Solomon、LDPC等）の採用を検討します。
• 二次元パリティに「全体パリティ（全ビットのパリティ）」を追加すると、奇数個の誤りは検出しやすくなりますが、特定の偶数ビットパターン（例：長方形の4ビット）は依然として検出不能になる場合があります。

FAQ