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