172
правки
Изменения
→Определение и устранение ошибок в общем случае
== Определение и устранение ошибок в общем случае ==
Пусть <tex>\Sigma</tex> - — исходный алфавит, <tex>C: \Sigma \to B^m</tex> - — кодирование, <tex>B=(0,1)</tex>
<tex>d: B^m,B^m \to R^+</tex> <tex>-</tex> — [[Расстояние Хэмминга]] между двумя кодами. <br>
Определим <tex>d_0 = \min</tex> <math>~d(c(x),c(y))</math>, <tex>x,y \in \Sigma</tex>, <tex>x \ne y</tex>
Тогда легко понять, что код, полученный преобразованием <tex>C</tex> может исправлять <math>~[</math><tex>{d_0-1}\over{2}</tex><math>~]</math> и обнаруживать <tex>[d_0-1]</tex> ошибок. Действительно, при любом натуральном количестве допустимых ошибок <tex>r</tex> любой код <tex>S</tex> образует вокруг себя проколотый шар таких строк <tex>S_i</tex>, что <tex>0<d(S,S_i)\le r</tex>. Если этот шар не содержит других кодов (что выполняется при <tex>r<d_0</tex>) , то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при <tex>r\le {{d_0-1}\over{2}} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной и тождественно исправить на центр шара — строку <tex>S</tex>.
[[Файл:Ham.png]]
== Ссылки ==
*[http://en.wikipedia.org/wiki/Hamming_code Hamming code - Wikipedia, the free encyclopedia]
