Содержание
Коды Хэмминга используются для вставки информации об исправлении ошибок в потоки данных. Коды составлены таким образом, что ошибка не только обнаруживается, но и исправляется. Добавление информации для исправления ошибок увеличивает объем данных, но также повышает надежность передачи данных по носителям с высоким коэффициентом ошибок.
Кодирование Хэмминга может быть сложно реализовать, но его можно сделать очень быстро, используя арифметические приемы на уровне битов. Это позволяет создать полезную и высокоскоростную систему исправления ошибок для использования во встраиваемых приложениях.
Шаг 1
Создайте слово данных. Любой бит с позицией, равной степени двойки (первый, второй, четвертый и т. Д.), Должен быть зарезервирован для информации о четности. Используйте столько, сколько необходимо, чтобы слово имело исходные данные и биты четности.
Пример:
1 1 0 1 0 0 1 0 становится _ _ 1 _ 1 0 1 _ 0 0 1 0
Исходные биты остаются в том же порядке, но были разложены для вставки битов четности.
Шаг 2
Вычислите первый бит четности. Начиная с первого бита, считывается бит, затем бит пропускается, и процедура повторяется до конца. А пока подсчитывается количество найденных. Биты четности в этом процессе не учитываются.
Если количество единиц четное, установите первый бит в ноль. В противном случае установите его на единицу.
Пример:
Биты 1, 3, 5, 7, 9 и 11 из _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101, содержат четыре единицы. Это четно, поэтому первый бит установлен в ноль: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Шаг 3
Вычислите оставшиеся биты четности. Начиная со второго бита, считываются два бита, затем два бита пропускаются, и процедура повторяется до конца. Четвертый бит считывает четыре бита, пропускает еще четыре, начиная с четвертого бита. За одним и тем же шаблоном следуют все биты четности, пока все они не будут вычислены.
Пример:
Бит 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 проверяет _1, 01, 01, которые содержат три единицы, поэтому бит 2 устанавливается в единицу. Бит 4: _ 0 1 1 1 0 1 _ 0 0 1 0 проверяет _101, 0, который содержит две единицы, поэтому бит 4 устанавливается в ноль. Бит 8: 0 1 1 0 1 0 1 _ 0 0 1 0 проверяет _0010, который содержит только один, поэтому бит 8 устанавливается в единицу.
Поэтому слово кодируется как 011010110010.
Шаг 4
Подтвердите слово. Если слово повреждено, биты четности не будут соответствовать ожидаемым. Чтобы убедиться, что слово не повреждено, просто вычислите биты четности, используя шаги два и три. Если биты не совпадают, запишите их положение.
Шаг 5
Исправьте неправильный бит. Если вы обнаружите неправильные биты четности, просто сложите позиции битов. Суммарное значение - это позиция неправильного бита. Измените битовое значение в этой позиции.
Например, если неправильные биты четности - это один и четыре, изменение значения пятого бита исправит ошибку.