平成24年度 秋期 午前 問3
基礎理論
ハミング符号に関する問題
4 ビットから成る情報ビット x1 x2 x3 x4 に対して，(x1＋x2＋x3＋x5) mod 2＝0，(x1＋x2＋x4＋x6) mod 2＝0，(x2＋x3＋x4＋x7) mod 2＝0 を満たす冗長ビット x5 x6 x7 を付加した符号 x1 x2 x3 x4 x5 x6 x7 を送信する。受信符号 y1 y2 y3 y4 y5 y6 y7 が，送信符号と高々 1 ビットしか異ならないとき，(y1＋y2＋y3＋y5) mod 2，(y1＋y2＋y4＋y6) mod 2，(y2＋y3＋y4＋y7) mod 2 がそれぞれ 0 になるかどうかによって，正しい情報ビット x1 x2 x3 x4 を求めることが可能である。y1 y2 y3 y4 y5 y6 y7＝1100010 であるとき，正しい情報ビットはどれか。ここで，a mod b は，a を b で割った余りを表す。
- ア0100
- イ1000
- ウ1100
- エ1101
答えと解説を見る
✓ これが正解エ1101
解説
合わない検査式の組合せが、狂ったビットを指します。
設問は、1 ビットまでの誤りを直せる符号を受け取り、正しい情報ビットを答えさせています。決め手は、三本の検査式のうちどれが余り 0 にならないかという一点です。受信符号を並べると先頭から 1、1、0、0、0、1、0 ですから、これを三本に入れていきます。一本目は 1 と 1 と 0 と 0 で和が 2、割った余りは 0 ですから合っています。二本目は 1 と 1 と 0 と 1 で和が 3、三本目は 1 と 0 と 0 と 0 で和が 1 となり、どちらも余りが 1 で合いません。次に、二本目と三本目の両方に現れて一本目には現れないビットを探します。一本目に入るのは先頭から数えて 1 番目と 2 番目と 3 番目と 5 番目、二本目は 1 番目と 2 番目と 4 番目と 6 番目、三本目は 2 番目と 3 番目と 4 番目と 7 番目です。二本目と三本目に共通するのは 2 番目と 4 番目ですが、2 番目は一本目にも現れるので外れ、残るのは 4 番目だけです。そこを 0 から 1 に裏返せば、情報ビットは 1、1、0、1 になります。訂正後の符号を三本に入れ直すと、いずれも余りが 0 に戻ることまで確かめられます。ハミング符号のように、偶奇を調べるパリティチェックを組み合わせて位置まで絞り込む考え方です。
ほかの選択肢はなぜ違うのか
- ア0100：先頭のビットを裏返した形です。そのビットは一本目と二本目に現れますが、一本目はもともと余りが 0 で合っているので、ここを動かすと合っていた側が崩れてしまいます。
- イ1000：二番目のビットを裏返した形です。このビットは三本すべてに現れるため、動かせば一本目の結果まで変わります。合う式と合わない式がこのように分かれた理由を説明できません。
- ウ1100：受信した符号の前半四桁をそのまま写しただけで、訂正をしていない形です。この並びのままでは二本目と三本目の余りが 1 のまま残り、送信された符号の条件を満たしません。
出典：平成24年度 秋期 応用情報技術者試験 午前 問3
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）