Теория информационных процессов и систем

Лекции читает канд.техн.наук, доцент Литвинов Владислав Леонидович

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

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

•Это значит, что если, например, комбинация a0 a1 a2 … an-1 является разрешенной, то комбинация an-1a0 a1 a2 … an-2 также является разрешенной.

•Циклические коды обычно имеют полиномиальное представление,

означающее, что бинарные элементы кодового слова a0 a1 a2 … an-1 интерпретируются как коэффициенты полинома от некоторой фиктивной переменной х: f(x)=an-1xn-1 + an-2xn-2 +…+ a2x2+a1x + a0

•Например, кодовое слово 11010 представляется в виде полинома x4+x3+x

•Наибольшая степень х в слагаемом с ненулевым коэффициентом называется степенью полинома. Таким образом, в полиноме степени n-1 старший коэффициент an-1 равен 1.

•Действия над кодовыми комбинациями сводятся к действиям над полиномами. Причем операция сложения производится по модулю 2. Множество таких полиномов и действий над ними образуют т.н.

•поле Галуа порядка 2 (обозначается GF(2)).

•Циклический сдвиг коэффициентов полинома получается умножением полинома на x с одновременным сложением с двучленом xn+1. Действительно, пусть

•f(x)=1•xn-1+an-2xn-2+…+a2x2+a1x+a0.

•Тогда

•f(x)•x + (xn+1) = xn+an-2xn-1+ … +a2x3+a1x2+a0x + xn+1 =

•= an-2xn-1+ … +a2x3+a1x2+a0x +1

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

•u1(x) = g(x)

•u2(x) = g(x)∙x + (xn+1)

•u3(x) = u2(x)∙x + (xn+1) = g(x)∙x2 + (xn+1)(x+1)

•…

•un(x) = g(x)∙xn-1 + (xn+1)(xn-2+xn-3+…+1)

•При таком способе построения полином g(x) называется порождающим. Если потребовать, чтобы порождающий полином g(x) был делителем двучлена (xn+1), то все разрешенные комбинации приобретают свойство делимости на g(x).

•Из этого следует, что можно легко проверить, является ли комбинация разрешенной.

•Достаточно проверить ее делимость на полином g(x).

•Основные свойства циклических кодов:

•1. В циклическом (n,k)-коде каждый кодовый полином должен иметь степень не более n-1.

•2. Существует полином g(x) степени (n-k) вида

•g(x)=xn-k+gn-k-1xn-k-1+…+g2x2+g1x+1,

•называемый порождающим полиномом кода.

•3. Каждый кодовый полином u(x) является кратным g(x), то есть u(x) = m(x)•g(x).

•Кодирование с использованием циклических кодов

•Если дана k-значная входная комбинация m, то n-значное кодовое

слово u циклического кода с порождающим полиномом g(x) можно получить двумя способами.

•Первый:

•исходная k-значная комбинация, выраженная в виде полинома

•m(x) = mk-1 xk-1+…+ m1 × x + m0 степени (k – 1), умножается на порождающий полином g(x) степени (n – k):

•u(x) = m(x) × g(x).

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

•Второй:

•Используется процедура деления полиномов и вычисления остатков. В соответствии с правилами деления полиномов для каждой пары полиномов С(х) и g(x), g(x) ≠ 0 существует единственная пара полиномов q(x) — частное и ρ(х) — остаток, такие, что

•С(х) = q(x)× g(x) ρ(х) ,

•Домножим исходный полином m(x) на xn-k. Получившийся полином будет иметь степень (k – 1) + (n – k) = (n-1). Представим его в виде

•m(x)×xn-k = q(x)×g(x) ρ(х),

•где q(x) – частное от деления m(x)×xn-k на порождающий полином g(x), а ρ(х) – остаток от деления.

•Поскольку степень g(x) равна (n-k), то степень ρ(x) должна быть (n-k- 1) или меньше, а сам полином ρ(x) будет иметь вид

•ρ(x)= rn- k- 1 × xn-k-1 +...+ r2 × x2+ r1 × x +r0.

•что соответствует кодовому слову u = (mk-1 … m1 m0 rn- k-1 r1 ... r0).

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