Раздел разработан в 2010 г. при поддержке компании ((http://www.raidixstorage.com/ru/ RAIDIX))
----
~~TOC~~
==Циклические коды==
Рассмотрим ((:linear_space:gf2 линейное пространство)) $ \mathbb V^n $ двоичных кодов, т.е. упорядоченных наборов (строк) $ (x_1,\dots,x_{n}) $ из $ n_{} $ чисел $ \{x_1,\dots,x_n\}\subset \{0,1\} $.
Рассмотрим непустое подмножество $ \mathbb U $ пространства $ \mathbb V^n $, обладающее следующим свойством: если строка $ (u_1,u_2,\dots,u_n) $ принадлежит $ \mathbb U $, то этому подмножеству принадлежит и строка, полученная из этой в результате циклического сдвига вправо:
$$ (u_n,u_1,u_2,\dots,u_{n-1}) \in \mathbb U $$
т.е. все компоненты (разряды) вектора сдвигаются вправо на одну позицию, тот элемент, что при этом сдвиге "вываливается" за пределы строки, переставляется в ее начало.
Очевидно, что:
$$ (u_{n-1},u_n,u_1\dots,u_{n-2}) \in \mathbb U , \dots , (u_2,u_3,\dots,u_{n-1},u_{1}) \in \mathbb U \ , $$
т.е. множество $ \mathbb U $ должно содержать, по крайней мере, $ n_{} $ строк (которые, впрочем, не обязательно будут различными). Если, вдобавок, множество $ \mathbb U $ является подпространством пространства $ \mathbb V^n $, т.е. замкнуто относительно операции сложения строк по модулю $ 2_{} $, то такое множество называется **циклическим кодом**. Будем обозначать его буквой $ C_{} $.
Заметим, что циклический код можно определить и на основе циклического сдвига __влево__:
$$
\begin{array}{c}
\rightarrow \\
\begin{array}{c}
(u_1,u_2,u_3, u_4, u_5) \\
(u_5,u_1, u_2, u_3, u_4) \\
(u_4,u_5, u_1, u_2, u_3) \\
(u_3,u_4, u_5, u_1, u_2) \\
(u_2,u_3, u_4, u_5, u_1)
\end{array}
\end{array} \qquad \qquad
\begin{array}{c}
\leftarrow \\
\begin{array}{c}
(u_1,u_2, u_3, u_4, u_5) \\
(u_2, u_3, u_4, u_5, u_1) \\
(u_3, u_4, u_5, u_1, u_2) \\
(u_4,u_5, u_1, u_2, u_3) \\
(u_5,u_1, u_2, u_3, u_4)
\end{array}
\end{array}
$$
В самом деле, правый набор строк получается в результате перестановки строк левого набора.
===Структура кода==
Для прояснения идейных основ использования циклических кодов в зашумленных каналах связи рассмотрим сначала их прототип в $ \mathbb Z^n $, т.е. в пространстве строк с целочисленными элементами.
С точки зрения ((:linear_space#определения традиционного для линейной алгебры определения)), $ \mathbb Z^n $ не является линейным пространством. Тем не менее если рассмотреть его как множество строк с целочисленными компонентами
$$ \mathbb Z^n = \left\{ (x_1,\dots,x_n)\ \mid \ \{x_j\}_{j=1}^n \subset \mathbb Z \right\} $$
относительно операций покомпонентного сложения и умножения на __целочисленные__ скаляры, то все аксиомы
1
-
8
((:linear_space#определения линейного векторного пространства)) будут выполнены.
Рассмотрим строку $ (a_{0},a_{1},\dots,a_{n-1}) \in \mathbb Z^n $. Она порождает следующую ((:algebra2:cyclic циклическую матрицу))
$$
\mathfrak C=\left(\begin{array}{lllll}
a_{0} & a_{1} & a_2 & \dots & a_{n-1} \\
a_{n-1} & a_{0} & a_{1} & \dots & a_{n-2} \\
a_{n-2} & a_{n-1} & a_{0} & \dots & a_{n-3} \\
\vdots & & & & \vdots \\
a_{1} & a_{2} & a_{3} & \dots & a_{0}
\end{array}
\right) \ .
$$
Тогда ((:linear_space#линейная_зависимость_базис_координаты линейная оболочка)) строк этой матрицы
$$ \mathcal L (\mathfrak C^{[1]},\mathfrak C^{[2]},\dots, \mathfrak C^{[n]}) $$
образует циклический код $ C_{} $. Чему равна ((:linear_space#линейная_зависимость_базис_координаты размерность)) $ \dim C $ этого подпространства ? Очевидно, это будет зависеть от вида строки
$ (a_{0},a_{1},\dots,a_{n-1}) $. Так,
$$ . \mbox{ при выборе } \quad a_0=1,a_{1}=0,a_{2}=0,\dots,a_{n-1}=0, \quad \mbox{ получим } \dim C = n \ , $$
$$ . \mbox{ при выборе } \quad a_{0}=1,a_{1}=1,\dots,a_{n-1}=1 \quad \mbox{ получим } \dim C = 1 \ . $$
В общем же случае, вопрос можно переформулировать в терминах ((:algebra2:rank#ранг_матрицы ранга матрицы)) $ {\mathfrak C} $. Вычисление этого ранга проведем с использованием соображений из пункта
☞
((:algebra2:cyclic ЦИКЛИЧЕСКАЯ МАТРИЦА)).
Рассмотрим полином $ g(x)= a_{0}+ a_{1}x+ \dots +a_{n-2}x^{n-2}+ a_{n-1}x^{n-1} $. Вычислим остаток $ g_1(x) $ от деления произведения $ x\cdot g(x) $ на полином $ x^{n}-1 $:
$$ x\cdot g(x) \equiv a_{0}x+ a_{1}x^2+ \dots + a_{n-2}x^{n-1}+ a_{n-1}x^{n} \equiv
$$
$$
\equiv a_{0}x+ a_{1}x^2+ \dots + a_{n-2}x^{n-1}+a_{n-1}(x^{n}-1+1) \equiv
$$
$$
\equiv \underbrace{a_{n-1}+a_{0}x+ a_{1}x^2+ \dots + a_{n-2}x^{n-1}}_{g_{_1}(x)} + a_{n-1}(x^{n}-1) \ .
$$
Оказывается, что коэффициенты остатка даются второй строкой матрицы $ \mathfrak C $. Далее по аналогии остаток от деления произведения $ x^2\cdot g(x) $ на полином $ x^{n}-1 $ совпадает с остатком от деления $ x\cdot g_1(x) $ на $ x^{n}-1 $ и коэффициенты этого остатка даются третьей строкой матрицы $ \mathfrak C $.
Вывод: матрица $ \mathfrak C_{} $ состоит из коэффициентов остатков деления полиномов $ \{x^jg(x)\}_{j=0}^{n-1} $
на $ x^{n}-1 $. Будем говорить, что **полином** $ g_{} (x) $ **порождает циклический код** $ C_{} $.
Оказывается, ранг матрицы $ \mathfrak C_{} $ связан с ((:polynomial#наибольший_общий_делитель наибольшим общим делителем)) полиномов $ g_{}(x) $ и $ x^{n}-1 $.
!!Т!! **Теорема 1.** //Если полином// $ g_{}(x) $ //порождает циклический код// $ C_{} $, //то//
$$ \operatorname{rank} ({\mathfrak C} ) = n - \deg \operatorname{HOD}(g(x),\ x^n-1) \ ; $$
$$ \det \mathfrak C_{} = \mathcal R(g(x),\ x^n-1) \ , $$
//где в правой части последней формулы стоит ((:dets:resultant результант))//.
**Доказательство**
☞
((:algebra2:cyclic ЗДЕСЬ)).
Как выяснить принадлежность заданной строки $ B= (b_{0},b_{1},\dots,b_{n-1}) \in \mathbb Z^n $ циклическому коду $ C_{} $? В общем случае, для ответа на этот вопрос приходится вычислять ранг расширенной матрицы, полученной присоединением к матрице $ \mathfrak C_{} $ данной строки[[Аналог операции ((:algebra2#конкатенация конкатенации)).]]:
$$ \tilde {\mathfrak C} = \left(\begin{array}{c} \mathfrak C \\ B \end{array} \right) \ . $$
!!Т!! **Теорема 2.** //Имеем://
$$ B \in C \qquad \iff \qquad \operatorname{rank} ({\mathfrak C} ) = \operatorname{rank} ( \tilde {\mathfrak C} ) \ . $$
!!П!! **Пример.** Пусть $ n_{}=4 $ и циклический код $ C_{} $ порождается полиномом $ g(x)=-2+2\,x-x^2+x^3 $. Имеем:
$$
\mathfrak C=\left(\begin{array}{rrrr}
-2&2&-1&1\\
1&-2&2&-1\\
-1&1&-2&2\\
2&-1&1&-2
\end{array}
\right)
$$
и $ \operatorname{rank} ({\mathfrak C} ) = 3 $ поскольку $ \det {\mathfrak C} =0 $, а
$$
\left|
\begin{array}{rrr}
-2&2&-1\\
1&-2&2\\
-1&1&-2
\end{array}
\right| \ne 0 \ .
$$
Пусть теперь требуется установить значения параметра $ {\color{Red} \alpha } $, при которых строка
$ B= (-3,1,{\color{Red} \alpha },2) $ принадлежит циклическому коду $ C_{} $. Имеем, согласно теореме 2:
$$
B \in C \quad \iff \quad
\operatorname{rank} \left(\begin{array}{rrrr}
-2&2&-1&1\\
1&-2&2&-1\\
-1&1&-2&2\\
2&-1&1&-2 \\
-3&1&{\color{Red} \alpha }& 2
\end{array}
\right)=3 \quad \iff
$$
$$
\iff \quad
\left|\begin{array}{rrrr}
-2&2&-1&1\\
1&-2&2&-1\\
-1&1&-2&2\\
-3&1&{\color{Red} \alpha } & 2
\end{array}
\right|=0 \quad \iff \quad {\color{Red} \alpha }=0 \ .
$$
♦
!!!!! Попробуем теперь выбрать порождающий циклический код полином $ g(x) $ среди делителей полинома $ x^{n}-1 $.
!!Т!! **Теорема 3.**// Пусть порождающий полином//
$$ g(x)=a_0+a_1x+\dots+a_rx^r\in \mathbb Z[x], (0< r
♦