正解 エ 次の問題へ

問2 4ビットから成る情報ビットx1 x2 x3 x4に対して、
(x1 + x2 + x3 + x5)mod2 = 0
(x1 + x2 + x4 + x6)mod2 = 0
(x2 + x3 + x4 + x7)mod2 = 0
を満たす冗長ビットx5 x6 x7を付加した符号x1 x2 x3 x4 x5 x6 x7を送信する。
 受信符号y1 y2 y3 y4 y5 y6 y7が、送信符号と高々1ビットしか異ならないとき、
(y1 + y2 + y3 + y5)mod2
(y1 + y2 + y4 + y6)mod2
(y2 + y3 + y4 + y7)mod2
がそれぞれ0になるかどうかによって、正しい情報ビットx1 x2 x3 x4を求めることが可能である。y1 y2 y3 y4 y5 y6 y7=1100010であるとき、正しい情報ビットはどれか。ここでamodbは、aをbで割った余りを表す。

ア 0100   イ 1000
ウ 1100   エ 1101

解説

パリティ符号による誤り訂正の問題です。

 問題文では「1ビットしか異ならないとき、正しい情報ビットを求めることが可能である」としています。なので「y1 y2 y3 y4 y5 y6 y7=1100010」をそのまま、上記の式に当てはめれば答えは分かる筈です。

(y1 + y2 + y3 + y5)mod2
(y1 + y2 + y4 + y6)mod2
(y2 + y3 + y4 + y7)mod2

(1 + 1 + 0 + 0)mod2 = 0
(1 + 1 + 0 + 1)mod2 = 1
(1 + 0 + 0 + 0)mod2 = 1
 2番目と3番目の式の結果が1になりました。つまり、「 2番目と3番目の式、両方に登場するビットを反転すれば、3つの式の答えが0になる 」のです。それでは、2番と3番に登場するビットを見てみましょう。

( y1 + y2 + y3 + y5 )mod2
( y1 + y2 + y4 + y6 )mod2
( y2 + y3 + y4 + y7 )mod2
 上記は、2番と3番の式に登場するビットを赤くしてみた物です。 y2 y4 が2番と3番の式に登場して「どっち?」と思うかもしれませんが、よく見ると y2 は1番~3番全ての式に登場しているので、 y2 を反転すると1番の式の解が1となってしまうため、 y2 は反転できません。

 すると、残るのは y4 です。 y4 を反転させると以下のようになります。
(1 + 1 + 0 + 0)mod2 = 0
(1 + 1 + 0 + 1)mod2 = 1
(1 + 0 + 0 + 0)mod2 = 1

(1 + 1 + 0 + 0)mod2 = 0
(1 + 1 + 1 + 1)mod2 = 0
(1 + 0 + 1 + 0)mod2 = 0

正解は、 y4 を反転させた「y1 y2 y3 y4 y5 y6 y7=110 1 010」なので、エが正解になります。

余談

 本当に、この式で1ビットの誤りを発見できるのか?例えば、全てのビットが0の場合に、1ビットずつ間違いだったらどうなるでしょうか?
エラーなし 000
(0 + 0 + 0 + 0)mod2 = 0
(0 + 0 + 0 + 0)mod2 = 0
(0 + 0 + 0 + 0)mod2 = 0

y1が誤りの場合 110
(1 + 0 + 0 + 0)mod2 = 1
(1 + 0 + 0 + 0)mod2 = 1
(0 + 0 + 0 + 0)mod2 = 0

y2が誤りの場合 111
(0 + 1 + 0 + 0)mod2 = 1
(0 + 1 + 0 + 0)mod2 = 1
(1 + 0 + 0 + 0)mod2 = 1

y3が誤りの場合 101
(0 + 0 + 1 + 0)mod2 = 1
(0 + 0 + 0 + 0)mod2 = 0
(0 + 1 + 0 + 0)mod2 = 1

y4が誤りの場合 011
(0 + 0 + 0 + 0)mod2 = 1
(0 + 0 + 1 + 0)mod2 = 0
(0 + 0 + 1 + 0)mod2 = 1

y5が誤りの場合 100
(0 + 0 + 0 + 1)mod2 = 1
(0 + 0 + 0 + 0)mod2 = 0
(0 + 0 + 0 + 0)mod2 = 0

y6が誤りの場合 010
(0 + 0 + 0 + 0)mod2 = 0
(0 + 0 + 0 + 1)mod2 = 1
(0 + 0 + 0 + 0)mod2 = 0

y7が誤りの場合 001
(0 + 0 + 0 + 0)mod2 = 0
(0 + 0 + 0 + 0)mod2 = 0
(0 + 0 + 0 + 1)mod2 = 1

 1ビットだけ誤りの場合は、解のパターンによって、どのビットが誤りか綺麗に特定できるようになっています。すごいですね!
以下のサイトに、詳しく解説してくれていますが、管理人にはさっぱり理解できませんでした!
誤り訂正符号の実例