問２ ４ビットから成る情報ビット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が、送信符号と高々１ビットしか異ならないとき、
(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であるとき、正しい情報ビットはどれか。ここでａmodｂは、ａをｂで割った余りを表す。
ア 0100 イ 1000
ウ 1100 エ 1101
解説
パリティ符号による誤り訂正の問題です。
問題文では「１ビットしか異ならないとき、正しい情報ビットを求めることが可能である」としています。なので「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
２番目と３番目の式の結果が１になりました。つまり、「２番目と３番目の式、両方に登場するビットを反転すれば、３つの式の答えが０になる」のです。それでは、２番と３番に登場するビットを見てみましょう。
( y1 + y2 + y3 + y5 )mod2
( y1 + y2 + y4 + y6 )mod2
( y2 + y3 + y4 + y7 )mod2
上記は、２番と３番の式に登場するビットを赤くしてみた物です。y2とy4が２番と３番の式に登場して「どっち？」と思うかもしれませんが、よく見るとy2は１番～３番全ての式に登場しているので、y2を反転すると１番の式の解が１となってしまうため、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＝1101010」なので、エが正解になります。
余談
本当に、この式で１ビットの誤りを発見できるのか？例えば、全てのビットが０の場合に、１ビットずつ間違いだったらどうなるでしょうか？
エラーなし 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
１ビットだけ誤りの場合は、解のパターンによって、どのビットが誤りか綺麗に特定できるようになっています。すごいですね！
以下のサイトに、詳しく解説してくれていますが、管理人にはさっぱり理解できませんでした！
誤り訂正符号の実例
最終更新：2013年09月15日 00:06
