応用情報技術者試験 令和4年春 午前問4 解説付き過去問
問題
ハミング符号とは、データに冗長ビットを付加して、1ビットの誤りを訂正できるようにしたものである。
ここでは、X1，X2，X3，X4の4ビットから成るデータに、3ビットの冗長ビットP3，P2，P1を付加したハミング符号 X1X2X3P3X4P2P1を考える。
付加ビットP1，P2，P3は、それぞれ
X1⊕X3⊕X4⊕P1＝0
X1⊕X2⊕X4⊕P2＝0
X1⊕X2⊕X3⊕P3＝0
となるように決める。ここで⊕は排他的論理和を表す。
ハミング符号 1110011には1ビットの誤りが存在する。 誤りビットを訂正したハミング符号はどれか。
X1⊕X3⊕X4⊕P1＝0
X1⊕X2⊕X4⊕P2＝0
X1⊕X2⊕X3⊕P3＝0
となるように決める。ここで⊕は排他的論理和を表す。
ハミング符号 1110011には1ビットの誤りが存在する。 誤りビットを訂正したハミング符号はどれか。
正解
解説
この問題は、ハミング符号における1ビットの誤り訂正機能と、誤りがある場合の訂正方法について問うものです。ハミング符号は冗長ビットを使用して、データ伝送中に発生する可能性のある誤りを検出し、訂正するための手法です。
- ハミング符号の基本構造
ハミング符号では、元のデータビットに対して特定の冗長ビット（パリティビット）を追加します。例えば、X1, X2, X3, X4の4ビットのデータに対して、P1, P2, P3の3ビットのパリティが加えられます。
これらのパリティビットは、特定のデータビットの組み合わせによって計算され、全体として偶数パリティ（XOR演算の結果が0になるように）が保たれるように設定されます。この偶数パリティの設定により、データ伝送中に1ビットの誤りが発生した場合にこれを検出し、訂正することが可能です。 - 誤りの検出と訂正
与えられたハミング符号 1110011 に対して、各パリティビットの条件を用いて誤りを検出します。誤りがある場合、対応するパリティビットが1になるはずです。次に、これらのパリティビットの値を用いて、誤っているビットの位置を特定します。
例えば、P1が反転している場合は、X1, X3, X4のいずれか（またはP1自身）に誤りがあることを示します。同様に、P2やP3の値も誤りの位置を特定するのに役立ちます。
この問題では、実際にこれらのパリティ条件を計算し直すことで、最初のビットX1が誤っていることが判明し、訂正後のコードが0110011になることが確認されます。
したがって、誤りビットを正しく訂正したハミング符号は0110011です。この誤り訂正のプロセスは、ハミング符号がどのようにして信頼性の高いデータ通信を実現するかを示す良い例です。