172
правки
Изменения
Нет описания правки
*Вторая пара: сумма тех бит, в чьем номере второй бит с конца ноль и сумма тех бит, в чьем номере второй бит с конца единица
...
*<tex>Kk</tex>-тая пара: сумма тех бит, в чьем номере <tex>k</tex>-тый бит с конца ноль и сумма тех бит, в чьем номере <tex>k</tex>-тый бит с конца единица
Легко понять, что если в одном бите из строки допущена ошибка, то с помощью дописанных <tex>k</tex> пар бит можно точно определить, какой именно бит ошибочный. Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в строке. Всего пар <tex>k</tex>, следовательно мы имеем <tex>k</tex> бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>2^k</tex>.
Итого, увеличивая код длиной <tex>n</tex> на <tex>2\log_2 n</tex>, можно обнаружить и исправить одну ошибку.
== Расстояние Хэмминга ==
'''Расстояние Хэмминга''' — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Например: <math>d(10{\color{Blue}1}1{\color{Blue}1}01, 10{\color{Red}0}1{\color{Red}0}01)=2</math>
Расстояние Хэмминга обладает свойствами метрики, удовлетворяя следующим условиям:
* <math>~d(x,y) \ge 0</math>
* <math>~d(x,x)=0</math>
* <math>~d(x,y)=d(y,x)</math>
* <math>~d(x,z) \le d(x,y) + d(y,z)</math>
== Определение и устранение ошибок в общем случае ==
Пусть <tex>\Sigma</tex> - исходный алфавит, <tex>C: \Sigma \to B^m</tex> - код, <tex>B=(0,1)</tex>
Определим <tex>d = \min</tex> <math>~d(c(x),c(y))</math>, <tex>x,y \in \Sigma</tex>, <tex>x<>y</tex>
Тогда легко понять, что код, полученный преобразованием <tex>C</tex> может исправлять <math>~[</math><tex>{d-1}\over{2}</tex><math>~]</math> и обнаруживать <tex>[d-1]</tex> ошибок. Действительно, при любом натуральном количестве допустимых ошибок <tex>r</tex> любой код S образует вокруг себя проколотый шар таких строк <tex>S_i</tex>, что <tex>0<d(S,S_i)<=r</tex>. Если этот шар не содержит других кодов (что выполняется при <tex>r<d</tex>) , то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при <tex>r<= {d-1}\over{2} </tex>), то попавшую в шар строку <tex>S_i</tex> можно тождественно исправить на центр шара <tex>-</tex> строку<tex>S</tex>.
