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

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

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

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

- высокая помехоустойчивость – за счет способности кода к обнаружению и исправлению ошибок.

Для оптимального кода количество исправляемых ошибок равно 2 ^k -1, где k – число контрольных разрядов.

Применяемые в настоящее время циклические коды, содержащие n разрядов, из которых m является информационными, а k = n - m – контрольными (проверочными), расположенными в конце кодовой комбинации. Так как информационные и контрольные разряды занимают строго определенные места и длина кодовой комбинации постоянна, то циклические коды относятся к систематическим кодам.

Для описания циклических кодов обычно пользуются записью любого n -разрядного двоичного числа в виде многочлена степени (n -1). Например, кодовая комбинация 1011001 записывается как многочлен x ⁶ + x ⁴ + x ³ + 1, т.е. коэффициенты многочлена не пишутся, а члены с коэффициентами 0 опускаются. Наивысшая степень числа с коэффициентом 1 называется степенью полинома (многочлена). Так, в примере рассмотрен многочлен 6 степени.

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

В циклическом кодировании все математические операции сложения производятся с использованием сложения по mod 2 и с приведением подобных членов.

Операцию умножения символически проводят по следующим правилам:

1) Вначале все многочлены перемножаются по обычным правилам, но с приведением подобных членов по mod 2.

2) Если старшая степень полученного в результате умножения многочлена не превышает (n -1), то этот многочлен является результатом символического умножения.

3) Если старшая степень полученного в результате умножения многочлена больше (n -1), то многочлен произведения делится на двучлен x +1. В этом случае результатом символического умножения считается остаток от деления (вычет).

Пример:

Имеем кодовые комбинации 001101 и 101110, где n = 6.

Эти комбинации соответствуют многочленам: x ³ + x ² + 1 и x ⁵ + x ³ + x ² + x.

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

Для проведения этой операции с многочленами необходимо их символически умножить на x × x = x ²:

1) (x ³ + x ² + 1) × x ² = x ⁵ + x ⁴ + x ², т.к. степень полученного многочлена не превышает (n -1) = 5, то этот многочлен принимается за результат умножения и действительно соответствует сдвинутой кодовой комбинации 110100.

2) (x ⁵ + x ³ + x ² + x) × x ² = x ⁷ + x ⁵ + x ⁴ + x 3, т.к. степень полученного многочлена превышает (n -1), то для получения результата символического умножения необходимо произвести деление этого многочлена на двучлен (xⁿ +1):

Остаток от деления x ⁵ + x ⁴ + x ³ + x принимается за результат символического умножения, что соответствует циклически сдвинутой кодовой комбинации 111010.

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

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

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

Дата добавления: 2015-10-28