Изменения

'''Избыточное кодирование''' (англ. ''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> передался с ошибкой, то не сойдется только одна сумма и очевидно, что можно легко определить, какой бит неверный

[[Файл:Ham2Ham3.pngjpg|1000px|thumb|left|Соответствие добавленной информации исходным битам. Первый вариант кодирования соответствует использованию битов, раскрашенных в тёмные и светлые цвета, оптимизация — в тёмные цвета и серый]]                                   

Теперь заметимЛегко понять, что если в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда нам достаточно оставить только один бит одном бите из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строкестроки допущена ошибка, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит - с помощью дописанных <tex>xork</tex> всех битов строкипар бит можно точно определить, какой именно бит ошибочный.== Определение и устранение ошибок Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в общем случае ==Пусть строке. Всего пар <tex>\Sigmak</tex> &mdash; исходный алфавит, следовательно мы имеем <tex>C: \Sigma \to B^mk</tex> &mdash; кодированиебит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>B=(0,1)2^k+2k</tex>.

<tex>d: B^mТеперь заметим, что в случае наличия ошибки в исходной строке,B^m \to R^+</tex> &mdash; [[Расстояние Хэмминга]] между двумя кодамировно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. <br>Определим <tex>d_0 = \min</tex> <math>~d(c(x)Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке,c(y))</math>то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит {{---}} <tex>x,y \in mathrm X \Sigma</tex>, <tex>x mathrm O \ne ymathrm R</tex>всех битов строки.

Тогда легко понятьИтого, что увеличивая код, полученный преобразованием длиной <tex>Cn</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-log_2 n + 1}\over{2}} </tex>), то попавшую в шар строку <tex>S_i</tex> можно считать ошибочной обнаружить и тождественно исправить на центр шара &mdash; строку <tex>S</tex>.<br>[[Файл:Hamодну ошибку.png]]

== Ссылки См. также ==* [[Обнаружение и исправление ошибок кодирования]]== Источники информации ==*[http://en.wikipedia.org/wiki/Hamming_code Wikipedia {{---}} Hamming code - Wikipedia, the free encyclopedia]