Определение места ошибки в КК циклического кода

Выбор образующего полинома

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

Как мы уже отмечали остаток от деления КК циклического кода на образующий полином является синдромом этого кода. Для того, чтобы код мог исправлять ошибки, количество ненулевых остатков должно быть равно количеству комбинаций с различным сочетанием ошибок. Если код исправляет однократную ошибку, то число различных остатков равно количеству элементов в КК длиной «n». В общем случае число различных остатков должно быть равно Сn^t^и. Поэтому в качестве образующих полиномов берутся многочлены из класса непроводимых.

Непроводимыми называются такие полиномы, которые делятся без остатка только на 1 и сами на себя.

Кроме того, среди непроводимых полиномов, отбирают так называемые примитивные.

Примитивным считается полином степени r, если он обеспечивает максимальное число непроводимых полиномов той же степени r. Таких остатков должно быть не менее 2^r-1/

Примитивные полиномы выбираются из специальных таблиц.

МККТТ рекомендует V.41 – P(x)= x¹⁶+x¹²+ x⁵+1 - «Аккорд 1200»

В циклических кодах синдром (остаток) является опознавателем ошибки, но не указывает непосредственно на место ошибки в принятой КК.

Идея исправления ошибок базируется на том, что ошибочная комбинация после определенного числа циклических сдвигов «подгоняется» под полученный остаток таким образом, что в сумме с остатком она дает исправленную комбинацию.

Остаток при этом представляет собой разницу между искаженным и исправленным разрядами. Единицы в остатке стоят на местах искаженных разрядов в «подогнанной» циклическими сдвигами КК.

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

При этом место ошибки не имеет значения. В этом смысле циклические коды могут исправлять пачки ошибок, если длина пачки ошибок не превышает кратность исправляемых ошибок t_u

Алгоритм оптимального декодирования на основе анализа веса

1. Принятая КК делится на образующий полином

2. Если остаток нулевой, то КК выдается получателю. Если не нулевой, то выполняют п.3

3. Подсчитывается вес остатка; если w≤ t_u, то принятая КК складывается по модулю 2 с полученным остатком, если w> t_u,то выполняется п.4

4. Производим циклический сдвиг КК влево на один разряд. Делим полученную в результате сдвига КК на образующий полином. Если вес остатка w≤ t_u, то складываем остаток с КК и полученную КК сдвигаем вправо на один разряд – будет исправленная КК. Если w> t_u, то выполняется п.5

5. Повторяем п.4 до тех пор, пока не будет w≤ t_u. КК, полученная в результате последнего циклического сдвига влево, суммируется с последним остатком. Далее выполняется п.6

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

Рассмотрим пример

Пусть передаем КК 1001110 кода (7,4), образующий полином Р(х)=1011 (х³+х+1). Пусть в принятой КК искажен 4 разряд. d₀=3, т.е. код исправляет однократную ошибку t_u=1, т.е. приняли мы КК →1000110. Попытаемся обнаружить и исправить эту ошибку

1. Делим принятую КК на Р(х):

1000110 1011