Декодирование циклических кодов

Обнаружение и исправление ошибок происходит по остаткам от деления принятой комбинации F(X) на образующий полином G(X). Если принятая комбинация делится на образующий полином без остатка, то код принят безошибочно. Остаток от деления свидетельствует об ошибке, но не указывает, какой именно. Чтобы найти ошибочный разряд и исправить его в циклических кодах, принято осуществлять следующие процедуры:

1) принятая комбинация делится на образующий полином;

2) подсчитывается количество единиц в остатке (вес остатка).Если W<=S, где S-допустимое число исправляемых данным кодом ошибок, то принятая комбинация складывается по модулю 2 с полученным остатком. Сумма даст исправленную комбинацию. Если W>S, то

3) производим циклический сдвиг влево принятой комбинации, делим полученную в результате циклического сдвига комбинацию на образующий полином К(Х). Если в остатке W<=S, то складываем делимое с остатком. Затем производим циклический сдвиг вправо полученной комбинации. Полученная комбинация уже не содержит ошибок. Если после первого циклического сдвига и последующего деления остаток получается таким, что его вес W>S, то

4) повторяется процедура п.3) до тех пор, пока не будет W<=S. В этом случае

5) производиться циклический сдвиг вправо на столько разрядов, на сколько была сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получим исправленную комбинацию.

Пример Показать процесс исправления одиночной ошибки в принятой кодовой комбинации.

Пусть имеется кодовое слово циклического кода 1001110, в котором произошла ошибка в четвертом разряде и получен код 100 0 11.

1. Делим принятую комбинацию на образующий полином g(X)=X³+X+1

2. Сравниваем вес полученного остатка W с возможным для данного кода числом исправляемых ошибок S. Вес остатка W=2. Число исправляемых ошибок S=1, т.е. W>S.

3. Производим циклический сдвиг принятой комбинации F(X ) на один разряд влево с последующим делением полученной в результате циклического сдвига комбинации на g(Х):

4. Повторяем процедуру до тех пор, пока не будет W<S

5. Складываем по модулю 2 последнее делимое с последним остатком

6. Производим циклический сдвиг комбинации, полученной в результате суммирования последнего делимого с последним остатком, вправо на 4 разряда (так как перед этим мы четырежды сдвигали принятую комбинацию влево) 1110100, 0111010, 0011101, 1001110 как видим, последняя комбинация соответствует переданной, т. е. уже не содержит ошибки.

Дата добавления: 2014-01-04