1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Избыточное кодирование''' (англ. ''redundant encoding'') {{---}} вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи.
{{Определение
|definition=Код определяет <tex>d</tex> ошибок, если при передаче кодового слова, в котором <tex>\leq d</tex> ошибок, алгоритм декодирования скажет, что есть ошибка.
}}
{{Определение
|definition=Код исправляет <tex>d</tex> ошибок, если при передаче кодового слова, в котором <tex>\leq d</tex> ошибок, алгоритм декодирования сможет восстановить исходное слово.
}}
== Код, определяющий одну ошибку ==
Итого, увеличивая код длиной <tex>n</tex> на <tex>\log_2 n + 1</tex>, можно обнаружить и исправить одну ошибку.
== Определение и устранение ошибок в общем случае =См. также =Пусть <tex>\Sigma</tex> — исходный алфавит, <tex>C: \Sigma \to B^m</tex> — кодирование, <tex>B=(0,1)</tex> <tex>d: B^m \times B^m \to \mathbb{R}</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 dpi = 150> {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)\leqslant r</tex>. Если этот шар не содержит других кодов (что выполняется при <tex>r<d_0</tex>) , то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при <tex dpi = 150>r \leqslant {{d_0-1}\over{2}} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной и тождественно исправить на центр шара — строку <tex>S</tex>.<br>[[Файл:Ham.png|350pxкодирования]]
== Источники информации ==
*[http://en.wikipedia.org/wiki/Hamming_code Wikipedia {{---}} Hamming code]
