応用情報技術者 2022年 春期 午前2 問04

ハミング符号の誤り訂正【午前2解説】

正解の理由

解法ステップ

1. 受信符号の各ビットに位置番号を割り当てる（コードの並びは $X_1{X}_2{X}_3{P}_3{X}_4{P}_2{P}_1$）。受信 1110011 なら
   • pos1:$X_1=1$, pos2:$X_2=1$, pos3:$X_3=1$, pos4:$P_3=0$, pos5:$X_4=0$, pos6:$P_2=1$, pos7:$P_1=1$。
2. 各パリティ検査式を受信ビットで評価してシンドロームを求める。
   • $P_1$ 検査：$X_1\oplus X_3\oplus X_4\oplus P_1=1\oplus 1\oplus 0\oplus 1$
     • 計算: $1\oplus 1=0,0\oplus 0=0,0\oplus 1=1$ → 結果 $=1$（不一致）
   • $P_2$ 検査：$X_1\oplus X_2\oplus X_4\oplus P_2=1\oplus 1\oplus 0\oplus 1$
     • 計算: $1\oplus 1=0,0\oplus 0=0,0\oplus 1=1$ → 結果 $=1$
   • $P_3$ 検査：$X_1\oplus X_2\oplus X_3\oplus P_3=1\oplus 1\oplus 1\oplus 0$
     • 計算: $1\oplus 1=0,0\oplus 1=1,1\oplus 0=1$ → 結果 $=1$
3. シンドロームを $(P_3,P_2,P_1)=(1,1,1)$ として、どのビットがその組合せに対応するかを確認する（下記の対応参照）。$(1,1,1)$ は位置1（$X_1$）に対応するため、位置1のビットを反転する。
4. 位置1を $1\to 0$ にすると訂正後符号は 0110011、すなわち選択肢 ア。

選択肢別の誤答解説

• ア（0110011）: 受信 1110011 の位置1を反転した符号。上記のシンドローム $(1,1,1)$ と一致するので正しい。
• イ（1010011）: 受信から見ると位置2 を反転した結果（pos2: $1\to 0$）。位置2 に誤りがある場合のシンドロームは $(P_3,P_2,P_1)=(1,1,0)$ となるため、今回の $(1,1,1)$ と不一致で誤り。
• ウ（1100011）: 位置3 を反転した結果（pos3: $1\to 0$）。位置3 のシンドロームは $(1,0,1)$ であり、今回の $(1,1,1)$ と不一致。
• エ（1110111）: 位置5（$X_4$）を反転した結果（pos5: $0\to 1$）。位置5 のシンドロームは $(0,1,1)$ であり、今回の $(1,1,1)$ と不一致。

よくある誤解

• パリティ検査の順序を逆に扱う：$P_1,P_2,P_3$ の検査結果をどの順序で並べるかで示す二進数が変わり、誤り位置を誤判定することがある。問題でどの検査がどのビットに対応しているかを明確にしてから対応付けすること。
• 計算を省略して「1つだけ違うビットを見つける」だけで終える：実際には各検査式の XOR を具体的に計算し、どの検査が1であるか（シンドローム）を確かめる必要がある。
• パリティビットとデータビットの配置を混同する：問題文の符号配置（ここでは $X_1{X}_2{X}_3{P}_3{X}_4{P}_2{P}_1$）を読み違えると検査の対象集合がずれ、誤った位置を導いてしまう。

補足コラム

• 各パリティ検査は「どの位置を監視しているか」を示す列（列ベクトル）を持ちます。誤りが1ビットであれば、その列ベクトルがシンドロームになります。
• 実務的には送信側で各パリティビットを設定する際、検査式（ここでは $X_1\oplus X_3\oplus X_4\oplus P_1=0$ 等）を満たすように $P_i$ を決めます。受信側は同じ式に受信ビットを代入してシンドロームを得ます。
• シンドロームが $000$ の場合は「誤りなし（または偶数個の誤りで検出できない場合）」を意味し、非ゼロなら単一ビットの位置を指します。

FAQ