ハミング距離とは何ですか？

ハミング距離

ハミング距離とは、2つの2進データ文字列を比較するための指標です。 長さが等しい2つのバイナリ列を比較する場合、ハミング距離は2つのビットが異なるビット位置の数です。

2つの列、aとb間のハミング距離はd（a,b）と表記されます。

ハミング距離の計算

2つの文字列のハミング距離を計算するには、(a⊕ b)のXOR演算を行い、結果の文字列にある1の総数を数えます。

例

2つの文字列1101 1001と1001 1101があるとする。

11011001 ⊕ 10011101 = 01000100とする。 これには1が2つ含まれているので、ハミング距離d(11011001, 10011101) = 2。

最小ハミング距離

同じ長さの文字列の集合において、最小ハミング距離とは、その集合内のすべての文字列の組の間で最小のハミング距離です。

例

010, 011, 101 and 111という4つの文字列があるとします。