はみんぐきょり
同じ長さの2つのビット列(または文字列)で、同じ位置の値が異なる箇所の数。2つのビット列の排他的論理和をとったときの1の個数に等しい。例えば 1011010 と 0110011 のハミング距離は4である。符号の中の2つの符号語の間の距離のうち最小のものを最小ハミング距離といい、最小ハミング距離がdの符号は、d − 1 ビットまでの誤りを検出でき、(d − 1) ÷ 2 の切り捨てのビット数までの誤りを訂正できる。
「ハミング距離」は、1分野の3問の練習問題に出てきます(情報理論と符号の基礎など)。
この用語の分野: 情報理論と符号の基礎
符号語どうしが離れているほど、誤りで別の符号語に変わりにくくなります。最小ハミング距離がdの符号では、d − 1 ビット以下の誤りでは別の符号語にならないので検出でき、誤りが (d − 1) ÷ 2 以下なら、受信語に最も近い符号語が元の符号語なので訂正できます。例えば、同じビットを3回送る繰り返し符号は d = 3 で、1ビットの誤りを多数決で訂正できます。
どの2つの符号語の排他的論理和も符号語になる線形符号では、2つの符号語の距離は、その排他的論理和である符号語の1の個数に等しくなります。そのため、最小ハミング距離は、0以外の符号語の1の個数(重み)の最小値として求められ、すべての組を比べる必要がありません。
ハミング距離は、2つのデータの違いを数える一般的な尺度として使われます。PUF(物理的複製困難関数)の評価では、異なるチップの応答の間のハミング距離が全ビットの50%に近いほど、個体を区別しやすいとされます。また、状態機械の符号化で、隣り合う状態のハミング距離を1にしておくと、遷移のときに変わるビットが少なくなります。
正解：C. 4
ハミング距離は、同じ位置のビットが異なる箇所の数です。2つの排他的論理和は 1101001 で、1の個数が4なので、ハミング距離は4です。1ビットずつ比べると、1、2、4、7ビット目が異なります。
正解：A. 検出は4ビットまで、訂正は2ビットまで
最小ハミング距離がdの符号では、d − 1 ビットまでの誤りなら、ほかの符号語に変わってしまうことがないので、検出できます。訂正では、受信したビット列に最も近い符号語に直すので、誤りが (d − 1) ÷ 2 の切り捨て以下なら、元の符号語が最も近いまま残ります。d = 5 では、検出は4ビットまで、訂正は2ビットまでです。
別のものです。ハミング距離は2つのビット列の違いを数える尺度で、ハミング符号は、最小ハミング距離が3になるように作った、1ビットの誤りを訂正できる符号です。どちらもハミングの名に由来します。
ハミング距離は、同じ長さのものどうしでしか定義されません。文字の挿入や削除も含めて違いを数えたいときは、編集距離(レーベンシュタイン距離)を使います。
ハミング距離は、同じ位置のビットが異なる箇所の数です。
2つの7ビットの符号語 1011010 と 0110011 のハミング距離はどれか。最小ハミング距離がdの符号では、d − 1 ビットまでの誤りなら、ほかの符号語に変わってしまうことがないので、検出できます。
ある符号の最小ハミング距離(どの2つの符号語の間のハミング距離のうちの最小値)が5である。誤りの検出だけに使う場合と、…6つの組のハミング距離は、00000と11110、01011と10101の組が4で、ほかの4つの組が3なので、最小ハミング距離は3です。
4つの符号語 00000、01011、10101、11110 からなる符号の、最小ハミング距離と、確実に訂正できる誤り…Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。
可逆圧縮 クラフトの不等式 情報エントロピー 情報量 接頭符号 前方誤り訂正(FEC) 相互情報量 二元対称通信路 ハフマン符号 ハミング符号