[1]
[[ベクトル]] [CODE(math)@en[[VAR(vector)[v]] = ([VAR[v[SUB[1]]]], [VAR[v[SUB[2]]]], ..., [VAR[v[SUB[[VAR[n]]]]]])]],
[CODE(math)@en[[VAR(vector)[u]] = ([VAR[u[SUB[1]]]], [VAR[u[SUB[2]]]], ..., [VAR[u[SUB[[VAR[n]]]]]])]]
において[[要素]]が等しくない個数、すなわち
[CODE(math)@en[[VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[u]], [VAR(vector)[v]]) = |{[VAR[i]] | [VAR[v[VAR[[SUB[i]]]]]] ≠ [VAR[u[SUB[[VAR[i]]]]]], 1 ≦ [VAR[i]] ≦ [VAR[n]]}|]]
を [CODE(math)@en[[VAR[v]]]] と [CODE(math)@en[[VAR[u]]]]
の[DFN[[RUBYB[ハミング距離] @en[Humming distance]]]]といいます。

[2]
'''定理''': ハミング距離は[[距離の公理]]
= [CODE(math)@en[[VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[u]], [VAR(vector)[v]]) ≧ 0]]
であり、等号成立は [CODE(math)@en[[VAR(vector)[v]] = [VAR(vector)[u]]]]
の時に限る。
= [CODE(math)@en[[VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[u]], [VAR(vector)[v]]) = [VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[v]], [VAR(vector)[u]])]]
([[交換法則]])
= [CODE(math)@en[[VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[u]], [VAR(vector)[v]]) + [VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[v]], [VAR(vector)[w]]) ≧ [VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[u]], [VAR(vector)[w]])]]
([[三角不等式]])

を満たします。


[3]
>>2 の証明

(1), (2) >>1 の定義より明らかである。

(3)
[CODE(math)@en[[VAR(vector)[u]]]],
[CODE(math)@en[[VAR(vector)[v]]]],
[CODE(math)@en[[VAR(vector)[w]]]]
の[[要素]] 
[CODE(math)@en[[VAR[u[SUB[[VAR[i]]]]]]]],
[CODE(math)@en[[VAR[v[SUB[[VAR[i]]]]]]]],
[CODE(math)@en[[VAR[w[SUB[[VAR[i]]]]]]]]
([CODE(math)@en[0 ≦ [VAR[i]] ≦ [VAR[n]]]])
がそれぞれ等しいかどうかで分類すると、
,[CODE(math)@en[[VAR(vector)[u]]]] と [CODE(math)@en[[VAR(vector)[v]]]],[CODE(math)@en[[VAR(vector)[v]]]] と [CODE(math)@en[[VAR(vector)[w]]]],[CODE(math)@en[[VAR(vector)[w]]]] と [CODE(math)@en[[VAR(vector)[u]]]],個数
,[CODE(math)@en[[VAR[u[SUB[[VAR[i]]]]]] = [VAR[v[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[v[SUB[[VAR[i]]]]]] = [VAR[w[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[w[SUB[[VAR[i]]]]]] = [VAR[u[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[a[SUB[1]]]]]]
,[CODE(math)@en[[VAR[u[SUB[[VAR[i]]]]]] = [VAR[v[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[v[SUB[[VAR[i]]]]]] ≠ [VAR[w[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[w[SUB[[VAR[i]]]]]] ≠ [VAR[u[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[a[SUB[2]]]]]]
,[CODE(math)@en[[VAR[u[SUB[[VAR[i]]]]]] ≠ [VAR[v[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[v[SUB[[VAR[i]]]]]] ≠ [VAR[w[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[w[SUB[[VAR[i]]]]]] = [VAR[u[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[a[SUB[3]]]]]]
,[CODE(math)@en[[VAR[u[SUB[[VAR[i]]]]]] ≠ [VAR[v[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[v[SUB[[VAR[i]]]]]] = [VAR[w[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[w[SUB[[VAR[i]]]]]] ≠ [VAR[u[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[a[SUB[4]]]]]]
,[CODE(math)@en[[VAR[u[SUB[[VAR[i]]]]]] ≠ [VAR[v[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[v[SUB[[VAR[i]]]]]] ≠ [VAR[w[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[w[SUB[[VAR[i]]]]]] ≠ [VAR[u[SUB[[VAR[i]]]]]]]],[CODE(math)@en[[VAR[a[SUB[5]]]]]]
となる。ここで、
- [CODE(math)@en[[VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[u]], [VAR(vector)[v]]) = [VAR[a[SUB[3]]]] + [VAR[a[SUB[4]]]] + [VAR[a[SUB[5]]]]]]
- [CODE(math)@en[[VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[v]], [VAR(vector)[w]]) = [VAR[a[SUB[2]]]] + [VAR[a[SUB[3]]]] + [VAR[a[SUB[5]]]]]]
- [CODE(math)@en[[VAR[d[SUB[[VAR[H]]]]]] ([VAR(vector)[w]], [VAR(vector)[u]]) = [VAR[a[SUB[2]]]] + [VAR[a[SUB[4]]]] + [VAR[a[SUB[5]]]]]]

であるから、[[三角不等式]]が成立することがわかる。