Самокорректирующиеся коды. Код Хэмминга

Для исправления ошибки не достаточно установить ее наличие, нужно указать позицию, в которой произошла ошибка. Увеличивая число дополнительных разрядов и формируя по определенным правилам проверочные символы можно усилить корректирующие свойства кода так, чтобы он не только обнаруживал, но и исправлял ошибки.

Метод, позволяющий определить место появления ошибочного знака и исправить его, был предложен в 1948 году Р.Хэммингом. Построенные с использованием этого метода коды получили название - коды Хэмминга.

В основу метода положено добавление к информационным битам добавочных битов проверки четности суммы знаков двоичной кодовой комбинации. Проверочные знаки расположены в разрядах, номера которых равны степеням числа 2: 1=2⁰, 2=2¹, 4=2², 8=2³, ….
В остальных разрядах кодовой комбинации размещаются информационные знаки. Для любого проверочного знака с номером k, начиная с него, k бит подряд являются проверяемыми, далее k бит подряд непроверяемыми, затем k бит подряд проверяемыми, и так далее. Для разряда с номером 1 проверяемыми являются разряды 1, 3, 5, 7, и так далее. Для разряда с номером 2 проверяемыми являются разряды 2, 3, 6, 7, 10, 11, … Для разряда 4 проверяемыми являются разряды 4, 5, 6, 7, 12,13,14,15, … Значение 0 или 1 вносится в разряд проверочного знака (с номером 1, 2, 4,..) так, чтобы сумма всех проверяемых разрядов была четным числом.

Алгоритм проверки полученной кодовой комбинации и устранения ошибки в ней состоит в следующем:

· Производится проверка всех разрядов четности,

· При отсутствии ошибок (четные суммы всех проверочных знаков) из кодовой комбинации удаляются проверочные разряды и информационная последовательность знаков передается получателю,

· При обнаружении ошибок в контрольных суммах, вычисляется сумма номеров всех неправильных проверочных разрядов, инвертируется содержимое разряда, номер которого равен вычисленной сумме, из кодовой комбинации удаляются проверочные разряды и информационная последовательность знаков передается получателю.

Пример. В отличие от выше приведенной переданной кодовой комбинации, в 5-ом разряде ошибочно принят знак 0. В связи с этим получены нечетные суммы проверочных разрядов 1 и 4, сумма которых равна 5.

Пример.

Пусть Х= 101100. Из условия p = 4. Обозначим эти разряды y₄y₃y₂y_1.

Запишем номера разрядов в двоичном представлении, как показано в таблице. Имеем 4 столбца номеров Åразрядов. В контрольные суммы s_i будем суммировать по модулю 2 значения разрядов имеющих на i –ом месте 1. Тогда имеем систему уравнений:

s₁ = 0Å1Å0Åy₁ Åy₃ = 0, y₃= 1

s₂ = 0Å1Å1Åy₁ Åy₄ = 0, y₄= 0

s₃ = 1Å0Å1Åy₁ = 0, y₁= 0

s₄ = y₂Åy₃Åy₄ = 0. y₂= 1

Отсюда y₁=0, y₂=1, y₃=1, y₄=0.

Если в последнем разряде возник ошибочный бит, вместо 0 будет 1, то в контрольном коде получим значение 0001, что указывает на номер Подробная информация по теме занятия размещена в электронных учебниках (Lessons и «Медицинская информатика»)

Не нашли, что искали? Воспользуйтесь поиском: