Для
обнаружения и исправления ошибок принятая
комбинация делится на образующий многочлен
g(х).
Если остаток R(х)
= 0, значит, комбинация принята без ошибок.
Наличие остатка свидетельствует о том, что
комбинация принята искаженной. Значение
остатка совпадет с одним из опознавателей
матрицы Н, который и
укажет на местоположение ошибки по вектору
ошибок.
1100001
1011
1110
1011
1010
1011
011 - ошибка в четвертом разряде
Если ошибка содержится в одном из поверочных разрядов, то одночлен одиночной ошибки будет иметь степень, меньшую, чем степень образующего многочлена и совпадет с остатком от деления. При этом номер разряда остатка прямо укажет на номер искаженного поверочного разряда.
1101011
1011
1100
1011
1111
1011
1001
1011
010 - ошибка во 2-м контрольном разряде
Существует более общий алгоритм обнаружения и исправления ошибок:
1.
Принятая комбинация делится на
образующий многочлен g(x).
Если остаток R(x)<>0
то определяется вес остатка w.
Если вес остатка равен или меньше числа
исправляемых ошибок t
(w<=t),
то принятую комбинацию складывают по
модулю 2 с остатком и получают исправленную
комбинацию.
2.
Если w>t,
то производится циклический сдвиг на один
символ влево и полученная после такого
сдвига комбинация снова делится на
образующий многочлен. Если вес полученного
остатка w<=t,
то циклически сдвинутую комбинацию
складывают с остатком и затем после
сложения
циклически сдвигают в обратную сторону
вправо на один символ (возвращают на
прежнее место). В результате получаем
исправленную комбинацию.
3.
Если после циклического сдвига на один
символ по прежнему w>t,
то производят дополнительные циклические
сдвиги влево. При этом после каждого сдвига
осуществляется деление сдвинутой
комбинации на g(x)
и проверяется вес остатка. При w<=t
сдвинутую комбинацию складывают с остатком
и производят обратных циклических сдвигов
вправо столько, сколько было сделано влево.
Пример
5.7. Необходимо проверить принятый код
1101110, для g(x)=1011
и t=1.
1.
Принятый код 1101110 делим на g(x),
находим остаток R(x)=111,
w=3
2.
Код 1101110 сдвигаем влево на один разряд,
получаем 1011101.
Делим на образующий многочлен g(x).
Находим остаток R(x)=101,
вес w=2
3.
Снова производим сдвиг влево, получаем
0111011. Делим на g(x).
Остаток R(x)=001.
w=1
4.
Складываем сдвинутую комбинацию с
остатком 0111011+001=0111010
5.
Производим два циклических сдвига
вправо
0111010
->
0011101 ->1001110
В результате получили исправленную комбинацию.