平成24年度春期 プロジェクトマネージャ 午前Ⅰ 問2

パリティ検査と誤り訂正

パリティの計算方法と、誤りの検出・訂正を区別する観点を準備しよう。

この問題で問われていること

異なる位置のビット反転を、パリティ検査の結果だけで区別できる条件を調べられるか。

パリティ検査と誤り訂正

異なる位置のビット反転を、パリティ検査の結果だけで区別できる条件を調べられるか。

確認ポイント

• 偶数パリティと奇数パリティでは、検査対象のビットから何を計算し、何と照合するか。
• 誤りがあると分かることと、元のビット列を一意に復元できることはどう違うか。
• 小さなビット列で反転する位置や個数を変え、異なる反転パターンが同じ検査結果になる場合があるか比較できるか。

正解

ア

解説

添付の公式解答の問2は「ア」です。図は添付の公式問題ページ（question-3.png）の問2を参照する。図では，各行・各列について，パリティビットを含む1の個数が偶数になっている。1ビットが反転すると，対応する行と列の両方で偶数という条件が崩れるため，その交点から誤り位置を特定して訂正できる。複数ビットの誤りでは，位置が一意に定まらない場合やパリティが変わらない場合がある。したがって，確実に訂正できるのは1ビットまでです。

添付の公式解答の問2は「ア」です。図は添付の公式問題ページ（question-3.png）の問2を参照する。図では，各行・各列について，パリティビットを含む1の個数が偶数になっている。1ビットが反転すると，対応する行と列の両方で偶数という条件が崩れるため，その交点から誤り位置を特定して訂正できる。複数ビットの誤りでは，位置が一意に定まらない場合やパリティが変わらない場合がある。したがって，確実に訂正できるのは1ビットまでです。

選択肢ア（正解）

正しい。1ビットの誤りなら，そのビットが属する行と列でパリティが不一致になる。その交点を誤り位置として特定し，ビットを反転して訂正できる。

選択肢イ

誤り。例えば，異なる行・列で2ビットが誤ると，不一致となる2行と2列の交点に複数の位置の組合せが考えられ，誤り位置を一意に特定できない。

選択肢ウ

誤り。例えば，長方形の四隅のうち3か所が誤ると，パリティの不一致は残りの1か所だけが誤った場合と同じになる。したがって，3ビットの誤りを確実に訂正できない。

選択肢エ

誤り。例えば，長方形の四隅で4ビットが誤ると，関係する各行・各列で2ビットずつ反転するため，パリティが変わらず，誤りを検出できない。

学習のポイント

異なる位置のビット反転を、パリティ検査の結果だけで区別できる条件を調べられるか。