次の記述の， に入る値の組合せとして，最も適切なものはどれか。
同じ長さの2つのビット列に対して，対応する位置のビットが異なっている箇所の数をそれらのハミング距離と呼ぶ。ビット列「0101011」と「0110000」のハミング距離は，表1のように考えると4であり，ビット列「1110001」と「0001110」のハミング距離は， ア である。4ビットの情報ビット列「X1 X2 X3 X4」に対して，「X5 X6 X7」をX5 = X2 + X3 + X4 mod 2，X6 = X1 + X3 + X4 mod 2，X7 = X1 + X2 + X4 mod 2（mod 2は整数を2で割った余りを表す）と置き，これらを付加したビット列「X1 X2 X3 X4 X5 X6 X7」を考えると，任意の2つのビット列のハミング距離が3以上であることが知られている。このビット列「X1 X2 X3 X4 X5 X6 X7」を送信し通信を行ったときに，通信過程で高々1ビットしか通信の誤りが起こらないという仮定の下で，受信ビット列が「0100110」であったとき，表2のように考えると「1100110」が送信ビット列であることがわかる。同じ仮定の下で，受信ビット列が「1001010」であったとき，送信ビット列は， イ であることがわかる。
表1 ハミング距離の計算
表2 受信ビット列が「0100110」の場合
| ア | イ | |
| ① | 5 | 「1001010」 |
| ② | 5 | 「0001010」 |
| ③ | 5 | 「1101010」 |
| ④ | 7 | 「1001010」 |
| ⑤ | 7 | 「1011010」 |
解答・解説
解答
⑤
解説
- 「1110001」と「0001110」とでは，7列全てが異なっていますので，ハミング距離は7になります。
- 選択肢にある4ビットの情報列（頭4桁）およびそこから算出される付加ビット列はそれぞれ，
①④「1001」→「100」
② 「0001」→「111」
③ 「1101」→「001」
⑤ 「1011」→「010」
となり，受信ビット列「1001010」と1ビットの通信誤りかつ付加ビットが一致する「1011010」が送信ビット列であることがわかります。
参考情報
過去の出題
なし
オンラインテキスト
（準備中）
