Вычисление синдрома и исправление ошибок в циклических кодах

Вычисление синдрома для циклических кодов является довольно простой процедурой, совершенно аналогичной процедуре кодирования. Рассмотрим ее.

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

Разделив й (х) на порождающий полином g (x), получим.

где q (х) — частное от деления; s (x) — остаток от деления.

Если й (х) является допустимым кодовым полиномом, то он делится на g (x) без остатка, т. е. s (x) = 0.

Следовательно, результат s (x) ф 0 является условием наличия ошибки в принятой последовательности, а полином s (x) имеет смысл синдрома ошибки в последовательности и (х).

Синдром s (x) имеет в общем случае вид.

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

При наличии в принятой последовательности й хотя бы одной ошибки вектор синдрома s будет иметь по крайней мере один ненулевой элемент, при этом факт наличия ошибки легко обнаружить, объединив по элементу ИЛИ выходы всех ячеек регистра синдрома.

Покажем, что синдромный многочлен s (x) однозначно связан с многочленом ошибки е (х), а значит, с его помощью можно не только обнаруживать, но и локализовать ошибку в принятой последовательности.

Рис. 4.8. Схема получения синдрома для порождающего полинома д (х) =х³ +х+1.

Пусть е (х) — полином вектора ошибки. Тогда полином принятой последовательности.

Учтем, что п (х) — допустимый кодовый полином, нацело делящийся на порождающий полином g (x), и запишем два выражения:

По определению вектора (полинома) ошибки:

То есть синдромный полином s (x) есть остаток от деления полинома ошибки е (х) на порождающий полином д (х).

Отсюда следует, что по синдрому s (x) можно однозначно определить вектор ошибки е (х), а следовательно, и исправить эту ошибку.