令和4年度 I-2-4

解説

この問題で問われていること

2つのビット列間のハミング距離の計算(ア)、および情報ビットX1〜X4に検査ビットX5〜X7を付加した符号において、受信ビット列「1000010」から高々1ビットの誤りを訂正して送信ビット列を求める問題(イ)。

解き方

① ハミング距離=異なるビットの数。受信したX1〜X4からX5〜X7を再計算(mod 2は偶数→0、奇数→1)し、1つだけ合わなければ、その検査ビット自体の誤り
② ア: 1110101と1001111は2・3・4・6番目が異なり4。イ: 1000010でX5=0、X6=1は一致、X7=1+0+0=1が受信値0と不一致→X7を直して1000011
③ ⑤

正解が正しい理由

アについて、「1110101」と「1001111」を位置ごとに比較すると、2・3・4・6番目のビットが異なっており、ハミング距離は4である。イについて、受信ビット列「1000010」(X1〜X7=1,0,0,0,0,1,0)に対し、まずX1〜X4がすべて正しいと仮定してX5=X2+X3+X4=0、X6=X1+X3+X4=1、X7=X1+X2+X4=1を計算すると、受信したX5(0)・X6(1)とは一致するが、受信したX7(0)とは一致しない。X5・X6が一致しX7のみ不一致ということは、誤りはX7の1ビットのみであると判断できる(X1〜X4のいずれかが誤りであれば、複数の検査式で不一致が生じるはずである)。したがって送信ビット列はX1〜X4とX5・X6を受信値のまま(1,0,0,0,0,1)とし、X7だけを計算値の1に訂正した「1000011」となる。以上よりア=4、イ=「1000011」の組合せである⑤が正しい。

この問題で必要な基礎

■ mod 2の足し算
「(mod 2)」は2で割った余りを表すので、足した結果が偶数なら0、奇数なら1になります。例えばX1+X3+X4=1+0+0=1なら1、1+1+0=2なら0です。

各選択肢について

• ① アは正しいが、イの「0000010」はX1を受信値(1)から0に変更しており、X1のみの誤りと仮定した場合の検算(X6・X7の再計算)が受信値と一致しないため誤り。
• ② アが「5」となっている点、およびイの「1100010」がX2を誤りと仮定した場合の検算(X5の再計算)が受信値と一致しない点の両方で誤り。
• ③ アは正しいが、イの「1001010」はX3を誤りと仮定しており、その場合の検算(X5の再計算)が受信値と一致しないため誤り。
• ④ アが「5」となっている点、およびイの「1000110」がX5を受信値(0)から1に変更しているが、X1〜X4を正しいとした場合の期待値(0)と一致しないため誤り。
• ⑤ ア=4(位置ごとの比較で異なるビットが4か所)、イ=「1000011」(X7のみを検算値に訂正した結果)が、ハミング距離の定義および誤り訂正の手順と一致しており、これが正答。

覚えるべきポイント

検査ビットを用いた誤り訂正では、受信したX1〜X4が正しいと仮定して検査式(X5, X6, X7)を再計算し、受信値と比較する。一致しない検査式が1つだけならその検査ビット自体の誤り、複数の検査式で不一致が生じるなら、それらに共通して現れる情報ビット(X1〜X4のいずれか)の誤りである、という判断方法を理解しておく。