Принцип декодирования при использовании циклического кода

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

Для обнаружения и исправления ошибок принятая комбинация делится на образующий многочлен g(х). Если остаток R(х) = 0, значит, комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей матрицы Н, который и укажет на местоположение ошибки по вектору ошибок.

1100001

1011

  1110

  1011

    1010

    1011

      011 - ошибка в четвертом разряде

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

1101011

1011

  1100

  1011

    1111

    1011

      1001

      1011

        010   - ошибка во 2-м контрольном разряде

Существует более общий алгоритм обнаружения и исправления ошибок:

1.      Принятая комбинация делится на образующий многочлен g(x). Если остаток R(x)<>0 то определяется вес остатка w. Если вес остатка равен или меньше числа исправляемых ошибок t (w<=t), то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.

2.      Если w>t, то производится циклический сдвиг на один символ влево и полученная после такого сдвига комбинация снова делится на образующий многочлен. Если вес полученного остатка w<=t, то циклически сдвинутую комбинацию складывают с остатком и затем после сложения  циклически сдвигают в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получаем исправленную комбинацию.

3.      Если после циклического сдвига на один символ по прежнему w>t, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига осуществляется деление сдвинутой комбинации на g(x)  и проверяется вес остатка. При w<=t сдвинутую комбинацию складывают с остатком и производят обратных циклических сдвигов вправо столько, сколько было сделано влево.

Пример 5.7. Необходимо проверить принятый код 1101110, для g(x)=1011 и t=1.

1.     Принятый код 1101110 делим на g(x), находим остаток R(x)=111, w=3
2.     Код 1101110 сдвигаем влево на один разряд, получаем 1011101.  Делим на образующий многочлен g(x). Находим остаток R(x)=101, вес w=2
3.     Снова производим сдвиг влево, получаем 0111011. Делим на g(x). Остаток R(x)=001. w=1
4.     Складываем сдвинутую комбинацию с остатком 0111011+001=0111010
5.     Производим два циклических сдвига вправо       

                         0111010 -> 0011101 ->1001110

В результате получили исправленную комбинацию.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.