Циклічні коди. Згортальні коди

Циклические коды.

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

Циклические коды удобно описывать многочленами переменной X. При этом показатели степени соответствуют номерам разрядов, а коэффициентами этого многочлена являются 0 и 1 отображаемой кодовой комбинации. Например, комбинацию 1001101 можно записать в виде .

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

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

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

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

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

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

Пример. Дано , , и Закодировать сообщение 1000100101. Для кодирования сообщения 1000100101, соответствующего многочлену разделим на :

В итоге этой операции получим остаток Суммируя произведение с полученным остатком, получим кодовый многочлен

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

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

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