令和元年度 I-2-5

解説

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

2つのビット列のハミング距離と、1ビット誤りを含む受信ビット列から元の送信ビット列を求める問題。

解き方

① ハミング距離=異なるビットの数。送信ビット列は、付加ビット X5〜X7 が規則どおりになる列を探す
② 1110001 と 0001110 は7ビット全部が異なる → ア=7(④⑤)。受信1001010の X3 を1に直した 1011010 は X5=0+1+1=0、X6=1+1+1=1、X7=1+0+1=0 で規則どおり(④の1001010のままでは X6=0 で合わない)
③ ⑤

正解が正しい理由

「1110001」と「0001110」は全7ビットが異なるのでハミング距離は7(ア)。受信「1001010」の情報ビット1001から付加ビットを計算するとX5=0,X6=0,X7=1となり、受信した010と一致しないので誤りがある。X3のみ誤りと仮定して1011にすると、X5=0+1+1=0、X6=1+1+1=1、X7=1+0+1=0で受信の010と一致する。よって送信ビット列は「1011010」(イ)。したがって⑤が正しい。

各選択肢について

• ① アが5となっている点が誤り。全7ビットが異なる。
• ② アが5となっている点が誤り。
• ③ アが5となっている点が誤り。
• ④ 受信列そのままでは付加ビットが規則と合わず、誤りが訂正されていない。
• ⑤ ア=7、イ=1011010の組合せが正しく、これが正答。

覚えるべきポイント

ハミング距離が3以上の符号は1ビットの誤りを訂正できる。1ビットずつ反転させて、付加ビットの規則を満たす列を探せばよい。