Рассмотрим линейное пространство $ \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_{} $.

Для прояснения идейных основ использования циклических кодов в зашумленных каналах связи рассмотрим сначала их прототип в $ \mathbb Z^n $, т.е. в пространстве строк с целочисленными элементами.

Рассмотрим строку $ (a_{0},a_{1},\dots,a_{n-1}) \in \mathbb Z^n $. Она порождает следующую циклическую матрицу $$ \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) \ . $$ Тогда линейная оболочка строк этой матрицы $$ \mathcal L (\mathfrak C^{[1]},\mathfrak C^{[2]},\dots, \mathfrak C^{[n]}) $$ образует циклический код $ C_{} $. Чему равна размерность $ \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 \ . $$ В общем же случае, вопрос можно переформулировать в терминах ранга матрицы $ {\mathfrak C} $. Вычисление этого ранга проведем с использованием соображений из пункта ☞ ЦИКЛИЧЕСКАЯ МАТРИЦА.

Рассмотрим полином $ 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_{} $ связан с наибольшим общим делителем полиномов $ 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) \ , $$ где в правой части последней формулы стоит результант.

Доказательство ☞ ЗДЕСЬ.

Как выяснить принадлежность заданной строки $ B= (b_{0},b_{1},\dots,b_{n-1}) \in \mathbb Z^n $ циклическому коду $ C_{} $? В общем случае, для ответа на этот вопрос приходится вычислять ранг расширенной матрицы, полученной присоединением к матрице $ \mathfrak C_{} $ данной строки¹⁾: $$ \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<n, a_r\ne 0) $$ кода $ C_{} $ является делителем полинома $ x^{n}-1 $. Тогда $ \operatorname{rank} (\mathfrak C_{} ) = n - r $. Строка $ (b_0,b_1,\dots,b_{n-1}) $ принадлежит коду $ C_{} $ тогда и только тогда, когда полином $ b_0+b_1x+\dots+b_{n-1}x^{n-1} $ делится на $ g(x) $.

Доказательство. Циклическая матрица имеет следующую структуру²⁾: $$ \begin{array}{rl} \mathfrak C= \left(\begin{array}{llllllll} a_0 & a_1 & \dots & a_r & 0 & \dots & 0 & 0 \\ & a_0 & \dots & a_{r-1} & a_r & \dots & 0 & 0 \\ & & \ddots & & & \ddots & & \\ & & & a_0 & a_1& \dots & & a_r \\ \hline a_r & 0 & \dots & & a_0 & \dots & & a_{r-1} \\ a_{r-1} & a_r & \dots & & & & & a_{r-2} \\ \vdots & & \ddots & & & & \ddots & \vdots \\ a_1 & a_2 & \dots & a_r & & \dots & & a_0 \end{array} \right) & \begin{array}{l} \left.\begin{array}{l} \\ \\ \\ \\ \end{array}\right\} n-r \\ \begin{array}{l} \\ \\ \\ \\ \end{array} \end{array} \end{array} $$ Поскольку $ \operatorname{HOD}(g(x),x^n-1)\equiv g(x) $, то, в соответствии с теоремой 1, $ \operatorname{rank} ({\mathfrak C} ) = n - r $. Легко видеть, что линейно независимыми строками матрицы являются первые $ n-r $ строк (над горизонтальной чертой). Строка $ B= (b_0,b_1,\dots,b_{n-1}) $, принадлежащая коду $ C_{} $, должна линейно выражаться через эти строки: $$ B=\gamma_0 (a_0,a_1,\dots,a_r,0,\dots,0)+\gamma_1 (0,a_0,a_1,\dots,a_r,\dots,0)+\dots+\gamma_{n-r-1} (0,\dots,0,a_0,\dots,a_r) \ , $$ и это равенство может быть переписано как полиномиальное тождество: $$b_0+b_1x+\dots+b_{n-1}x^{n-1}\equiv $$ $$ \equiv \gamma_0(a_0+a_1x+\dots+a_rx^{r})+\gamma_1(a_0x+a_1x^2+\dots+a_rx^{r+1})+ $$ $$ +\dots+\gamma_{n-r-1}(a_0x^{n-r-1}+a_1x^{n-r}+\dots+a_rx^{n-1}) \equiv $$ $$ \equiv (\gamma_0+\gamma_1x+\dots+\gamma_{n-r-1}x^{n-r-1})(a_0+a_1x+\dots+a_rx^{r}) \ . $$ ♦

Обозначим через $ h_{}(x) $ частное от деления $ x^n-1 $ на $ g_{}(x) $. Строка $ (b_0,b_1,\dots,b_{n-1}) $ принадлежит коду $ C_{} $ тогда и только тогда, когда

$$ (b_0+b_1x+\dots+b_{n-1}x^{n-1})h(x) \equiv 0 \pmod{x^n-1} \ . $$

Доказательство. Если $ (b_0,b_1,\dots,b_{n-1}) \in C_{} $, то, в соответствии с теоремой, полином $ G(x)= b_0+b_1x+\dots+b_{n-1}x^{n-1} $ может быть представлен в виде произведения $ Q(x) g(x) $; тогда $ Q(x) g(x)h(x) \equiv Q(x)(x^n-1) \equiv 0 \pmod{x^n-1} $.

С другой стороны, если $ G(x)h(x) \equiv 0 \pmod{x^n-1} $, то $ G(x)h(x) \equiv \tilde Q(x) (x^n-1) $ при $ \tilde Q(x) \in \mathbb Z[x] $ и, следовательно, $ G(x) \equiv \tilde Q(x) g(x) $. Применение теоремы завершает доказательство. ♦

Полином $ h_{}(x) $, связанный с порождающим циклический код $ C_{} $ полиномом $ g_{}(x) $ тождеством $$ h(x) g(x) \equiv x^n-1 $$ называется проверочным полиномом циклического кода.

Пример. Пусть $ n_{}=6 $ и циклический код порождается полиномом $ g(x)=1+2\,x+2\,x^2+x^3 $. Проверить принадлежность строки $ B=(-1,-1,1,3,3,1) $ данному коду.

Решение. Имеем: $$ x^6-1\equiv \overbrace{(x^3+2\,x^2+2\,x+1)}^{=g(x)}\overbrace{(x^3-2\,x^2+2\,x-1)}^{=h(x)} \ . $$

1. Можно действовать по аналогии с предыдущим примером и вычислить $ \operatorname{rank} (\tilde {\mathfrak C}) $.

2. Можно, в соответствии с теоремой 3, составить полином $ G(x)=-1-x+x^2+3\,x^3+3\,x^4+x^5 $ и проверить его на делимость с порождающим код полиномом $ g_{}(x) $: $$ G(x)\equiv (x^2+x-1) g(x) \ . $$

3. Можно проверить выполнение условия следствия к теореме 3: $$ G(x)h(x) \equiv x^8+x^7-x^6-x^2-x+1 \equiv x^2+x-1-x^2-x+1 \pmod{x^6-1} \ . $$

4. Наконец, можно рассмотреть корни $ \lambda_1=-1,\ \lambda_2=-\frac{1}{2}+\mathbf i \frac{\sqrt{3}}{2}, \lambda_3=-\frac{1}{2}-\mathbf i \frac{\sqrt{3}}{2} $ полинома $ g_{} (x) $ и проверить, что в каждом из них полином $ G_{}(x) $ обращается в нуль.

♦

В предыдущем пункте было проведено описание циклического кода $ C_{} $ как подмножества (линейного подпространства) пространства $ \mathbb Z^n $. Теперь надо описать способы кодирования, т.е. сопоставления вектору информационных разрядов $ (x_1,\dots,x_k) $ конкретного кодового слова $ (b_0,b_1,\dots,b_{n-1}) $ из $ C_{} $.

На практике используются два способа кодирования. Оба используют циклические коды с порождающим полиномом $ g(x)=a_0+a_1x+\dots+a_{r-1}x^{r-1}+x^r $, который удовлетворяет двум условиям³⁾:

1. $ g_{}(x) $ является нетривиальным делителем полинома $ x^n-1 $;

2. его степень $ r_{} $ связана с числом информационных разрядов $ k_{} $ равенством: $ k=n-r $.

Несистематическое кодирование заключается в сопоставлении информационному вектору $ (x_1,\dots,x_k) $ кодового слова $ (b_0,b_1,\dots,b_{n-1}) $ по правилу, которое описывается на языке полиномов: $$ b_0+b_1x+\dots+b_{n-1}x^{n-1}\equiv (x_1+x_2x+\dots+x_kx^{k-1}) g(x) \ , $$ т.е. заключается в умножении «информационного» полинома на полином, порождающий код.

Систематическое кодирование заключается в сопоставлении информационному вектору $ (x_1,\dots,x_k) $ кодового слова $ (c_0,c_1,\dots,c_{n-1}) $ по правилу: $$ c_0+c_1x+\dots+c_{n-1}x^{n-1}\equiv (x_1+x_2x+\dots+x_kx^{k-1}) x^{n-k} - R(x) \ , $$ где $ R(x) $ — остаток от деления полинома $ (x_1+x_2x+\dots+x_kx^{k-1}) x^{n-k} $ на порождающий код полином $ g_{}(x) $.

На основании теоремы 3 из предыдущего ПУНКТА, можно утверждать, что оба способа кодирования корректны: полиномы $ b_0+b_1x+\dots+b_{n-1}x^{n-1} $ и $ c_0+c_1x+\dots+c_{n-1}x^{n-1} $ делятся на порождающий код полином $ g_{}(x) $, а значит, наборы их коэффициентов являются кодовыми словами.

Теперь проиллюстрируем оба этих способа на примере.

Пример. Пусть $ n_{}=6 $ и циклический код порождается полиномом $ g(x)=1+2\,x+2\,x^2+x^3 $. Найти кодовые слова, соответствующие информационному вектору $ (x_1,x_2,x_3) $.

Решение. Составляем полином $ M(x)= x_1+x_2x+x_3x^2 $.

В случае несистематического кодирования $$ M(x)g(x)\equiv x_1+(2\,x_1+x_2)x+(2\,x_1+2\,x_2+x_3)x^2+(x_1+2\,x_2+2\,x_3)x^3+ (x_2+2\,x_3)x^4+x_3x^5 \ , $$ т.е. кодовое слово имеет вид $$ (x_1,\ 2\,x_1+x_2,\ 2\,x_1+2\,x_2+x_3,\ x_1+2\,x_2+2\,x_3,\ x_2+2\,x_3,\ x_3) \ . $$ Легко убедиться, что это слово является результатом умножения информационного вектора на верхнюю часть циклической матрицы $ \mathfrak C $: $$ (x_1,x_2,x_3) \left(\begin{array}{cccccc} 1 & 2 & 2 & 1 & 0 & 0 \\ 0 & 1 & 2 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 2 & 1 \end{array} \right) \ ; $$ что, впрочем, вполне ожидаемо, если посмотреть доказательство теоремы 3 из предыдущего ПУНКТА: кодовое слово обязано быть линейной комбинацией строк циклической матрицы.

Для систематического кодирования вычисляем сначала остаток от деления $ M(x)x^3 $ на $ g_{}(x) $: $$ R(x) \equiv (-x_1+2\,x_2-2\,x_3)+(-2\,x_1+3\,x_2-2\,x_3)x+(-2\,x_1+2\,x_2-x_3)x^2 ; $$ и кодовое слово имеет вид $$ (x_1-2\,x_2+2\,x_3,\ 2\,x_1-3\,x_2+2\,x_3,\ 2\,x_1-2\,x_2+x_3,\ x_1,\ x_2,\ x_3) \ . $$ Здесь тоже можно выписать матричное представление: $$ (x_1,x_2,x_3) \left(\begin{array}{rrrrrr} 1 & 2 & 2 & 1 & 0 & 0 \\ -2 & -3 & -2 & 0 & 1 & 0 \\ 2 & 2 & 1 & 0 & 0 & 1 \end{array} \right) \ . $$ Матрица систематического кодирования может быть получена из матрицы несистематического кодирования с помощью элементарных преобразований над строками: $$ \left(\begin{array}{cccccc} 1 & 2 & 2 & 1 & 0 & 0 \\ 0 & 1 & 2 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 2 & 1 \end{array} \right)\quad \rightarrow \quad \left(\begin{array}{rrrrrr} 1 & 2 & 2 & 1 & 0 & 0 \\ -2 & -3 & -2 & 0 & 1 & 0 \\ 0 & 0 & 1 & 2 & 2 & 1 \end{array} \right) \quad \rightarrow \quad \left(\begin{array}{rrrrrr} 1 & 2 & 2 & 1 & 0 & 0 \\ -2 & -3 & -2 & 0 & 1 & 0 \\ -2 & -4 & -3 & 0 & 2 & 1 \end{array} \right) \quad \rightarrow $$ $$ \rightarrow \quad \left(\begin{array}{rrrrrr} 1 & 2 & 2 & 1 & 0 & 0 \\ -2 & -3 & -2 & 0 & 1 & 0 \\ 2 & 2 & 1 & 0 & 0 & 1 \end{array} \right) \ ; $$ и этот факт достаточно ожидаем, поскольку два способа кодирования соответствуют разным выборам кодовых слов (базисных строк) в одном и том же линейном подпространстве пространства $ \mathbb Z^n $ — циклическом коде $ C_{} $. Какую информацию содержат строки этой матрицы — какие полиномы они порождают? — Оказывается, эти строки состоят из коэффициентов полиномов вида $$ x^{j}-(b_{j,r-1}x^{r-1}+b_{j,r-2}x^{r-2}+\dots+b_{j1}x^1+b_{j0}) \quad npu \quad j\in\{r,\dots,n-1\} , $$ где полином в скобках является остатком от деления $ x^{j} $ на порождающий код полином $ g_{}(x) $. $$ x^3 \equiv -1-2\,x-2\,x^2,\ x^4 \equiv 2+3\,x+2\,x^2,\ x^5 \equiv -2-2\,x-x^2 \pmod{1+2\,x+2\,x^2+x^3} \ . $$ ♦

Вывод. Несистематический способ кодирования проще в реализации; систематический — удобнее с точки зрения расположения в кодовом слове информационных и проверочных разрядов — они объединены в блоки.

Исследование операции умножения полиномов по модулю $ x^{n}-1 $, использованной в ☝ ВЫШЕ требует отдельного пункта. Впрочем, при первом чтении этот материал можно пропустить.

Предположим, что заданы два полинома $$ f(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1} \qquad \mbox{ и } \qquad g(x)=b_0+b_1x+\dots+b_{n-1}x^{n-1} $$ с целыми коэффициентами. Организуем их умножение по модулю полинома $ x^n-1 $, действуя по схеме, которую проиллюстрируем для случая $ n_{}=5 $: $$ (a_0+a_1x+a_2x^2+a_3x^3+a_4x^4)(b_0+b_1x+b_2x^2+b_3x^3+b_4x^4) = $$ $$ = \begin{array}{l|rrrrr|rrrr} b_0\times & a_0&+a_1x&+a_2x^2 &+a_3x^3 &+a_4x^4 & + & & &\\ b_1\times & & a_0x&+a_1x^2 &+a_2x^3 &+a_3x^4 &+a_4x^5 &+ & &\\ b_2\times & & & a_0x^2 & +a_1x^3 & +a_2x^4& +a_3x^5&+a_4x^6 & + &\\ b_3\times & & & & a_0x^3 & +a_1x^4 & +a_2x^5&+a_3x^6&+a_4x^7& + \\ b_4\times & & & & & a_0x^4 & +a_1x^5& +a_2x^6&+a_3x^7&+a_4x^8 \end{array} $$ Использование соотношений $ x^5 \equiv 1, x^6 \equiv x, x^7 \equiv x^2, x^8 \equiv x^3 \pmod{x^5-1} $ позволяет циклически перебросить слагаемые, стоящие справа от правой черты влево от нее: $$ \equiv \begin{array}{l|lllll} b_0\times & a_0&+a_1x&+a_2x^2 &+a_3x^3 &+a_4x^4 + \\ b_1\times & a_4&+ a_0x&+a_1x^2 &+a_2x^3 &+a_3x^4 + \\ b_2\times & a_3&+ a_4x& +a_0x^2 & +a_1x^3 & +a_2x^4+ \\ b_3\times & a_2&+ a_3x& +a_4x^2 &+a_0x^3 & +a_1x^4 + \\ b_4\times & a_1&+ a_2x&+a_3x^2&+a_4x^3 & +a_0x^4 \end{array} \pmod{x^5-1} . $$ Дальше остается только собрать подобные члены. Результатом такого умножения полиномов будет полином $ c_0+c_1x+c_2x^2+c_3x^3+c_4x^4 $ с коэффициентами, задаваемыми соотношениями: $$ \begin{array}{llllll} c_0=&a_0b_0&+a_1b_4&+a_2b_3&+a_3b_2&+a_4b_1 \\ c_1=&a_0b_1&+a_1b_0&+a_2b_4&+a_3b_3&+a_4b_2 \\ c_2=&a_0b_2&+a_1b_1&+a_2b_0&+a_3b_4&+a_4b_3 \\ c_3=&a_0b_3&+a_1b_2&+a_2b_1&+a_3b_0&+a_4b_4 \\ c_4=&a_0b_4&+a_1b_3&+a_2b_2&+a_3b_1&+a_4b_0 \end{array} $$ Здесь коэффициенты $ a_0,a_1,a_2,a_3,a_4 $ расположены в «естественном» порядке, а их сомножители — коэффициенты $ b_4,b_3,b_2,b_1,b_0 $ — при подъеме с последней формулы вверх циклически сдвигаются влево. Эту цикличность можно «заложить» в индексы если воспользоваться модулярным формализмом: $$ c_0=\sum_{j=0}^4 a_jb_{5-j \pmod{5}},\ c_1=\sum_{j=0}^4 a_jb_{6-j \pmod{5}},\ c_2=\sum_{j=0}^4 a_jb_{7-j \pmod{5}},\ c_3=\sum_{j=0}^4 a_jb_{8-j \pmod{5}},\ c_4=\sum_{j=0}^4 a_jb_{9-j \pmod{5}} \ ; $$ как принято ☞ ЗДЕСЬ, $ n \pmod{5} $ означает остаток от деления натурального числа $ n_{} $ на $ 5_{} $.

Циклическая свёртка

Для произвольных векторов-строк $ X=(x_{1},\dots,x_n) $ и $ Y=(y_{1},\dots,y_n) $ вектор $ Z=(z_{1},\dots,z_n) $, с элементами, определяемыми формулами $$ z_k=\sum_{j=1}^n x_jy_{n+k-j \pmod{n}}= $$ $$ \begin{array}{lcl} =x_1y_k+x_2y_{k-1}+\dots+x_ky_1 & + & \\ & + & x_{k+1}y_n+x_{k+2}y_{n-1}+\dots+x_ny_{k+1} \end{array} $$ при $ k \in \{1,\dots,n\} $, называется циклической свёрткой векторов $ X_{} $ и $ Y_{} $, сама операция нахождения свертки обозначается $ \ast $: $$ Z=X\ast Y \ .$$ Аналогичное определение используется и для полиномов. Если $ f(x)=a_0+a_{1}x+\dots+a_{n-1}x^{n-1} $ и $ g(x)=b_0+b_1x+\dots+b_{n-1}x^{n-1} $, то $$ c_0+c_1x+\dots+c_{n-1}x^{n-1}=f(x)\cdot g(x) \pmod{x^n-1} \qquad \iff $$ $$ \iff \qquad (c_0,c_1,\dots,c_{n-1})= (a_0,a_1,\dots,a_{n-1})\ast (b_0,b_1,\dots,b_{n-1}) \ . $$

Задача. Организовать экономное вычисление циклической свёртки.

Решение этой задачи см. в разделе ☞ УМНОЖЕНИЕ ПОЛИНОМОВ.

Снова рассматриваем циклические коды в $ \mathbb Z^n $. В соответствии с определением, принадлежность кодового слова $ (b_0,b_1,\dots,b_{n-1}) $ циклическому коду $ C_{} $, порождаемому полиномом $ g(x)=a_0+a_1x+a_2x^2+\dots+a_{r}x^{r}, (r<n,a_{r}\ne 0) $, равносильна тому, что полином $ G(x)=b_0+b_1x+b_2x^2+\dots+b_{n-1}x^{n-1} $ делится на $ g_{}(x) $. Предположим теперь, что при передаче по зашумленному каналу связи кодовое слово исказилось и на выходе мы получили вектор $ (\tilde b_0,\tilde b_1,\dots,\tilde b_{n-1}) $. Этот вектор задает некоторый полином $ \tilde G(x)= \tilde b_0+ \tilde b_1x+ \tilde b_2x^2+\dots+ \tilde b_{n-1}x^{n-1} $.

Полином $ s_{}(x) $, равный остатку от деления полинома $ \tilde G(x) $ на порождающий циклический код полином $ g_{}(x) $, называется синдромом полинома $ \tilde G(x) $ в данном коде: $$ s(x)={\bf \mbox{СИНДРОМ }}(\tilde G(x)) = \tilde G(x) \pmod{g(x)} \ . $$

Если синдром $ s_{}(x) $ полученного на выходе из канала полинома $ \tilde G(x) $ тождественно равен $ 0_{} $, то будем считать, что ошибка передачи не обнаружена.

Пример. Пусть $ n=6 $ и циклический код порождается полиномом

$$ g(x)=1+2\,x+2\,x^2+x^3 \, . $$ Пусть при передаче по каналу кодового полинома $ G(x)=-1-x+x^2+3\,x^3+3\,x^4+x^5 $ произошла ошибка ровно в одном из коэффициентов. Вычислим синдромы получающихся полиномов $ \tilde G(x) $.

Пусть сначала «испортился» старший коэффициент и мы получили на выходе полином $$ \tilde G(x)=-1-x+x^2+3\,x^3+3\,x^4+\alpha\, x^5 \qquad npu \quad \alpha \in \mathbb Z . $$ Имеем: $$ {\bf \mbox{СИНДРОМ }}(\tilde G(x))\equiv (2-2\,\alpha)+(2-2\,\alpha)\,x+(1-\alpha)\,x^2 \ ; $$ т.е. получился полином $ 2_{} $-й степени, в котором пока трудно увидеть намек на какую-то идею. Вычислим теперь синдром от полинома $ x\tilde G(x) $: $$ {\bf \mbox{СИНДРОМ }}(x\tilde G(x))\equiv \alpha - 1 \ ; $$ и вот этот полином — вместо ожидаемой $ 2_{} $-й степени — имеет нулевую степень, т.е. равен константе. Более того, эта константа обращается в нуль как раз при том единственном значении параметра $ \alpha_{} $, которое обеспечивает совпадение полинома $ \tilde G(x) $ с кодовым полиномом $ G_{}(x) $!

Пойдем дальше: $$ {\bf \mbox{СИНДРОМ }}(x^2\tilde G(x))\equiv (\alpha - 1)x \ ; $$ т.е. синдром получается домножением предыдущего на $ x_{} $. Аналогично: $$ {\bf \mbox{СИНДРОМ }}(x^3\tilde G(x))\equiv (\alpha - 1)x^2 \ , $$ и т.д.

Попробуем теперь испортить в кодовом полиноме $ G_{}(x) $ коэффициент при $ x^{4} $: $$ \tilde G(x)=-1-x+x^2+3\,x^3+\beta\,x^4+x^5 \qquad npu \quad \beta \in \mathbb Z . $$ Снова последовательно вычисляем синдромы для последовательности $ G_{}(x),xG_{}(x),x^2G_{}(x),\dots $: $$ \begin{array}{lcl} {\bf \mbox{СИНДРОМ }}(\tilde G(x))&\equiv& (2\,\beta-6) +(3\beta-9)x+(2\beta-6)x^2, \\ {\bf \mbox{СИНДРОМ }}(x\tilde G(x))&\equiv& (6-2\beta)+(6-2\beta)x+ (3-\beta)x^2,\\ {\bf \mbox{СИНДРОМ }}(x^2\tilde G(x))&\equiv&\beta- 3, \\ {\bf \mbox{СИНДРОМ }}(x^3\tilde G(x))&\equiv&(\beta- 3)x,\\ {\bf \mbox{СИНДРОМ }}(x^4\tilde G(x))&\equiv&(\beta- 3)x^2,\\ \dots & & \dots \\ \end{array} $$ Видим проявление того же эффекта, что и в предыдущем случае: при каком-то показателе $ j_{} $ синдром полинома $ x^j \tilde G(x) $ становится равным константе, причем эта константа обращается в нуль только при значении параметра, обеспечивающем выполнение тождества $ \tilde G(x)\equiv G(x) $.

Проверим наблюдение для случая «порчи» других коэффициентов. Оформим результаты в виде таблицы: верхняя ее строка показывает при каком мономе полинома $$ G(x)=-1-x+x^2+3\,x^3+3\,x^4+x^5 $$ портится коэффициент, а сама таблица содержит степени синдромов полиномов $ x^j \tilde G(x) $ $$ \begin{array}{r|cccccc} & x^5 & x^4 & x^3 & x^2 & x & x^{0} \\ \hline \\ \tilde G & 2 & 2 & 2 & 2 & 1 & 0 \\ x\tilde G & 0 & 2 & 2 & 2 & 2 & 1 \\ x^2\tilde G & 1 & 0 & 2 & 2 & 2 & 2 \\ x^3\tilde G & 2 & 1 & 0 & 2 & 2 & 2 \\ x^4\tilde G & 2 & 2 & 1 & 0 & 2 & 2 \\ x^5\tilde G & 2 & 2 & 2 & 1 & 0 & 2 \\ x^6\tilde G & 2 & 2 & 2 & 2 & 1 & 0 \end{array} $$ Видим, что в последовательности синдромов обязательно встречается константа и встречается она при значении показателя $ j_{} $, устойчиво связанного с номером разряда кодового слова (или индекса коэффициента полинома), в котором происходит ошибка. Более того, подтверждается и другое наблюдение: эта константа обращается в нуль только при условии когда ошибки при передаче кодового слова по каналу не происходит. ♦

Теорема 1. Пусть порождающий циклический код полином $ g_{}(x) $ является нетривиальным делителем полинома $ x^{n}-1 $. Если при передаче кодового полинома $ G_{}(x) $ по каналу связи произошла ровно одна ошибка в $ j_{} $-м коэффициенте и получен полином $ \tilde G(x)=G(x)+E x^j $, то

$$ {\bf \mbox{СИНДРОМ }}(x^{n-j}\tilde G(x))\equiv E \ . $$

Доказательство. Имеем: $$ x^{n-j}\tilde G(x) \equiv x^{n-j} G(x)+E x^n \equiv E \pmod{g(x)} \ , $$ поскольку $ G_{}(x) $ делится на $ g_{}(x) $ и $ x^n-1 $ делится на $ g_{}(x) $.

Итак, ошибка обнаружена. Теперь осталось показать, что остальные синдромы — «нормальные», т.е. отличные от константы, и, следовательно, ошибка обнаружена однозначно. В общем случае это утверждение неверно. Так, к примеру, при $$ n=12,\ g=x^6-1,\ \tilde G(x)=\underbrace{1+x-x^3+x^4-x^5-x^6-x^7+x^9-x^{10}+x^{11}}_{=G(x)}+E\,x^5 $$ получим, что $$ {\bf \mbox{СИНДРОМ }}(x\tilde G(x))\equiv {\bf \mbox{СИНДРОМ }}(x^7\tilde G(x))\equiv E \ , $$ т.е. наряду с возможностью декодирования в истинный полином $ G_{}(x) $ , обнаруживается еще и «фантом» — полином $$ G_{E}(x)= 1+x-x^3+x^4+(E-1)x^5-x^6-x^7+x^9-x^{10}+(1-E)x^{11} \ , $$ являющийся кодовым при любом значении $ E \in \mathbb Z $.

Тем не менее, можно утверждать, что, как правило, такой ситуации не возникнет. Не будем пока строго обосновывать этот вывод, а покажем, что всегда возможно выбрать порождающий полином $ g_{}(x) $ так, чтобы не возникло указанного в предыдущем абзаце эффекта. Итак, фактически надо гарантировать, чтобы сравнение $$ x^{\ell} \equiv \ \gamma \pmod{g(x)} $$ при $ \gamma \in \mathbb Z $ не выполнялось ни при одном показателе $ \ell\in \{1,2,\dots,n-1\} $. С этой целью, выберем в качестве $ g_{}(x) $ полином $ g(x)\equiv (x-1)X_{n}(x) $, где $ X_n(x) $ — полином из пункта ☞ УРАВНЕНИЕ ДЕЛЕНИЯ КРУГА, корнями которого являются все первообразные корни $ n_{} $-й степени из единицы (и только такие корни). Таким образом, $ r=\deg g=\phi(n)+1 $, где $ \phi $ — функция Эйлера. Обозначим $ \lambda_1=1,\lambda_2,\dots,\lambda_r $ — корни $ g_{}(x) $. Тогда требуемое сравнение эквивалентно полиномиальному тождеству $$ \iff x^{\ell} \equiv \ g(x)Q_k(x)+ \gamma \quad npu \quad Q_k(x)\in \mathbb Z[x] \ . $$ При подстановке в него корней $ \lambda_{j} $ получаем: $$ 1=\gamma,\ \lambda_2^{\ell}=\gamma,\dots,\lambda_r^{\ell}=\gamma \ , $$ откуда $ \lambda_2^{\ell}=1 $ и это равенство невозможно при $ \ell\in \{1,2,\dots,n-1\} $ поскольку его выполнение противоречило бы первообразности корня $ \lambda_{2} $. ♦

Алгоритм. Последовательно строим синдромы полиномов $ \tilde G, x\tilde G,x^2 \tilde G,\dots, x^{n-1} \tilde G $ до тех пор, пока не встретим полином нулевой степени (константу): $ {\bf \mbox{СИНДРОМ }}(x^{n-j}\tilde G(x))=E $; заключаем, что в соответствующем моному $ x^{j} $ разряде кодового слова произошла ошибка; вычитаем эту константу из соответствующего разряда полученного слова: $$ (b_0,b_1,\dots,b_{j-1},\tilde b_j-E,\dots,b_{n-1}) $$ и получим истинное кодовое слово.

Последовательное вычисление синдромов организуется достаточно просто с учетом следующего утверждения.

Теорема 2. Если

$$ s(x)=s_0+s_1x+\dots+s_{r-1}x^{r-1} $$ — синдром полинома $ F(x) \in \mathbb Z[x] $, а $ \tilde s(x)=\tilde s_0+\tilde s_1x+\dots+ \tilde s_{r-1}x^{r-1} $ — синдром полинома $ xF(x) $, то коэффициенты $ \tilde s_j $ вычисляются по правилу: $$ \tilde s_0=-s_{r-1}a_0,\ \tilde s_1=s_0-s_{r-1}a_1,\ \tilde s_2=s_1-s_{r-1}a_2,\dots, \tilde s_{r-1}=s_{r-2}-s_{r-1}a_{r-1} \ . $$

Для исправления единичной ошибки можно также использовать проверочный полином $ h_{}(x) $ кода. В самом деле, факт ошибки устанавливается проверкой $ \tilde G(x) h(x) \not\equiv 0 \pmod{x^n-1} $.

Теорема 3. Если $ \tilde G(x)\equiv G(x)+E x^j $, то

$$ \tilde G(x) h(x) \equiv E\, x^j h(x) \pmod{x^n-1} \ , $$ т.е. место ошибки устанавливается по совпадению остатка от деления $ \tilde G(x) h(x) $ на $ x^n-1 $ с циклическим сдвигом строки коэффициентов полинома $ h_{}(x) $.

Можно развить предложенный подход к коррекции ошибок, основанный на проверке степеней синдромов последовательности $ \{x^{\ell} \tilde G(x) \}_{\ell=0}^{n-1} $, на случай появления нескольких ошибок.

Пример. Пусть $ n=12 $ и циклический код порождается полиномом $ g(x)= 1-x+2\,x^2-x^3+x^4 $. Пусть при передаче по каналу кодового полинома

$$ G(x)=1-4\,x+4\,x^2-x^3-5\,x^4+11\,x^5-13\,x^6+14\,x^7-10\,x^8+9\,x^9- $$ $$ -5\,x^{10}+3\,x^{11} $$ произошли ошибки в двух коэффициентах. Вычислим синдромы получающихся полиномов $ \tilde G(x) $. Пусть сначала испорчены два старших коэффициента: $$ \tilde G(x)=1-4\,x+4\,x^2-x^3-5\,x^4+11\,x^5-13\,x^6+14\,x^7-10\,x^8+9\,x^9+ $$ $$ +\beta x^{10}+\alpha x^{11} \quad npu \quad \{\alpha,\beta\} \subset \mathbb Z . $$ Получаем: $$ {\bf \mbox{СИНДРОМ }}(\tilde G(x))\equiv (\alpha-\beta-8)+(1-2\alpha-\beta)x+(\alpha-3)x^2+(-2-\beta-\alpha)x^3 ; $$ и степень синдрома «не внушает подозрений» — она равна ожидаемой степени остатка от деления произвольного полинома на $ g_{}(x) $. Далее, $$ {\bf \mbox{СИНДРОМ }}(x\tilde G(x))\equiv (\alpha+\beta+2)+(-2\beta-10)x+(\beta+5)x^2+(-\beta-5)x^3 , $$ и снова не подозрений нет. Но вот следующий синдром $$ {\bf \mbox{СИНДРОМ }}(x^2\tilde G(x))\equiv (\beta+5)+(\alpha-3)x $$ имеет степень меньшую $ 3_{} $, более того, обращение в нуль его коэффициентов позволяет установить исходный (кодовый) полином $ G_{}(x) $. Формально: $$ G(x) \equiv \tilde G(x) - x^{12-2}\times {\bf \mbox{СИНДРОМ }}(x^2\tilde G(x)) \ .$$

Проверим гипотезу на другом примере. Пусть $$ \tilde G(x)=1-4\,x+4\,x^2-x^3-5\,x^4+11\,x^5+\delta\,x^6+\gamma\,x^7-10\,x^8+9\,x^9-5\,x^{10}+3\,x^{11} \quad npu \quad \{\gamma,\delta\} \subset \mathbb Z . $$ Опустим вычисления, приведя только оценки степеней синдромов $$ \begin{array}{c|c|c|c|c|c|c|c} j & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline &&&&&&& \\ \deg {\bf \mbox{СИНДРОМ }}(x^j\tilde G(x)) & 3 & 3 & 3 & 3 & 3 & 3 & 1 \end{array} $$ при $$ {\bf \mbox{СИНДРОМ }}(x^6\tilde G(x))\equiv (\delta+13)+(\gamma-14)\,x \ . $$ Снова понижение степени синдрома свидетельствует об обнаружении ошибки, снова коэффициенты подсказывают величины этих ошибок: $$ G(x) \equiv \tilde G(x) - x^{12-6}\times {\bf \mbox{СИНДРОМ }}(x^6\tilde G(x)) \ .$$

Испортим теперь два коэффициента «вразбивку»: $$ \tilde G(x)=1-4\,x+4\,x^2-x^3+\zeta x^4+11\,x^5+\eta\,x^6+14\,x^7-10\,x^8+9\,x^9-5\,x^{10}+3\,x^{11} \quad npu \quad \{\zeta,\eta\} \subset \mathbb Z . $$ $$ \begin{array}{c|c|c|c|c|c|c|c|c|c} j & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline &&&&&&&& \\ \deg {\bf \mbox{СИНДРОМ }}(x^j\tilde G(x)) & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2 \end{array} $$ при $$ {\bf \mbox{СИНДРОМ }}(x^8\tilde G(x))\equiv (\zeta+5)+(\eta+13)x^2 \ . $$ Исправление возможно: $$ G(x) \equiv \tilde G(x) - x^{12-8}\times {\bf \mbox{СИНДРОМ }}(x^8\tilde G(x)) \ .$$ Однако если ошибочные коэффициенты оказываются разнесенными по полиному $ \tilde G $ немного больше, как, к примеру, в $$ \tilde G(x)=1-4\,x+4\,x^2-x^3-5\,x^4+\theta x^5-13\,x^6+14\,x^7+\xi\,x^8+9\,x^9-5\,x^{10}+3\,x^{11} \ , $$ то оценки степеней синдромов последовательности $ \{x^{\ell} \tilde G(x) \}_{\ell=0}^{11} $ не позволят определить местоположение ошибок, поскольку все они имеют степень $ 3_{} $. Хотя наблюдательный читатель — с помощью интуиции — выделит в последовательности этих синдромов один, отличающийся по внешнему виду от остальных, именно — $$ {\bf \mbox{СИНДРОМ }}(x^7\tilde G(x))\equiv (\theta-11)+(10+\xi)\,x^3 \ , $$ и убедится, что кодовый полином получится по формуле, которую вывели выше: $$ G(x) \equiv \tilde G(x) - x^{12-7}\times {\bf \mbox{СИНДРОМ }}(x^7\tilde G(x)) \ ;$$ но эту человеческую бдительность трудно реализовать программно… ♦

Возникает подозрение, что обнаруженный эффект понижения степени синдрома сработает и в общем случае: $$ \tilde G(x)=G(x)+x^j E(x) $$ при $ \deg E< r=\deg g $, т.е. в случае, когда при передаче по каналу ошибки происходят серией⁴⁾ в (не более чем) $ \deg E(x) $ подряд идущих разрядах. Действительно, при таком ограничении на степень полинома $ E(x) $ имеем: $$ {\bf \mbox{СИНДРОМ }}(x^{n-j} \tilde G(x)) \equiv E(x) \ , $$ т.е. «поврежденный кусок» при проверке не пропустим. Если же, вдобавок, $ \deg E(x) $ много меньше $ r_{} $, то «место повреждения» — число $ j_{} $ — будем производить по принципу максимального правдоподобия, полагая $$ j=\min_{\ell\in\{0,1,\dots,n-1\}} \deg {\bf \mbox{СИНДРОМ }}(x^{n-\ell} \tilde G(x)) \ ; $$ иными словами, выбирая из последовательности синдромов те, что имеют минимальную степень.

Можно сходу придумать контрпример к предлагаемой схеме.

Пример. Пусть

$$ n=18,\ g(x)= 1+x+x^2-x^3-x^4-x^5+x^6+x^7+x^8 ,$$ и полученный полином имеет вид: $$ \tilde G(x)= 10+4\,x+8\,x^2-15\,x^3-9\,x^4-12\,x^5+12\,x^6+13\,x^7+18\,x^8+8\,x^9 $$ $$ -8\,x^{11}-11\,x^{12}-5\,x^{13}+4\,x^{14}+9\,x^{15}+9\,x^{16}+2\,x^{17} \ . $$ Подобрать кодовый полином $ G_{}(x) $, «породивший» $ \tilde G(x) $.

Решение. Последовательным вычислением синдромов полиномов $ x^{n-\ell} \tilde G(x) $ обнаружим полиномы минимальной степени $$ x^6\tilde G(x)\equiv 2-x^3 \qquad u \qquad x^{12}\tilde G(x)\equiv -1+2\,x^3 \ . $$ Таким образом, кодовыми полиномами, выбираемыми по критерию минимализации степени синдрома оказываются два: $$ G_1(x)\equiv \tilde G(x) - (-2\,x^{12}+x^{15}) \qquad u \qquad G_2(x)\equiv \tilde G(x)-(x^6-2\,x^9) \ . $$ ♦

Однако нельзя слишком уж сильно портить линейный код: понятие кодового расстояния не зря вводилось…

Вернемся к случаю одиночной ошибки, описанному в теореме $ 1_{} $ предыдущего пункта. Пусть $ \tilde G(x) \equiv G(x)+E x^j $, где $ E\in \mathbb Z $ и $ G_{}(x) $ — кодовый полином. Последнее означает, что $ G_{}(x) $ делится нацело на полином $ g_{}(x) $, порождающий циклический код: $ G_{}(x) \equiv Q(x)g(x) $ при $ Q(x)\in \mathbb Z[x] $.

Рассмотрим какой-то из корней полинома $ g_{}(x) $; поскольку $ g_{}(x) $ договорились выбирать среди делителей полинома $ x^n -1 $, то этот корень — это корень $ n_{} $-й степени из $ 1_{} $ и, в общем случае, комплексное число. Обозначим его $ \varepsilon_{} $. Подстановка $ x=\varepsilon_{} $ в кодовый полином $ G_{}(x) $ даст $ 0_{} $, а в полином $ \tilde G(x) $ — величину $$ \tilde G(\varepsilon_{}) = G(\varepsilon)+E \varepsilon_{}^j = E \varepsilon_{}^j \ . $$

Таким образом, место ошибки (т.е. поврежденного коэффициента = разряда кодового слова) обнаруживается по совпадению числа $ \tilde G(\varepsilon_{}) $ с элементом последовательности $$ E \varepsilon_{}^0,\ E \varepsilon_{}^1,\ E \varepsilon_{}^2,\dots, E \varepsilon_{}^{n-1} \ . $$ При дополнительном условии, что в этой последовательности не будет одинаковых элементов (или коллизий).

Последнее замечание накладывает дополнительное ограничение на выбор полинома $ g_{} $. Выберем его так, чтобы среди его корней находился хотя бы один первообразный корень степени n из единицы. Для определенности, пусть это будет корень $$ \varepsilon_1= \cos \frac{2 \pi}{n} + \mathbf i \sin \frac{2 \pi}{n} \ . $$ Тогда, по теореме из пункта ☞ КОРНИ ИЗ ЕДИНИЦЫ, все элементы последовательности $ \{ \varepsilon_1^k \}_{k=0}^{n-1} $ будут различными и представление комплексного числа $ \tilde G(\varepsilon_1) $ в тригонометрической форме: $$ \tilde G(\varepsilon_1) = \rho \left( \cos \varphi + \mathbf i \sin \varphi \right) \quad npu \quad \varphi\in [0,2\, \pi [ , $$ позволит однозначно определить место ошибки $ j_{} $ и ее величину $ E_{} $ по формулам: $$ E= \rho,\quad \ 2\pi k/n= \varphi \ . $$ В предложенной схеме есть один изъян, который проиллюстрируем на примере.

Пример. Пусть

$$ n=6,\ g(x)=-1+2\,x-2\,x^2+x^3 \, ;. $$ Корнем $ g_{}(x) $ является $ \varepsilon_1=\frac{1}{2}+ \mathbf i \frac{\sqrt{3}}{2} $ — первообразный корень $ 6_{} $-й степени из единицы.

Пусть при передаче кодового полинома $ G(x)=3-5\,x+2\,x^2+3\,x^3-5\,x^4+2\,x^5 $ произошла одна ошибка и на выходе из канала получен полином $ \tilde G(x)\equiv G(x)-3\,x^2 $. Подставляем в него $ x=\varepsilon_1 $: $$ \tilde G(\varepsilon_1)=\frac{3}{2}(1-\mathbf i \sqrt{3}) $$ и начинаем сравнивать полученное выражение со степенями $ \varepsilon_1^k $: $$ \{ \varepsilon_1^k \}_{k=0}^{5}=1,\ \frac{1}{2}(1+\mathbf i \sqrt{3}),\ \frac{1}{2}(-1+\mathbf i \sqrt{3}),\ -1, \frac{1}{2}(-1-\mathbf i \sqrt{3}),\ \frac{1}{2}(1-\mathbf i \sqrt{3})\ . $$ Видим, что возможны два варианта: $$ \tilde G(\varepsilon_1)=- 3 \varepsilon_1^2=3 \varepsilon_1^5 \ . $$ Эта неоднозначность возникла вследствие того, что в предложенной выше схеме мы ошибочно предположили величину $ E_{} $ положительной. ♦

Для ликвидации изъяна схемы, будем выбирать $ n_{} $ нечетным. Тогда множество $ \{ \varepsilon_1^k \}_{k=0}^{n-1} $ теряет симметрию относительно начала координат и ошибку будем обнаруживать проверкой условия ee вещественности⁵⁾: $$ \tilde G(\varepsilon_1)/\varepsilon_1^k \in \mathbb R \quad \iff \quad \tilde G(\varepsilon_1)\varepsilon_1^{n-k} \in \mathbb R \ . $$ (Последнее соотношение следует из равенства $ \varepsilon_1^k \varepsilon_1^{n-k}= \varepsilon_1^{n}=1 $.)

Пример. Пусть

$$ n=15,\ g(x)=1-x+x^3-x^4+x^5-x^7+x^8 $$ Корнем $ g_{}(x) $ является $$ \varepsilon_1= \frac{1}{8}\left(1+\sqrt{5}+\sqrt{30-6\sqrt{5}}+\mathbf i\left[-\sqrt{10-2\,\sqrt{5}}+\sqrt{3}+\sqrt{15}\right]\right)\approx 0.913545+ 0.406737 \, \mathbf i $$ — первообразный корень $ 15_{} $-й степени из единицы.

Пусть при передаче кодового полинома $$ G(x)=-2+6\,x-5\,x^2+x^3+x^4-5\,x^5+10\,x^6-6\,x^7-2\,x^8+5\,x^9-6\,x^{10}+7\,x^{11}-2\,x^{12}-3\,x^{13}+2\,x^{14} $$ произошла одна ошибка и на выходе из канала получен полином $ \tilde G(x)\equiv G(x)-2\,x^4 $. Домножаем $ \tilde G(\varepsilon_1) $ на степени $ \varepsilon_1 $ и проверяем полученные выражения на вещественность⁶⁾: $$ \tilde G(\varepsilon_1)\approx 0.209057-1.989044\, \mathbf i,\ \tilde G(\varepsilon_1)\varepsilon_1= 1- \sqrt{3} \, \mathbf i,\ \tilde G(\varepsilon_1)\varepsilon_1^2\approx 1.956295+0.415823 \, \mathbf i, \dots, \tilde G(\varepsilon_1)\varepsilon_1^{11}=-2, \dots $$ Здесь ошибка обнаруживается однозначно. ♦

Можно ли развить этот подход до метода исправления двух (и более) ошибок? Попробуем это сделать для случая ошибок, возникших в двух соседних коэффициентах. Если это — младшие коэффициенты полинома: $$ \tilde G(x)\equiv G(x)+E_0+E_1x \ , $$ то при $ r=\deg g>2 $ линейный полином $ E_0+E_1x $ представляет собой остаток от деления $ \tilde G(x) $ на порождащий код полином $ g_{}(x) $: поскольку $ G_{}(x) $ — кодовый полином, то $ G(x) \equiv Q(x) g(x) $ при $ Q(x)\in \mathbb Z $, но тогда тождество $$ \tilde G(x)\equiv Q(x) g(x)+E_0+E_1x $$ фактически является определением остатка и частного от деления $ \tilde G(x) $ на $ g_{}(x) $.

Если мы знаем выражения для хотя бы двух корней $ \lambda_{1} $ и $ \lambda_{2} $ полинома $ g_{}(x) $, то мы сможем установить коэффициенты $ E_0+E_1x $ из системы линейных уравнений: $$ \tilde G(\lambda_1)=E_0+E_1 \lambda_1,\ \tilde G(\lambda_2)=E_0+E_1 \lambda_2 \ . $$ Схема понятна, и очевидным образом обобщается на случай, если полином $ \tilde G(x) $ содержит больше двух ошибок, но они сконцентрированы в младших $ r-1 $ коэффициентах этого полинома — в этом случае, фактически, задача превращается в задачу полиномиальной интерполяции. Но вот общую ситуацию, когда расположение двух подряд идущих ошибок, т.е. число $ j_{} $ в $$ \tilde G(x)\equiv G(x)+E_jx^j+E_{j+1}x^{j+1} $$ неизвестно, предложенный подход не покроет — например, в случае $ j+1 \ge r $. Альтернативой может служить следующий алгоритм, который мы изложим в слегка упрощенном варианте, выбрав в качестве порождающего полинома $ g_{}(x) $ полином, имеющий корнем наряду с $ \varepsilon_1 $ (первообразным корнем степени $ n_{} $ из единицы) еще и $ 1_{} $. Подстановка этих двух корней в последнее тождество даст систему уравнений: $$ \tilde G(1)=E_j+E_{j+1},\quad \tilde G(\varepsilon_1)=\varepsilon_1^j(E_j+E_{j+1}\varepsilon_1) \ . $$ Домножим второе равенство на $ \varepsilon_1^{n-j} $: $$ \tilde G(1)=E_j+E_{j+1},\quad \varepsilon_1^{n-j}\tilde G(\varepsilon_1)=E_j+E_{j+1}\varepsilon_1 \ . $$ Из этих уравнений получим выражения для $ E_j $ и $ E_{j+1} $: $$ E_j=-\varepsilon_1\frac{\varepsilon_1^{n-j-1}\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1},\quad E_{j+1}=\frac{\varepsilon_1^{n-j}\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1} \ . $$ Ключевым обстоятельством является вещественность обоих чисел. Именно на этом построим критерий поиска «места ошибки», т.е. величины $ j_{} $: будем последовательно по $ k\in \{0,1,2,\dots,n-2\} $ вычислять величины $$ -\varepsilon_1\frac{\varepsilon_1^{k-1}\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1}\quad u \quad \frac{\varepsilon_1^{k}\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1} $$ до тех пор, пока оба числа не станут вещественными.

Пример. Пусть

$$ n=15, g(x)=(1-x+x^3-x^4+x^5-x^7+x^8)(x-1) \, ,$$ т.е. полином $ g(x) $ получается домножением полинома из предыдущего примера на $ x_{}-1 $.

Пусть при передаче кодового полинома $$ G(x)=2-8\,x+11\,x^2-6\,x^3+8\,x^5-17\,x^6+14\,x^7-9\,x^9+11\,x^{10}-11\,x^{11}+5\,x^{12}+3\,x^{13}-3\,x^{14} $$ произошли две ошибки подряд и на выходе из канала получен полином $ \tilde G(x)\equiv G(x)-2\,x^5+x^6 $.

Подстановка $ x_{}=1 $ в полученный полином дает $ \tilde G(1)=-1 \ne 0 $, т.е. наличие ошибки подтверждено. Далее, начинаем параллельное вычисление двух последовательностей: $$ \tilde G(\varepsilon_1),\ \tilde G(\varepsilon_1)\varepsilon_1,\ \tilde G(\varepsilon_1)\varepsilon_1^2,\dots $$ и $$ \frac{\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1},\ \frac{\varepsilon_1\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1},\ \frac{\varepsilon_1^{2}\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1}, \dots , $$ где величина $ \varepsilon_{1} $ — такая же, как и в предыдущем примере. Первая из этих последовательностей была рассмотрена в предыдущем случае — одиночной ошибки передачи. Вещественность какого-то элемента этой последовательности означает наличие ошибки в соответствующем коэффициенте полученного полинома. Таким образом, алгоритм содержит в себе еще и проверку гипотезы на одиночность ошибки. Если очередной элемент этой последовательности не является вещественным числом, произведем — с его помощью — вычисление соответствующего элемента второй последовательности. Если этот элемент — вещественное число, — а так и происходит в рассматриваемом примере на $ 10_{} $-м шаге: $$ \frac{\varepsilon_1^{10}\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1} \approx 1 \ , $$ то для контроля вычисляем еще и величину⁷⁾ $$ -\varepsilon_1\frac{\varepsilon_1^{9}\tilde G(\varepsilon_1)-\tilde G(1)}{\varepsilon_1-1} \approx -2 \ , $$ которая также оказывается вещественным числом. Место двух подряд идущих ошибок обнаружено. Их исправление производится по формуле $ \tilde G(x)+ x^{15-10}(-2+x) $. ♦

Остался нерассмотренным общий случай — когда две ошибки не обязательно соседствуют:

$$ \tilde G(x)\equiv G(x)+E_jx^j+E_{k}x^{k} \ \mbox{ при } \ j<k \, . $$ Рассмотрение этого случая ☞ ЗДЕСЬ, но для понимания последующего материала настоящего раздела вполне достаточно уже разобранных выше случаев.

Наша задача состоит в том, чтобы развитые в предыдущих пунктах идеи перевести на язык двоичных кодов — перейти к арифметике по модулю $ 2_{} $.

Циклический код образует линейное подпространство пространства $ \mathbb V^n $ и, следовательно, является частным случаем линейного кода. Но тогда можно установить соответствие между способами их определения.

С целью состыковки обозначений принятым в литературе, изменим порядок записи разрядов циклического кода. Будем считать, что строке $ (b_{n-1},b_{n-2},\dots,b_1,b_0) \in \mathbb V^n $ соответствует полином $ b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\dots+b_1x+b_0 $, т.е. младшие разряды строки соответствуют старшим коэффициентам полинома.

Пусть $$ g(x)=x^r+a_{r-1}x^{r-1}+\dots+a_0 \quad npu \quad \{a_0,\dots,a_{r-1}\} \subset \{0,1\} \ ,$$ — порождающий полином кода; мы выбираем его среди нетривиальных делителей по модулю $ 2_{} $ полинома $ x^n - 1 $. Проверочный полином $ h_{}(x) $ удовлетворяет теперь сравнению $$ g(x)h(x) \equiv 1 \pmod{2} \ . $$ Циклический код $ C_{} $, порожденный полиномом $ g_{}(x) $, имеет базисными строки, составленные из коэффициентов полиномов $ x^{k-1}g(x),x^{k-2}g(x), \dots,g(x) $. Иными словами, порождающей матрицей кода $ C_{} $ будет матрица $$ \begin{array}{rl} & \ \ \ \ x^{n-1} x^{n-2} \ \ \ x^{n-3} \ \ \dots \ \ \ \ \ \ x^k \ \ \ x^{k-1} \ \ \dots \ \ \ \ \ \ \ \ \ \ 1 \\ & \ \ \ \ \downarrow \ \ \ \ \downarrow \ \ \ \ \ \ \downarrow \ \ \ \quad \ \quad \ \quad \downarrow \ \ \ \ \downarrow \ \ \qquad \qquad \ \ \downarrow \\ \mathbf G_{k\times n}=&\left( \begin{array}{ccccccccc} 1 & a_{r-1} & a_{r-2} & \dots & a_1 & a_0 & 0 & \dots & 0 \\ & 1 & a_{r-1} & \dots & a_2 & a_1 & a_0 & & 0 \\ \mathbb O & & \ddots & & & & & \ddots & \vdots \\ & & & 1 & \dots & & & & a_0 \end{array} \right) \end{array} \ . $$ Эта матрица соответствует несистематическому способу кодирования.

Базисные строки кода, а, значит, и порождающую матрицу, можно выбрать не единственным способом; так, систематическому способу кодирования соответствует порождающая матрица $$\mathbf G=\left( \begin{array}{ccccc|lll} 1 & 0 & 0 & \dots & 0 & b_{n-1,r-1} & \dots & b_{n-1,0} \\ & 1 & 0 & \dots & 0 & b_{n-2,r-1} & \dots & b_{n-2,0} \\ \mathbb O & & \ddots & & \vdots & \vdots & & \vdots \\ & & & & 1 & b_{r,r-1} & \dots & b_{r0} \end{array} \right) \ , $$ которая уже не является циклической. Справа от черты стоят коэффициенты остатков от деления мономов $ x^{n-1},x^{n-2},\dots,x^r $ на $ g_{}(x) $: $$ x^j\equiv b_{j,r-1}x^{r-1}+b_{j,r-2}x^{r-2}+\dots+b_{j0} \equiv - (b_{j,r-1}x^{r-1}+b_{j,r-2}x^{r-2}+\dots+b_{j0}) \quad (\operatorname{modd} \ 2,g(x)) \ . $$ Посмотрим что представляют собой проверочные матрицы соответствующие двум видам порождающей матрицы. Для последней матрицы она строится просто — поскольку она имеет блочную структуру вида $ \mathbf G = \left[ E_k \mid P \right] $ при $ E_{k} $ — единичной матрице $ k_{} $-го порядка, то, в соответствии со следствием к теореме 1 из ☝ ПУНКТА, — проверочная матрица имеет вид $ \mathbf H=\left[ P^{\top} \mid E_{r} \right] $

Пример. Пусть $ n=7, g(x)=x^3+x^2+1 $. Тогда для систематического кодирования

$$ \mathbf G= \left(\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{array} \right) \quad \Rightarrow \quad \mathbf H= \left(\begin{array}{cccc|ccc} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{array} \right) \ . $$ Что представляют собой строки проверочной матрицы $ \mathbf H $? — Оказывается, они содержат коэффициенты проверочного полинома $ h_{}(x) $ кода $ C_{} $. Действительно, в данном примере $ h(x)=x^4+x^3+x^2+1 $ и $$ \begin{array}{ll} \begin{array}{c} 1 \ \ \ x \ \ \ x^2 \ \ \ x^3 \ \ \ x^4 \ \ x^5 \ x^6 \ \end{array} & \\ \begin{array}{cccccccc} \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \ \end{array} & \\ \left(\begin{array}{ccccccc} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{array} \right) & \begin{array}{l} \leftarrow h(x) \\ \leftarrow x^5+x^2+x+1\equiv h(x)x^5 \pmod{x^7-1} \\ \leftarrow x^6+x^3+x^2+x\equiv h(x)x^6 \pmod{x^7-1} \end{array} \end{array} $$ Для несистематического кодирования структура проверочной матрицы оказывается еще более простой: $$ \mathbf G= \left(\begin{array}{ccccccc} 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{array} \right) \ \Rightarrow \ $$ $$ \Rightarrow \ \mathbf H= \left( \begin{array}{ccccccc} 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 \end{array} \right) \begin{array}{l} \leftarrow h(x) \\ \leftarrow h(x)x \\ \leftarrow h(x)x^2 \end{array} \ , $$ т.е. можно сказать, что $ \mathbf H $ тоже является циклической матрицей с порождающим полиномом $ h_{}(x) $ — если записать этот полином «в обратном порядке» (т.е. формально рассмотреть полином $ h^{*}(x)\equiv x^4h(1/x) $) и циклически переставить строки. ♦

Теперь обсудим разобранные в предыдущих пунктах способы обнаружения и исправления ошибок.

Пример. Рассмотрим циклический код из предыдущего примера: $ n=7, g(x)=x^3+x^2+1 $. Пусть при передаче кодового полинома $ G(x)=x^6+x^3+x+1 $ по каналу связи произошла ровно одна ошибка и на выходе получили полином $ \tilde G(x)=x^6+x^4+x^3+x+1 $.

1-й cпособ. Вычисление синдромов $ x^j\tilde G(x) $ как остатков от деления на полином $ g_{}(x) $ — только теперь все вычисления идут по модулю $ 2_{} $: $$ {\bf \mbox{СИНДРОМ }} (\tilde G(x))\equiv x^2+x+1 \ , $$ и, поскольку синдром ненулевой, то ошибка при передаче действительно произошла. Далее, последовательно вычисляем остатки от деления полиномов $ {\bf \mbox{СИНДРОМ }}(x^j\tilde G(x)) $ при $ j\in \{1,2,\dots \} $ и при этих вычислениях можем воспользоваться теоремой 2 из ☝ ПУНКТА: $$ {\bf \mbox{СИНДРОМ }}(x\tilde G(x))\equiv x+1 \ ,\ {\bf \mbox{СИНДРОМ }}(x^2\tilde G(x))\equiv x(x+1)=x^2+1,\ $$ $$ {\bf \mbox{СИНДРОМ }}(x^3\tilde G(x))\equiv x(x^2+1) \pmod{g(x)} \equiv 1 \ . $$ Остаток оказался равным константе, следовательно ошибочный коэффициент найден, и $ G(x) \equiv \tilde G(x) + x^{7-3} \pmod{2} $.

2-й cпособ. Домножение $ \tilde G(x) $ на проверочный полином — использование теоремы 3 из ☝ ПУНКТА. Здесь $ h(x)=x^4+x^3+x^2+1 $ и $$ \tilde G(x) h(x) \equiv x^6+x^4+x+1 \equiv x^4h(x) \equiv x \quad (\operatorname{modd} \ 2,x^7-1) \ . $$ Снова ошибочный коэффициент обнаружен.

3-й cпособ. Подстановка в $ \tilde G(x) $ корня порождающего полинома. А какого, собственно, корня? Если в случае предыдущего ☝ ПУНКТА, когда мы рассматривали коды в $ \mathbb Z^n $, мы спокойно подставляли корень $ n_{} $-й степени из единицы, то для данного примера этот прием не пройдет — полином $ g_{}(x) $ не является делителем полинома $ x^7-1 $ во множестве $ \mathbb Z_{} $, а только по модулю $ 2_{} $. Комплексные корни у полинома $ g_{} (x) $, разумеется, имеются, но они не являются корнями полинома $ x^7-1 $!

Рассматриваем поле Галуа $ \mathbf{GF}(2^3) $. Поле содержит $ 8_{} $ элементов — полиномов вида $ A_2x^2+A_1x+A_0 $ с коэффициентами из $ \{0,1\} $. Полином $ g(x)=x^3+x^2+1 $ является неприводимым по модулю $ 2_{} $ полиномом и, следовательно, операция умножения полиномов из поля по двойному модулю $ 2, g(x) $ удовлетворяет всем аксиомам поля. Полиномы $ x_{},\ x^2,\ x^4 $ удовлетворяют уравнению $ g(\mathfrak x)=0 \quad (\operatorname{modd} \ 2,g(x)) $ и являются примитивными элементами поля. Последнее означает, что любой ненулевой элемент поля совпадает с какой-то степенью любого из этих полиномов, например: $$ \begin{array}{l|rrr||} x^0 & & & 1 \\ x^1 & & x & \\ x^2 & x^2 & & \\ x^3 & x^2 & &+1 \\ x^4 & x^2 &+x &+1 \\ x^5 & & x &+1 \\ x^6 & x^2 &+x & \end{array} \qquad \begin{array}{|l|rrr} (x^2)^0 & & & 1 \\ (x^2)^1 & x^2 & & \\ (x^2)^2 & x^2 & +x &+1 \\ (x^2)^3 & x^2 &+x & \\ (x^2)^4 & &x & \\ (x^2)^5 & x^2 & &+1 \\ (x^2)^6 & &x &+1 \end{array} $$ Эти полиномы и будут аналогами первообразных корней из ☝ ПУНКТА. Подставим любой из них в полином $ \tilde G(\mathfrak x) $ и проведем вычисления по двойному модулю. Например, $$ \tilde G(x) = x^6+x^4+x^3+x+1 \equiv x^2+x+1 \quad (\operatorname{modd} \ 2,g(x)) $$ В приведенной выше таблице полином $ x^2+x+1 $ соответствует элементу $ x^4 \quad (\operatorname{modd} \ 2,g(x)) $. Это и есть моном полинома, в котором допущена ошибка.

Проверим, на всякий случай, наше заключение: не изменится ли оно если возьмем в качестве примитивного элемента полином $ x^{2} $? $$ \tilde G(x^2) = x^{12}+x^8+x^6+x^2+1 \equiv x \equiv (x^2)^4 \quad (\operatorname{modd} \ 2,g(x)) \ , $$ т.е. снова имеем $ 4 $-ю степень примитивного элемента поля. ♦

Итак, для целей корректировки ошибок порождающий циклический код полином $ g_{}(x) $ имеет смысл выбрать среди примитивных — тогда любой его корень можно использовать для исправления одной ошибки.

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

Надо оправдать последний вывод. Циклический код является линейным кодом, у него имеется проверочная матрица $ \mathbf H $. В предыдущем примере эта матрица как раз строилась для случая, когда степень полинома $ g_{}(x) $ равнялась $ 7=2^3-1 $. Столбцами этой $ 3\times 7 $-матрицы были все трехбитные ненулевые столбцы — но тогда, с точностью до их перестановки, эта матрица совпадает с проверочной матрицей (7,4)-кода Хэмминга.

Покажем теперь справедливость этого утверждения для общего случая $ n=2^M-1 $. Выбираем в качестве порождающего код полинома произвольный примитивный полином $ g_{}(x) $ степени $ M_{} $. Если $ \mathfrak A \in \mathbf{GF}(2^M) $ — его корень, то этот корень будет примитивным элементом поля $ \mathbf{GF}(2^M) $, построенного на основе операции умножения по двойному модулю $ 2,g(x) $. Примитивность корня означает, что все его степени $$ \mathfrak A^{n-1},\ \mathfrak A^{n-2},\dots ,\mathfrak A, \mathfrak A^0=1 $$ будут различными элементами этого поля. Любой кодовый полином $ G(x)=b_0x^{n-1}+b_1x^{n-2}+\dots+b_{n-1} \in C $ делится на $ g_{}(x) $, и, следовательно (см. начало ☞ ПУНКТА ): $$ G(\mathfrak A)= b_0\mathfrak A^{n-1}+b_1\mathfrak A^{n-2}+\dots+b_{n-1} =\mathfrak o \ .$$ Любую степень $ \mathfrak A^k $ элемента поля можно линейно выразить через первые $ M-1 $ степеней посредством соотношения $ g(\mathfrak A)= \mathfrak o $. Так, для приведенного выше примера: $$ \begin{array}{c} n=7, g(x)=x^3+x^2+1 \\ \hline \\ \begin{array}{l|rrr|r} \mathfrak A^0 & & & 1 & 001\\ \mathfrak A^1 & & \mathfrak A & & 010 \\ \mathfrak A^2 & \mathfrak A^2 & & & 100 \\ \mathfrak A^3 & \mathfrak A^2 & &+1 & 101 \\ \mathfrak A^4 & \mathfrak A^2 &+\mathfrak A &+1 & 111 \\ \mathfrak A^5 & & \mathfrak A &+1 & 011 \\ \mathfrak A^6 & \mathfrak A^2 &+\mathfrak A & & 110 \end{array} \end{array} $$ и $$ \begin{array}{rrrrl} G(\mathfrak A)= b_0 (& \mathfrak A^2 & +\mathfrak A & )+ \\ + b_1 (& & \mathfrak A &+1 ) + \\ + b_2 (& \mathfrak A^2 &+\mathfrak A &+1 ) + \\ + b_3 (& \mathfrak A^2 & &+1 ) + \\ +b_4 (& \mathfrak A^2 & & ) + \\ +b_5 (& &\mathfrak A & ) + \\ +b_6 (& & & +1 )= \\ = \mathfrak o \ . \end{array} $$ Это равенство можно рассматривать как полиномиальное тождество относительно величины $ \mathfrak A $. Приравниваем нулю коэффициенты при $ \mathfrak A^2, \mathfrak A, 1 $ и получаем систему линейных уравнений, которой должны удовлетворять величины $ \{b_j\}_{j=0}^6 $: $$ b_0 \left(\begin{array}{c} 1 \\ 1 \\ 0 \end{array}\right) + b_1 \left(\begin{array}{c} 0 \\ 1 \\ 1 \end{array}\right)+ b_2 \left(\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right)+ b_3 \left(\begin{array}{c} 1 \\ 0 \\ 1 \end{array}\right)+ b_4 \left(\begin{array}{c} 1 \\ 0 \\ 0 \end{array}\right)+b_5 \left(\begin{array}{c} 0 \\ 1 \\ 0 \end{array}\right)+ b_6 \left(\begin{array}{c} 0 \\ 0 \\ 1 \end{array}\right)= \left(\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\right) \ . $$ Все столбцы в левой части равенства различны, поскольку они соответствуют различным элементам поля $ \mathbf{GF}(8) $. Именно в этом моменте существенно проявляется свойство примитивности элемента поля $ \mathfrak A $: множество $ \{\mathfrak A^j\}_{j=0}^6 $ совпадает со множеством $$ \{a_2 \mathfrak A^2+a_1 \mathfrak A+a_0 \ \mid \ \{a_0,a_1,a_2\} \subset \{0,1\}, (a_0,a_1,a_2) \ne (0,0,0) \} $$ различных ненулевых полиномов над $ \mathbf{GF}(2) $ степеней $ \le 2 $. Аналогичное утверждение справедливо и в общем случае поля $ \mathbf{GF}(2^m) $. Переписав эти соотношения в матричной форме, мы получим равенство вида $$ \mathbf H \cdot \left(\begin{array}{l} b_0\\ b_1\\ \vdots \\ b_{n-1}\end{array}\right) = \mathbb O \ $$ и столбцы матрицы $ \mathbf H_{M\times (2^M-1)} $ — это все ненулевые $ M_{} $-разрядные двоичные столбцы. Но тогда матрица $ \mathbf H $ — с точностью до перестановки — является проверочной матрицей кода Хэмминга.

.

[1]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.