Алгоритм декодирования циклических кодов

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

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

Таким образом, остатки от деления принятой комбинации на образующий полином является опознавателями ошибок циклических кодов. Но данные остатки еще не указывают непосредственно на место ошибки в кодовой комбинации.

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

Многочлен ошибок Е(х)=А(х)+Н(х), где А(х) - исходный многочлен циклического кода. Так, если ошибка произошла в , то при коде (9,5) =100000000, ошибке в соответствует =010000000 и т.д. Остаток от деления Е(0,1) на для данного 9-элементного кода всегда одинаков, он не зависит от вида передаваемой комбинации. В рассматриваемом примере R(0,1)=0101. Наличие ошибки в других элементах (> ) приведет к другим остаткам. Остатки зависят только от вида и n. Для n=9 и =10011 будет следующее соответствие:

Элемент с ошибкой
Синдром

Указанное однозначное соответствие можно использовать для определения места ошибки. Синдром не зависит от переданной кодовой комбинации, но в нем сосредоточена вся информация о наличии ошибок. Обнаружение и исправление ошибок в систематических кодах может производиться только на основе анализа синдрома.

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

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

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

– принятая кодовая комбинация делится на ;

– подсчитывается вес остатка (количество единиц в остатке);

– если < ( - допустимое количество ошибок, которое, исправляется кодом), то исправление сводится к сложению принятой кодовой комбинаций с остатком;

– если , то производят циклический сдвиг принятой кодовой комбинации влево на один разряд, а затем делят на ее и определяют вес остатка. Если то делимое суммируют с остатком, а затем производят циклический сдвиг на один элемент вправо. Это и будет исправленная кодовая комбинация; г

– если после первого сдвига остаток дает , то повторяют операцию сдвига на один разряд влево, а затем деление и определение веса остатка производят до тех пор, пока не будет удовлетворяться условие .

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

Пример: Рассмотрим данную методику применительно к r=3 и . Передано 1001110: Образующий полином Р(х)=х³+х+1, ошибка произошла на позиции
, т.е. принято 1000110. Определить номер элемента с ошибкой.