Изменения

Перейти к: навигация, поиск

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

1622 байта добавлено, 02:43, 31 октября 2010
Нет описания правки
== Код, определяющий одну ошибку ==
Увеличив объем кода на 1 бит, можно получить возможность определять при передаче наличие одной ошибки. Для этого к коду нужно добавить бит x: <tex>0110..10x</tex>, такой, чтобы сумма всех единичек единиц была четной. В случае, если контрольная сумма окажется нечетной, следует отправить запрос на повторную посылку элемента, в котором была обнаружена ошибка. Такое кодирование применяется только если вероятность ошибки крайне мала, например, в оперативной памяти компьютера.
== Кодирование Хэмминга ==
Кодирование Хэмминга предусматривает как возможность обнаружения ошибки, так и возможность её исправления.
Рассмотрим простой пример: <tex>-</tex> закодируем четыре бита: <tex>a, b, c, d</tex>. Полученный код будет иметь длину в 8 бит и выглядеть следующим образом: <tex>a,b,c,d, a \oplus b, c \oplus d, a \oplus c, b \oplus d.</tex>
Рассмотрим табличную визуализацию кода:
|}
Как видно из таблицы, даже если один из битов <tex>a, b, c, d</tex> передался с ошибкой, содержащие его <tex>xor-</tex>-суммы не сойдутся. Итого, зная строку и столбец в проиллюстрированной таблице можно точно исправить ошибочный бит. По аналогичному принципу можно закодировать любое число бит. Пусть мы имеем исходную строку длиной в <tex>2^k</tex> бит. Для получения её кода добавим к ней <tex>k</tex> пар бит по следующему принципу:*Первая пара: сумма четных бит и сумма нечетных бит*Вторая пара: сумма тех бит, в чьем номере второй бит с конца ноль и сумма тех бит, в чьем номере второй бит с конца единица...*<tex>K</tex>-тая пара: сумма тех бит, в чьем номере <tex>k</tex>-тый бит с конца ноль и сумма тех бит, в чьем номере <tex>k</tex>-тый бит с конца единица Легко понять, что если в одном бите из строки допущена ошибка, то с помощью дописанных <tex>k</tex> пар бит можно точно определить, какой именно бит ошибочный. Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в строке. Всего пар <tex>k</tex>, следовательно мы имеем <tex>k</tex> бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>2^k</tex>.
172
правки

Навигация