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

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

Пусть ${\displaystyle {\overline {y}}=(y_{0},y_{1},\dots ,y_{n-1})\in L^{n}}$ — слово длины n над алфавитом из элементов конечного поля ${\displaystyle L=GF(q)}$ и ${\displaystyle y(x)=y_{0}+y_{1}x+y_{2}x^{2}+\dots +y_{n-1}x^{n-1}}$ — полином, соответствующий этому слову, от формальной переменной ${\displaystyle x}$. Видно, что это соответствие является изоморфизмом линейных пространств. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации ${\displaystyle {\overline {y}}=m_{1}{\overline {y_{1}}}+m_{2}{\overline {y_{2}}}}$ пары слов ${\displaystyle {\overline {y_{1}}}=(y_{1,0},\dots ,y_{1,n-1})}$ и ${\displaystyle {\overline {y_{2}}}=(y_{2,0},\dots ,y_{2,n-1})}$, равен линейной комбинации полиномов этих слов ${\displaystyle {y}(x)=\sum _{k=0}^{n-1}(m_{1}y_{1k}+m_{2}y_{2k})x^{k}=m_{1}{\overline {y_{1}}}(x)+m_{2}{\overline {y_{2}}}(x)}$.

Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n − 1 над полем ${\displaystyle GF(q)}$.

Если ${\displaystyle {\overrightarrow {c_{1}}}}$ — кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова ${\displaystyle {\overrightarrow {c}}}$, то соответствующий ему полином ${\displaystyle c_{1}(x)}$ получается из предыдущего умножением на x:

${\displaystyle c_{1}(x)=xc(x)\mod (x^{n}-1)}$, пользуясь тем, что ${\displaystyle x^{n}\equiv 1\mod (x^{n}-1).}$

Сдвиг вправо и влево соответственно на ${\displaystyle j}$ разрядов:

${\displaystyle c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),}$

${\displaystyle c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).}$

Если ${\displaystyle m(x)}$ — произвольный полином над полем ${\displaystyle GF(q)}$, и ${\displaystyle c(x)}$ — кодовое слово циклического ${\displaystyle (n,k)}$ кода, то ${\displaystyle m(x)c(x)\mod (x^{n}-1)}$ — тоже кодовое слово этого кода.

Определение

Порождающим полиномом циклического ${\displaystyle (n,k)}$ кода ${\displaystyle C}$ называется такой ненулевой полином ${\displaystyle g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i}}$ из ${\displaystyle C}$, степень которого наименьшая, и коэффициент при старшей степени ${\displaystyle g_{r}=1}$.

Теорема 1

Если ${\displaystyle C}$ — циклический ${\displaystyle (n,k)}$ код, и ${\displaystyle g(x)}$ — его порождающий полином, то степень ${\displaystyle g(x)}$ равна ${\displaystyle r=n-k}$, и каждое кодовое слово может быть единственным образом представлено в виде

${\displaystyle c(x)=m(x)g(x),}$

где степень ${\displaystyle m(x)}$ меньше или равна ${\displaystyle k-1}$.

Теорема 2

${\displaystyle g(x)}$ — порождающий полином циклического ${\displaystyle (n,k)}$ кода — является делителем двучлена ${\displaystyle x^{n}-1}$.

Следствия

Таким образом, в качестве порождающего полинома можно выбирать любой полином делитель ${\displaystyle x^{n}-1}$. Степень выбранного полинома будет определять количество проверочных символов ${\displaystyle r}$, число информационных символов ${\displaystyle k=n-r}$.

Полиномы ${\displaystyle g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)}$ линейно независимы, иначе ${\displaystyle m(x)g(x)=0}$ при ненулевом ${\displaystyle m(x)}$, что невозможно.

Значит кодовые слова можно записывать, как и для линейных кодов, следующим образом:

${\displaystyle {\overline {m}}G=(m_{0},m_{1},\dots ,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\\\dots \\x^{k-1}g(x)\end{bmatrix}}=m(x)g(x),}$

где ${\displaystyle G}$ является порождающей матрицей, ${\displaystyle m(x)}$ — информационным полиномом.

Матрицу ${\displaystyle G}$ можно записать в символьной форме:

${\displaystyle G={\begin{bmatrix}g_{0}&g_{1}&\dots &g_{r-1}&g_{r}&0&\dots &0\\0&g_{0}&\dots &g_{r-2}&g_{r-1}&g_{r}&\dots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&\dots &0&g_{0}&g_{1}&\dots &g_{r}\end{bmatrix}}.}$

Для каждого кодового слова циклического кода справедливо ${\displaystyle c(x)=0\mod g(x)}$. Поэтому проверочную матрицу можно записать как

${\displaystyle H={\begin{bmatrix}1&x&x^{2}&\dots &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).}$

Тогда

${\displaystyle {\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).}$

При несистематическом кодировании кодовое слово получается в виде произведения информационного полинома на порождающий:

${\displaystyle c(x)=m(x)g(x).}$

Оно может быть реализовано при помощи перемножения полиномов.

При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного:

${\displaystyle c(x)=[s(x)\;m(x)].}$

Пусть информационное слово образует старшие степени кодового слова, тогда

${\displaystyle c(x)=x^{r}m(x)+s(x),\quad r=n-k.}$

Тогда из условия ${\displaystyle c(x)=x^{r}m(x)+s(x)=0\mod g(x)}$ следует

${\displaystyle s(x)=-x^{r}m(x)\mod g(x).}$

Это уравнение и задаёт правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров (МЛФ).

В качестве делителя ${\displaystyle x^{7}-1}$ выберем порождающий полином третьей степени ${\displaystyle g(x)=x^{3}+x+1}$, тогда полученный код будет иметь длину ${\displaystyle n=7}$, число проверочных символов (степень порождающего полинома) ${\displaystyle r=3}$, число информационных символов ${\displaystyle k=4}$, минимальное расстояние ${\displaystyle d=3}$.

Порождающая матрица кода:

${\displaystyle G={\begin{bmatrix}1&1&0&1&0&0&0\\0&1&1&0&1&0&0\\0&0&1&1&0&1&0\\0&0&0&1&1&0&1\end{bmatrix}},}$

где первая строка представляет собой запись полинома ${\displaystyle g(x)}$ коэффициентами по возрастанию степени.

Остальные строки — циклические сдвиги первой строки.

Проверочная матрица:

${\displaystyle H={\begin{bmatrix}1&0&0&1&0&1&1\\0&1&0&1&1&1&0\\0&0&1&0&1&1&1\end{bmatrix}},}$

где i-й столбец, начиная с 1-го, представляет собой остаток от деления ${\displaystyle x^{i-1}}$ на полином ${\displaystyle g(x)}$, записанный по возрастанию степеней, начиная сверху.

Так, например, 4-й столбец получается ${\displaystyle h_{4}(x)=x^{3}\mod g(x)=x+1}$, или в векторной записи ${\displaystyle [110]}$.

Легко убедиться, что ${\displaystyle GH^{T}=0}$.

В качестве порождающего полинома ${\displaystyle g(x)}$ можно выбрать произведение двух делителей ${\displaystyle x^{15}-1}$:

${\displaystyle g(x)=g_{1}(x)g_{2}(x)=(x^{4}+x+1)(x^{4}+x^{3}+x^{2}+x+1)=x^{8}+x^{7}+x^{6}+x^{4}+1.}$

Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома ${\displaystyle m(x)}$ со степенью ${\displaystyle k-1}$ таким образом:

${\displaystyle c(x)=m(x)g(x).}$

Например, информационному слову ${\displaystyle {\overline {m}}=[1000111]}$ соответствует полином ${\displaystyle m(x)=x^{6}+x^{5}+x^{4}+1}$, тогда кодовое слово ${\displaystyle c(x)=(x^{6}+x^{5}+x^{4}+1)(x^{8}+x^{7}+x^{6}+x^{4}+1)=x^{14}+x^{12}+x^{9}+x^{7}+x^{5}+1}$, или в векторном виде ${\displaystyle {\overline {c}}=[100001010100101]}$.

• Обнаружение и исправление ошибок
• Линейный код
• БЧХ код
• Конечное поле
• Многочлен над конечным полем
• Код Рида — Соломона
• Код Хэмминга

• Механизмы контроля целостности данных.