4.5. Способ коррекции ошибок циклическими кодами

Важным свойством циклических кодов является то, что все они строятся с помощью образующего полинома Приведем методику построения циклического кода. Образующий полином принимает участие в образовании каждой кодовой комбинации, поэтому комбинация кода делится на образующий полином без остатка. Однако без остатка делятся только те многочлены (комбинации), которые принадлежат данному коду, т. е. образующий полином позволяет выбрать разрешенные кодовые комбинации из всех возможных. Если же при делении принятой кодовой комбинации циклического кода на образующий многочлен будет получен остаток, значит, имеет место ошибка. Таким образом, остатки от деления принятой комбинации на образующий полином являются опознавателями ошибок циклических кодов. Но данные остатки еще не указывают непосредственно на место ошибки в кодовой комбинации.

В циклических кодах идея исправления ошибок основывается на следующем. Ошибочная комбинация после

- определенного числа циклических сдвигов «подгоняется» под остаток таким образом, чтобы в сумме с остатком она давала бы исправленную комбинацию. Остаток при этом представляет собой разницу между искаженными и правильными символами, а единицы в остатке стоят на местах искаженных разрядов в «подогнанной» циклическими сдвигами комбинации. «Подгоняют» искаженную комбинацию до тех пор, пока число единиц в остатке не будет равно числу ошибок в коде. При этом, естественно, число единиц может быть равно числу ошибок исправляемых данйым кодом (код исправляет три ошибки и в искаженной комбинации три ошибки) или меньше (код исправляет три ошибки, в принятой комбинации — одна ошибка).

Таким образом, для обнаружения и исправления ошибочного разряда производят следующие операции [133].

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

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

3) производят циклический сдвиг принятой комбинации влево на один разряд. Комбинацию, полученную в результате циклического сдвига, делят на образующий полином Если в результате повторного деления целимое суммируют с остатком, затем

4) производят циклический сдвиг вправо на один разряд комбинации, полученной в результате суммирования последнего делимого с последним остатком. Полученная комбинация уже не содержит ошибок. Если после первого циклического Сдвига и последующего деления остаток получается таким, что его вес то

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

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

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

1. Делим принятую комбинацию на образующий полином:

2. Сравниваем вес полученного остатка с числом исправляемых ошибок т. е.

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

4. Повторяем п. 3 до тех пор, пока не будет получено

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

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