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

Широкое распространение получил класс линейных кодов, которые называются циклическими. Название этих кодов происходит от их основного свойства: если кодовая комбинация a₁, а₂,......, a_n-1, a_n принадлежит циклическому коду, то комбинации a_n, a₁, а₂,........, a_n-1; a_n-1, a_n, a₁, а₂,......., а_n-2 и т.д., полученные циклической перестановкой элементов, также принадлежат этому коду.

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

Поскольку любое число в произвольной системе счисления можно записать в виде a_n-1х^n-1+a_n-2x^n-2+...+ а₀х⁰, где х-основание системы счисления, a_n-1,...,a₀ – цифры этой системы, то переход от двоичного числа к записи в виде многочлена осуществляется следующим образом:

11011 1x⁴ + 1х³ +0х²+1x¹ +1x⁰=x⁴+x³+x+1

Отсюда видно, что кодовая комбинация длиной п (п=5) описывается многочленом степени п—1. Однако запись кодовой комбинации в виде многочлена не всегда определяет длину кодовой комбинации п. Например, при п=5 многочлену х²+1 соответствует кодовая комбинация 00101. Поэтому при переходе к записи в виде кодовой комбинации необходимо дописывать нулевые старшие разряды.

Кодовые комбинации циклического кода описываются полиномами, обладающими определенными свойствами. Последние определяются свойствами и операциями той алгебраической системы, к которой принадлежит множество полиномов.

В циклических кодах разрешенными кодовыми комбинациями являются те, которые имеют нулевой вычет по модулю P_v(x), т. е. делятся на образующий полином без остатка. Из всех возможных полиномов степени п (2^п) только 2^к полиномов (к = п—r ) имеют нулевой вычет по модулю Р_г(х). Они и образуют множество разрешенных кодовых комбинаций циклического кода.

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

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

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

Способы формирования циклических кодов.

Пусть задан полином P(x)=a_r-1x^r+a_r-2 x^r-1 +...+1, определяющий исправляющую способность кода, и задан исходный простой код, который требуется преобразовать в корректирующий циклический.

Обозначим многочлен, соответствующий комбинации простого кода, как Q(x). Возьмем произведение Q(x)x^r и разделим его на Р(х). В результате получим многочлен G(x) и остаток

Умножим левую и правую части на Р(х). В результате получим: Q(x) • х^r = G(x) • Р(х) + R(x) => G(x) • Р(х) = Q(x) • x^r + R(x)

Левая часть уравнения делится без остатка на Р(х), а значит, и правая часть также делится на Р(х). Таким образом, мы можем получить два различных способа формирования циклических кодов:

1-Исходный позиционный полином умножают на образующий полином. Данный способ

приводит к получению неразделимого кода.

2-Исходный полином умножают на х^г, затем путем деления на Р(х) получают остаток

R(x), который необходимо прибавить к Q(x)x^r. Данный способ позволяет получить

разделимый код, в котором исходная кодовая комбинация является одной из разрешенных.

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