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

Циклическим кодом называется линейный код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых векторов, образующих его. Пусть дан n-мерный вектор v = a₀a₁…a_n-1 с координатами из конечного поля F. Его циклическим сдвигом называется вектор v' = a_n­-1a₀a₁…a_n-2.

Рассмотрим n-мерное арифметическое пространство над полем Галуа GF(2). Каждому вектору a₀a₁…a_n-1 из GF(2) можно сопоставить взаимно однозначно многочлен a₀+a₁x+…+a_n-1x^n-1 с коэффициентами из GF(2). Сумме двух векторов a₀a₁…a_n-1 и b₀b₁…b_n-1 ставится в соответствие сумма соответствующих им многочленов, произведению элементов поля на вектор - произведение многочлена, соответствующего этому вектору, на элемент.

Рассмотрим некоторый многочлен g(x) из описанного линейного пространства. Множество всех многочленов из этого подпространства, которые делятся без остатка на g(x), образует линейное подпространство. Линейное подпространство определяет некоторый линейный код.

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

Покажем, как связаны полиномиальные коды C(g(x)) и циклические коды. Пусть a = a₀…a_n-1 – некоторое кодовое слово, а соответствующий кодовый многочлен a(x) = a₀+...+a_n-1x^n-1. Циклическому сдвигу a' соответствует кодовый многочлен a'(x) = a_n-1+a₀x+…+a_n-2x^n-1, который можно выразить через первоначальный:

Поскольку полиномиальный код должен делиться на g(x), то для того, чтобы он был циклическим, многочлен a'(x) должен делиться на g(x). Из этого соображения можно сформулировать следующую теорему. Полиномиальный код является циклическим тогда и только тогда, когда многочлен g(x) является делителем многочлена xⁿ–1. В этом случае многочлен g(x) называется порождающим многочленом циклического кода.

В теории кодирования доказывается следующая теорема: если многочлен g(x) имеет степень n–k и является делителем xⁿ–1, то C(g(x)) является линейным циклическим (n, k)-кодом.

Многочлен xⁿ–1 разложим на множители xⁿ–1 = (x–1)(x^n-1+x^n-1+…+1). Следовательно, циклические коды существуют при любом n. Число циклических n-разрядных кодов равно числу делителей многочлена xⁿ–1. Для построения циклических кодов разработаны таблицы разложения многочленов xⁿ–1 на неприводимые многочлены, то есть на такие, которые делятся только на единицу и на самого себя.

Рассмотрим, например, какие коды можно построить на основе многочлена x⁷–1 над полем GF(2). Разложение многочлена на неприводимые множители имеет вид

Поскольку можно образовать шесть делителей многочлена x⁷–1, комбинируя неприводимые делители, существует шесть двоичных циклических кодов. (n, k)-код определяется, во-первых, значением n, а во-вторых, значением k = n – s, s – степень многочлена-делителя xⁿ–1, определяющего код. Ниже приведены делители полинома и соответствующие им значения k:

x – 1, s=1, k=6;

x³+x²+1, s=3, k=4;

x³+x+1, s=3, k=4;

(x–1)(x³+x²+1)=x⁴+x²+x+1, s=4, k=3;

(x–1)(x³+x+1)=x⁴+x³+x²+1, s=4, k=3;

(x³+x²+1)( x³+x+1)=x⁶+ x⁵+ x⁴+ x³+ x²+ x, s=6, k=1.

(7, 6)-код имеет лишь один проверочный символ, а (7, 1)-код – лишь один информационный. Они являются соответственно кодом с проверкой на чётность и кодом с повторением.

Как и обычный линейный код, циклический код может быть задан порождающей матрицей. Следовательно, задача состоит в том, чтобы найти такую матрицу, то есть найти k линейно независимых кодовых комбинаций, образующих её. Воспользуемся для этого свойством замкнутости циклического кода относительно операции циклического сдвига. Заметим, что циклический сдвиг вправо на один разряд эквивалентен умножению многочлена g(x) на x. Тогда порождающую матрицу можно построить, взяв в качестве строк порождающий многочлен и k его циклических сдвигов:

Например, рассмотрим один из делителей многочлена x⁷–1, а именно полином g(x)=1+x+x³. Ему соответствует кодовая комбинация 1101000 (выписаны коэффициенты при степенях 0, 1, …, 6 порождающего многочлена, так как кодовая комбинация содержит 7 символов). Тогда порождающая матрица (7,4) имеет вид

Рассмотрим теперь, как с помощью порождающего многочлена g(x) = 1+x+x³ осуществляется кодирование (7, 4)-кодом. Возьмём, например, 4-разрядное слово (0101), которому соответствует многочлен f(x) = x + x³. Перемножив эти два многочлена:

f(x)g(x) = (x+x³)(1+x+x³) = x+x²+x³+x⁶,

получим кодовую комбинацию 0111001. Аналогично можно получить кодовые слова для всех 4-разрядных двоичных слов. Однако получившийся код, как видно, не является разделимым, что неудобно для практических нужд.

Чтобы закодировать сообщение h(x) циклическим кодом C(g(x)), который является разделимым, нужно разделить многочлен x^n-kh(x) на g(x) и прибавит остаток от деления к многочлену x^n-kh(x).

Для примера рассмотрим кодовую комбинацию 1101. Этому вектору соответствует полином h(x)=1+x+x³. Тогда x^n-k h(x)=x³+x⁴+x⁶. Разделим получившийся многочлен на g(x) = 1+x+x³, получим остаток, равный 0. Тогда кодовый вектор равен 0001101.