Циклические коды и их свойства

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

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

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

В теории циклического кодирования каждую r-элементную комбинацию принято записывать в виде некоторого полинома G(х) степени (n - 1);

где а - цифры двоичной системы счисления, отображающие элементы кодовой комбинации;

х - фиктивная переменная, заменяющая собой основание системы счисления.

Например, комбинация 1001101 может быть записана в виде

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

Рассмотрим процесс кодирования на примере. Пусть исходная кодовая комбинация кода 10110 представляет собой k информационных разрядов. Этой комбинации будет соответствовать полином А (х) = х⁴ + х² + + х. Предположим, что число контрольных разрядов r = 4 и используется образующий многочлен g (х) = х³+ х + +1. При построении избыточного кода полином неизбыточной кодовой комбинации сначала умножается на x^r:

Полученный в результате умножения полином Р (х) делится на образующий многочлен g(х):

Кодовая комбинация циклического кода F(х) получится сложением полинома Р(х) с остатком от деления, т. е. F(х) = Р(х) + остаток Р (x)/g(x) = х⁸ + х⁶ + х⁵ + х³ + х² + х + 1. Полученная кодовая комбинация избыточного циклического кода будет иметь вид 101101111. Первые пять разрядов ее являются информационными, а оставшиеся четыре – контрольными.

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