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

Определение

Порождающим полиномом циклического ${\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]}$.