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

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

正解の理由

解法ステップ

1. 受信ビットを左から $x_1,\dots ,x_7$ と読み取る（ここでは $x=(1,0,0,0,1,0,1)$）。
2. 式に従ってシンドロームを求める（計算は mod 2）：
   • $c_0=x_1+x_3+x_5+x_7=1+0+1+1\equiv 1$
   • $c_1=x_2+x_3+x_6+x_7=0+0+0+1\equiv 1$
   • $c_2=x_4+x_5+x_6+x_7=0+1+0+1\equiv 0$
3. シンドロームから誤り位置を求める：
   • $i=c_0+2c_1+4c_2=1+2\cdot 1+4\cdot 0=3$
4. 左から第3ビットを反転する：
   • 受信 1000101 → 1(0→1)0 0101 = 1010101
5. よって訂正後の符号語は選択肢 エ に一致する。

選択肢別の誤答解説

• ア: 1000001
  これは受信語の第5ビット（左から5番目：1→0）を反転した結果であり、シンドロームが示す第3ビット反転とは異なります。したがって不正解。
• イ: 1000101
  受信語そのまま。シンドロームが非ゼロであるため誤りが検出されており、そのままは正しくありません。
• ウ: 1001101
  これは左から第4ビットを反転した結果（第4ビット 0→1）であり、正しい訂正位置（第3ビット）とは一致しません。
• エ: 1010101
  左から第3ビットを反転した結果で、シンドロームに基づく正しい訂正操作に一致します。したがって正解。

よくある誤解

1. 「シンドロームが0でなければ必ず誤訂正される」
   → 誤りです。シンドロームが0でなければ何らかの誤りがあることを示します。ハミング(7,4)は最小ハミング距離が3なので、シンドロームが0になる誤り（検出されない誤り）は重み3以上の誤りに限られ、1ビット・2ビット誤りはシンドローム0にはなりません。
2. 「ビット位置の番号付け方向を誤る」
   → 問題ごとに「左から何ビット目」と定義される方向を必ず確認してください。方向を間違えると全く異なる位置を反転してしまいます。

補足コラム

• 位置1の検査: $x_1,x_3,x_5,x_7$（$c_0$）
• 位置2の検査: $x_2,x_3,x_6,x_7$（$c_1$）
• 位置4の検査: $x_4,x_5,x_6,x_7$（$c_2$） となっています。シンドロームのビット列 $(c_2,c_1,c_0)$ を二進数と見なすと誤り位置を直接示します（ここでは $c_0$ が最下位ビット扱い）。

FAQ