Понятие циклических кодов.




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

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

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

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

В качестве информационных символов (И) для построения циклических кодов используются комбинации двоичного безызбыточного кода.

Если некоторую комбинацию безызбыточного кода G(X) умножить на образующий многочлен Р(Х), в результате получится комбинация циклического кода F(X), обладающего уже некоторой помехоустойчивостью. Корректирующие свойства циклического кода определяются видом образующего многочлена Р(Х). Полученный код, не будет систематическим: контрольные символы будут располагаться бессистемно, на произвольных местах.

В циклических кодах для контрольных символов отводятся места после информационных символов - в конце кодовой комбинации. (14.1), где Q(X) - результат деления произведение на образующий полином Р(Х) которое будет той же степени, что и кодируемая комбинация G(X), R(X) - остаток или, умножив обе части на образующий многочлен Р(Х). Кодовая комбинация циклического кода (14.3) может быть получена двумя способами: путем умножения комбинации Q(X), являющейся одной из комбинаций безызбыточного кода, подлежащего преобразованию в циклический код на образующий полином Р(Х); в результате умножения заданной комбинации безызбыточного кода G(X) на одночлен , имеющий ту же степень, что и образующий многочлен Р(Х), и добавления к произведению остатка R(X), полученного от деления произведения на образующий многочлен Р(Х).

Полученное сообщение является одним из ансамбля N сообщений. Каждое из них нужно кодировать таким же образом. Чтобы избежать остальных расчетов прибегают к использованию образующей матрицы. Образующая матрица получается из отраженной единичной матрицы путем приписывания к ней справа матрицы дополнений . (14.4). Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен Р(Х).

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

Наибольшее распространение получили две модели кода Хемминга: код с обнаружением и исправлением одиночной ошибки (минимальное кодовое расстояние d = 3) и код с исправлением одиночной ошибки и обнаружением двойной (d = 4).

Декодирование циклических кодов.

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

Если при делении принятой комбинации на образующий многочлен получится остаток, то это свидетельствует о наличии ошибки, т.е. вместо переданной комбинации F(X) мы принимаем некоторую другую комбинацию H(X), которую можно представить в виде суммы двух многочленов H(X) = F(X) + E(X), (14.10) где E(X) - многочлен ошибок.

Обнаружение и исправление ошибок: вычисляется остаток от деления принятой комбинации F(X) на образующий многочлен Р(Х). Если остаток равен 0, то комбинация не содержит ошибки. Если остаток не равен 0, то в принятой комбинации имеется ошибка; при неравенстве 0 остатка подсчитывается его "вес" W, причем, если W £ s, то принятую кодовую комбинацию надо сложить по модулю 2 с остатком. Если W > s, то производится циклический сдвиг влево на один символ (на один разряд). Полученная после такого сдвига комбинация вновь делится на образующий многочлен и подсчитывается "вес" остатка: а) W £ s, циклически сдвинутую комбинацию складывают с остатком и затем, после сложения, циклически сдвигают в обратную сторону (вправо) на один символ. Получается исправленная комбинация;

б) W > s. При этом производятся дополнительные циклические сдвиги влево. После каждого циклического сдвига на один символ полученная комбинация делится на образующий многочлен и определяется "вес" остатка. Если W £ s, то полученную от деления комбинацию складывают с остатком, но циклическую перестановку обратно вправо осуществляют не один раз, а столько, сколько было сделано сдвигов влево. В результате получается исправленная комбинация.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-26 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: