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