Циклические коды - Техника передачи дискретных сообщений

Широкое распространение получил класс линейных кодов которые называются циклическими. Название этих кодов происходит от их основного свойства: если кодовая комбинация A1, а2,......, aN-1, aN принадлежит циклическому коду, то комбинации aN, a1, А2,........, aN-1; aN-1, aN, a1, а2,......., аN-2 и т. д., полученные циклической перестановкой элементов, также принадлежат этому коду.

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

,

Где Х-основание системы счисления, AN-1,...,a0 - цифры этой системы, то переход от двоичного числа к записи в виде многочлена осуществляется следующим образом:

1101 1х3 +1х2+1x0=x3+x2+1

KK ЦК описываются полиномами обладающими определенными свойствами. Последние определяются свойствами и операциями той алгебраической системы, к которой принадлежит множество полиномов. Например, в алгебраической системе, которая носит название поля Галуа (GF(x)), действие над коэффициентами полиномов (сложение, вычитание) производится по модулю два. Умножение полиномов должно производиться по модулю некоторого полинома Рr(х). Эти два условия определяют замкнутость указанных операций: их применение не приводит к кодовым комбинациям, длинна которых больше длинны заданного кода n.

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

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

,

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

Умножим левую и правую части на P(x). В результате получим:

Перепишем равенство ( * ) в виде

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

    1. Путем умножения многочлена исходной кодовой комбинации на производящий полином; 2. Путем деления на производящий полином и приписывания к остатка от деления.

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

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

Похожие статьи




Циклические коды - Техника передачи дискретных сообщений

Предыдущая | Следующая