* 正解 エ [[問3へ>資格試験/情報処理技術者試験/高度共通午前1/過去問2012年秋午前1/問3]] #include(資格試験/情報処理技術者試験/高度共通午前1/過去問2012年秋午前1/問2) * 解説 パリティ符号による誤り訂正の問題です。 問題文では「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 = &color(red){1} >(1 + 0 + 0 + 0)mod2 = &color(red){1} 2番目と3番目の式の結果が1になりました。つまり、「&bold(){2番目と3番目の式、両方に登場するビットを反転すれば、3つの式の答えが0になる}」のです。それでは、2番と3番に登場するビットを見てみましょう。 >( y1 + &color(red){y2} + y3 + y5 )mod2 >( y1 + &color(red){y2} + &color(red){y4} + y6 )mod2 >( &color(red){y2} + y3 + &color(red){y4} + y7 )mod2 上記は、2番と3番の式に登場するビットを赤くしてみた物です。&bold(){&color(red){y2}}と&bold(){&color(red){y4}}が2番と3番の式に登場して「どっち?」と思うかもしれませんが、よく見ると&bold(){&color(red){y2}}は1番~3番全ての式に登場しているので、&bold(){&color(red){y2}}を反転すると1番の式の解が1となってしまうため、&bold(){&color(red){y2}}は反転できません。 すると、残るのは&bold(){&color(red){y4}}です。&bold(){&color(red){y4}}を反転させると以下のようになります。 >(1 + 1 + 0 + 0)mod2 = 0 >(1 + 1 + 0 + 1)mod2 = &color(red){1} >(1 + 0 + 0 + 0)mod2 = &color(red){1} >↓ >(1 + 1 + 0 + 0)mod2 = 0 >(1 + 1 + &color(red){1} + 1)mod2 = &color(red){0} >(1 + 0 + &color(red){1} + 0)mod2 = &color(red){0} 正解は、&bold(){&color(red){y4}}を反転させた「y1 y2 y3 &bold(){&color(red){y4}} y5 y6 y7=110&bold(){&color(red){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ビットだけ誤りの場合は、解のパターンによって、どのビットが誤りか綺麗に特定できるようになっています。すごいですね! 以下のサイトに、詳しく解説してくれていますが、管理人にはさっぱり理解できませんでした! [[誤り訂正符号の実例>http://www.math.kindai.ac.jp/~chinen/err_corr_f/err_corr.html]] [[問3へ>資格試験/情報処理技術者試験/高度共通午前1/過去問2012年秋午前1/問3]] [[問2へ>資格試験/情報処理技術者試験/高度共通午前1/過去問2012年秋午前1/問2]]