Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Избыточное кодирование, код Хэмминга
Избыточное кодирование (англ. redundant encoding) — вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи.
[править] Код, определяющий одну ошибку Увеличив объем кода на бит, можно получить возможность определять при передаче наличие одной ошибки. Для этого к коду нужно добавить бит : , такой, чтобы сумма всех единиц была четной. В случае, если контрольная сумма окажется нечетной, следует отправить запрос на повторную посылку элемента, в котором была обнаружена ошибка. Такое кодирование применяется только если вероятность ошибки крайне мала, например, в оперативной памяти компьютера. [править] Кодирование Хэмминга Кодирование Хэмминга предусматривает как возможность обнаружения ошибки, так и возможность её исправления. Рассмотрим простой пример — закодируем четыре бита: . Полученный код будет иметь длину бит и выглядеть следующим образом: Рассмотрим табличную визуализацию кода: Как видно из таблицы, даже если один из битов передался с ошибкой, содержащие его -суммы не сойдутся. Итого, зная строку и столбец в проиллюстрированной таблице можно точно исправить ошибочный бит. Если один из битов передался с ошибкой, то не сойдется только одна сумма и очевидно, что можно легко определить, какой бит неверный По аналогичному принципу можно закодировать любое число бит. Пусть мы имеем исходную строку длиной в бит. Для получения её кода добавим к ней пар бит по следующему принципу:
...
Соответствие добавленной информации исходным битам. Первый вариант кодирования соответствует использованию битов, раскрашенных в тёмные и светлые цвета, оптимизация — в тёмные цвета и серый
Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда можно оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит — всех битов строки. Итого, увеличивая код длиной на , можно обнаружить и исправить одну ошибку. [править] Определение и устранение ошибок в общем случае Пусть — исходный алфавит, — кодирование, — расстояние Хэмминга между двумя кодами. Тогда легко понять, что код, полученный преобразованием может исправлять и обнаруживать ошибок. Действительно, при любом натуральном количестве допустимых ошибок любой код образует вокруг себя проколотый шар таких строк , что . Если этот шар не содержит других кодов (что выполняется при ), то можно утверждать, что если в него попадает строка, то она ошибочна. Аналогично можно утверждать, что если шары всех кодов не пересекаются (что выполняется при ), то попавшую в шар строку можно считать ошибочной и тождественно исправить на центр шара — строку .
|