Изменения

Перейти к: навигация, поиск

Расстояние Хэмминга

32 байта добавлено, 07:05, 4 ноября 2011
Нет описания правки
II. Рассмотрим два варианта, когда <tex>x = y</tex> (1) и <tex>x \ne y</tex> (2):
#Пусть <tex>x = y</tex>, тогда <tex>d = 0</tex> (по свойству №1), так как <tex>d(x,z)</tex> и <tex>d(z,y)</tex> не могут быть меньше нуля, значит их сумма также неотрицательна <tex>(0 \le d(x,z) + d(z,y))</tex>, следовательно , неравенство <tex>~d(x,y) \le d(x,z) + d(z,y)</tex> выполняется.#Пусть слова <tex>x</tex> и <tex>y</tex> отличаются в некоторой позиции <tex>t</tex>, т.е <tex>d(x,y) = 1</tex>. Тогда какое бы слово <tex>z</tex> мы ни взяли, оно в этой позиции будет отличаться по крайней мере хотя бы от одного из слов <tex>x</tex> и <tex>y</tex>. Следовательно, суммируя в правой части <tex>~( 1 \le d(x, z)+ d(z,y)</tex>, когда <tex>z</tex> и равно одному из слов <tex>x</tex> или <tex>y</tex>; <tex>~2 \le d(x,z) + d(z, y)</tex>, мы обязательно учтем все позиции, в которых различались слова когда <tex>z</tex> не равно ни одному из слов <tex>x</tex> и <tex>y)</tex>. Все неравенства выполняютсяСледовательно, неравенство <tex>~d(x, значитy) \le d(x, их сумма тожеz) + d(z, ч.т.дy)</tex> выполняется.}}
338
правок

Навигация