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

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

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

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

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

При этом место ошибки не имеет значения. В этом смысле циклические коды могут исправлять пачки ошибок, если длина пачки ошибок не превышает кратность исправляемых ошибок 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

1011 101

1111

1000

1011

Получим остаток 11, его вес равен 2> t_u=1

2. Производим сдвиг полученной КК влево на 1 разряд

1000110→0001101

делим на Р(х)

0001101 1011

1011

110 - вес остатка 2> t_u=1

3. Еще сдвигаем влево КК

0001101→0011010 делим на Р(х)

0011010

1011 1011

1100

111 - вес остатка 3> t_u=1

4. Еще сдвигаем влево КК

0011010→0110100 делим на Р(х)

0110100 1011

1011

1100

1011

1110

101 - вес остатка 2> t_u=1

5. Еще сдвигаем влево КК

0110100→1101000, делим на Р(х)

1101000 1011

1011

1100

1011

1110

1011

1010

1011

1 - вес остатка w= t_u =1

6. Складываем последнее делимое с остатком

1101000

1101001

7. Сдвинем эту КК вправо на 4 разряда, т.к. мы сдвигаем исходную КК влево на 4 разряда:

1101001 →1110100

1110100 →0111010

0111010 →0011101

0011101 →1001110

Получим исправленную КК – сравним с переданной: 1001110