338
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Расстояние Хэмминга (Hamming distance)''' {{---}} число позиций, в которых соответствующие цифры символы двух двоичных слов строк одинаковой длины различны. }}
В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых k-ичных алфавитов и служит [[Метрическое пространство#def1 | метрикой]] различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
[[Файл:Hamming.JPG|thumb|180px|3-битный бинарный куб для нахождения расстояния Хэмминга]]
{{Утверждение
|statement=<tex>~d(x,y) \le d(x,z) + d(z,y)</tex>
|proof='''Доказательство №1''' Пусть слова <tex>x</tex> и <tex>y</tex> отличаются в некоторых позициях. Тогда какое бы слово <tex>z</tex> мы ни взяли, оно будет отличаться в каждой из этих позиций по крайне мере от одного из слов <tex>x</tex> и <tex>y</tex>. Следовательно, суммируя в правой части <tex>d(x, z)</tex> и <tex>d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова <tex>x</tex> и <tex>y</tex>. Т.е. получается, что <tex>~d(x,y) \le d(x,z) + d(z,y)</tex>. '''Доказательство №2 (с помощью математической индукции)''' I. Все позиции независимы.
II. Рассмотрим два варианта, когда <tex>x = y</tex> (1) и <tex>x \ne y</tex> (2):
