情報理論と符号の基礎
4つの符号語 00000、01011、10101、11110 からなる符号の、最小ハミング距離と、確実に訂正できる誤りのビット数の組み合わせとして、正しいものはどれか。
- A最小ハミング距離は4、1ビットまで訂正できる
- B最小ハミング距離は3、2ビットまで訂正できる
- C最小ハミング距離は3、1ビットまで訂正できる
答えと解説を見る
正解：C. 最小ハミング距離は3、1ビットまで訂正できる
6つの組のハミング距離は、00000と11110、01011と10101の組が4で、ほかの4つの組が3なので、最小ハミング距離は3です。訂正できるのは (3 − 1) ÷ 2 = 1 ビットまでです。この符号は、どの2つの符号語の排他的論理和も符号語になる線形符号なので、0以外の符号語の1の個数の最小値として、3を求めることもできます。
- A. 4は距離の最大値です。訂正できる誤りの数は、最も近い2つの符号語の距離、つまり最小値で決まります。
- B. 2は、検出だけに使う場合の d − 1 です。訂正できるのは (d − 1) ÷ 2 の切り捨てまでです。
- C. 正しい。最小ハミング距離が3なので、1ビットの誤りまで訂正できます。