Изменения

{{В разработке}}'''Избыточное кодирование''' (англ. ''redundant encoding'') {{- --}} вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. {{Определение|definition=Код определяет <tex>d</tex> ошибок, если при передаче кодового слова, в котором <tex>\leq d</tex> ошибок, алгоритм декодирования скажет, что есть ошибка.}} {{Определение|definition=Код исправляет <tex>d</tex> ошибок, если при передаче кодового слова, в котором <tex>\leq d</tex> ошибок, алгоритм декодирования сможет восстановить исходное слово.}} 

Увеличив объем кода на <tex>1 </tex> бит, можно получить возможность определять при передаче наличие одной ошибки. Для этого к коду нужно добавить бит <tex>x</tex>: <tex>0110..10x</tex>, такой, чтобы сумма всех единиц была четной. В случае, если контрольная сумма окажется нечетной, следует отправить запрос на повторную посылку элемента, в котором была обнаружена ошибка. Такое кодирование применяется только если вероятность ошибки крайне мала, например, в оперативной памяти компьютера.

Рассмотрим простой пример <tex>{{---</tex> }} закодируем четыре бита: <tex>a, b, c, d</tex>. Полученный код будет иметь длину <tex>8 </tex> бит и выглядеть следующим образом: <tex>a,b,c,d, a \oplus b, c \oplus d, a \oplus c, b \oplus d.</tex>

{| class="wikitable" style="width:10cm" border=1|-align="1center" bgcolor=#F0F0F0! <tex>a</tex> || <tex>b</tex> ||style="background:#FFF"| <texbgcolor=#FFF>a \oplus b</tex>|-align="center" bgcolor=#F0F0F0! <tex>c</tex> || <tex>d</tex> ||style="background:#FFF"| <tex>c \oplus d</tex>|-align="center" bgcolor=#FFF! |<tex>a \oplus c</tex> || <tex>b \oplus d</tex>

Как видно из таблицы, даже если один из битов <tex>a, b, c, d</tex> передался с ошибкой, содержащие его <tex>xor</tex>-суммы не сойдутся. Итого, зная строку и столбец в проиллюстрированной таблице можно точно исправить ошибочный бит.Если один из битов <tex>a \oplus b, a \oplus c, b \oplus d, c\oplus d</tex> передался с ошибкой, то не сойдется только одна сумма и очевидно, что можно легко определить, какой бит неверный

*<tex>k</tex>-тая пара: сумма тех бит, в чьем номере <tex>k</tex>-тый бит с конца ноль и сумма тех бит, в чьем номере <tex>k</tex>-тый бит с конца единица<br>[[Файл:Ham3.jpg|1000px|thumb|left|Соответствие добавленной информации исходным битам. Первый вариант кодирования соответствует использованию битов, раскрашенных в тёмные и светлые цвета, оптимизация — в тёмные цвета и серый]]                                   

== Расстояние Хэмминга =='''Расстояние Хэмминга''' — число позицийЛегко понять, что если в которых соответствующие цифры двух двоичных слов одинаковой длины различныодном бите из строки допущена ошибка, то с помощью дописанных <tex>k</tex> пар бит можно точно определить, какой именно бит ошибочный. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функциейЭто объясняется тем, определяющей расстояние что каждая пара определяет один бит номера ошибочного бита в метрическом пространстве) объектов одинаковой размерностистроке. Всего пар <tex>k</tex>, следовательно мы имеем <tex>k</tex> бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>2^k+2k</tex>.

Например: <math>d(10Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит {\color{Blue---}1}1{<tex> \color{Blue}1}01, 10{mathrm X \color{Red}0}1{mathrm O \color{Red}0}01)=2mathrm R</mathtex>всех битов строки.

Расстояние Хэмминга обладает свойствами метрикиИтого, удовлетворяя следующим условиям:* увеличивая код длиной <mathtex>~d(x,y) \ge 0</math>* <math>~d(x,x)=0n</mathtex>* на <mathtex>~d(x,y)=d(y,x)</math>* <math>~d(x,z) \le d(x,y) log_2 n + d(y,z)1</mathtex>, можно обнаружить и исправить одну ошибку.

== Определение См. также ==* [[Обнаружение и устранение исправление ошибок в общем случае кодирования]]== Источники информации ==Пусть <tex>\Sigma<*[http:/tex> /en.wikipedia.org/wiki/Hamming_code Wikipedia {{-- исходный алфавит, <tex>C: \Sigma \to B^m</tex> - кодирование, <tex>B=(0,1)</tex>}} Hamming code]

Тогда легко понять, что код, полученный преобразованием <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\le</tex><tex>{d-1}\over{2} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной и тождественно исправить на центр шара <tex>-</tex> строку <tex>S</tex>.