Избыточное кодирование, код Хэмминга

Эта статья находится в разработке!

Избыточное кодирование - вид кодирования, использующий избыточное количество информации с целью последующего контроля целостности данных при записи/воспроизведении информации или при её передаче по линиям связи.

Код, определяющий одну ошибку

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

Кодирование Хэмминга

Кодирование Хэмминга предусматривает как возможность обнаружения ошибки, так и возможность её исправления. Рассмотрим простой пример: закодируем четыре бита: [math]a, b, c, d[/math]. Полученный код будет иметь длину в 8 бит и выглядеть следующим образом: [math]a,b,c,d, a \oplus b, c \oplus d, a \oplus c, b \oplus d.[/math] Рассмотрим табличную визуализацию кода:

[math]a[/math]	[math]b[/math]	[math]a \oplus b[/math]
[math]c[/math]	[math]d[/math]	[math]c \oplus d[/math]
[math]a \oplus c[/math]	[math]b \oplus d[/math]

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