Циклический код Хэмминга в расширении конечного поля

[Without Name]

Хочу разобраться в том, как строятся коды Хэмминга в расширении конечного поля. Вектор $c$ над $GF(q)$ является кодовым словом тогда и только тогда, когда $cH^T = 0$. Например, выберем следующую проверочную матрицу $(7,4)$-кода Хэмминга:

$\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}$

Переходя в расширение поля, эту матрицу можно записать более компактно. Столбцы матрицы $H$ можно отождествить с элементами поля $GF(8)$. ТОгда, используя для построения поля $GF(8)$ многочлен $p(z)=z^3 + z + 1$ и выбирая $z$ в качестве представителя примитивного элемента $\alpha$, перепишем матрицу в виде

$H = [ \alpha^0 \alpha^1 \alpha^2 \alpha^3 \alpha^4 \alpha^5 \alpha^6]$

Формула $cH^T = 0$ превращается в произведение векторов.

Я хочу пойти в обратном порядке: по многочлену построить проверочную и кодирующую матрицы. Для построения поля выберу тот же самый многочлен, получится та же самая матрица. А теперь я хочу закодировать и раскодировать сообщение. Так как этот код - циклический, процедуру кодирования можно записать так: $c(x) = a(x)g(x)$, где $g(x)=x^3 + x + 1$. Возьмем сообщение $i(x)=(1010) = x^3 + x$. Тогда $i(x)g(x) = x^6 + x^3 +x^2 + x = 1001110$. Далее используем проверочную матрицу, чтобы убедиться в том, что получилось кодовое слово. Используем матрицу, составленную из элементов расширения поля:

$(0111001)\begin{bmatrix} \alpha^0 \\ \alpha^1 \\ \alpha^2 \\ \alpha^3 \\ \alpha^4 \\ \alpha^5 \\ \alpha^6 \end{bmatrix} = \alpha^1 + \alpha^2 + \alpha^3 + \alpha^6 = \alpha^3$

Ошибка, должен был получиться ноль. Если записать биты бинарного представление многочленов в матрице в обратном порядке (от старшего к младшему), то получается то же самое, не ноль.

Где я ошибся:

-- 04.04.2023, 09:37 --

Мои расчеты

[Without Name]

>Где я ошибся:

Где я ошибся?

[svv]

Если проверочная матрица имеет вид $\mathbf H=(\mathbf P^\top | \mathbf I_{n-k})$ (формула 1.16), то порождающая (кодирующая) имеет вид $\mathbf G=(\mathbf I_k | \mathbf P)$ (формула 1.14). Если сообщение передано без ошибок, то синдром будет нулевым. Это свойство обеспечивается тем, что при таком виде матриц
$\mathbf G\mathbf H^\top=\mathbf I_k\mathbf P + \mathbf P\mathbf I_{n-k} = \mathbf P+\mathbf P=\mathbf 0,$
где нулевая матрица имеет размер $k\times(n-k)$.

Проверочная матрица из примера 14 имеет указанный вид, соответственно, порождающая для примера 14 равна
$\mathbf G=\begin{bmatrix}1000110\\0100101\\0010011\\0001111\end{bmatrix}$

Но Ваша проверочная матрица получается из той, что в примере 14, некоторой перестановкой столбцов. Для сохранения свойства $\mathbf G\mathbf H^\top=\mathbf 0$ нужно применить к порождающей ту же самую перестановку столбцов. Мы получим:
$\mathbf G=\begin{bmatrix}1101000\\1010001\\0110100\\1110010\end{bmatrix}$
И, действительно,
$\mathbf G\mathbf H^\top= \begin{bmatrix}1101000\\1010001\\0110100\\1110010\end{bmatrix} \begin{bmatrix}100\\010\\001\\110\\011\\111\\101\end{bmatrix} = \begin{bmatrix}000\\000\\000\\000\end{bmatrix}$

А какую Вы брали порождающую матрицу? Как сопоставляли ей вектор элементов $\mathrm{GF}(8)$?

[Without Name]

Я строил порождающую матрицу при помощи матрицы $P^T=\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}$

Получилось $G = \begin{bmatrix} 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{bmatrix}$

А как определить по проверочной матрице, каким должен быть порядок столбцов в порождающей матрице?

[svv]

Единственный способ, который я знаю (и который применил выше) — это начать со стандартной формы $\mathbf G=(\mathbf I_k | \mathbf P), \mathbf H=(\mathbf P^\top | \mathbf I_{n-k})$ с одной и той же матрицей $\mathbf P$, а потом переставить столбцы $\mathbf H$ так, как Вы хотите, а к $\mathbf G$ применить ту же перестановку столбцов.
Смысл такой процедуры — чтобы соотношение $\mathbf G\mathbf H^\top=\mathbf 0$ сохранилось и после перестановки — а именно оно обеспечивает нулевой синдром, когда нет ошибок.

[Without Name]

Нет-нет, с матрицами все в порядке. Если кодировать матрицами, то проверка проходит успешно. Вот смотрите:



Проблема в том, что кодирование при помощи многочлена, с помощью которого построен код, отличается от кодирования при помощи матриц. Многочлен $g(x) = x^3 + x + 1$. Мои расчеты видны на листочке. Возьмем информационную последовательность $i = 1010, i(x) = x^3 + x$, тогда кодирование при помощи многочлена $i(x)g(x) = x^6 + x^3 + x^2 + x = 1001110$. Сразу видно, что получился несистематический код.

Теперь закодируем при помощи матрицы $G: (1010)*G = 1010001 $



Получился систематический код.

Это уже другая книга, автор Р. Блейхут, я параллельно читаю несколько книг :) До этого был Морелос-Сарагоса.

-- 05.04.2023, 16:49 --

Вот теория

[svv]

Блейхут у меня есть, я по нему изучал коды Рида-Соломона (где тоже используются конечные поля, причём там без них уже никак не обойтись). А с кодом Хэмминга я вообще не знаком — разбирался только по тем страничкам, что Вы дали. В общем, посмотрю Блейхута.

[svv]

Пусть $c(x)=i(x)g(x)=x^6+x^3+x^2+x^1$.
В нижней части листочка Вы находите $c(\alpha)$ двумя способами. Правильный — нижний способ, который является простой подстановкой $x=\alpha$ в $c(x)$ с последующим упрощением. Только Вы там ошиблись и в одном из переходов $\alpha^1$ заменили на $1=\alpha^0$.

Если в векторе $\mathbf H$ степени $\alpha$ располагаются от младшей к старшей, то и в векторе $\mathbf c$ коэффициенты тоже должны располагаться от $c_0$ до $c_{n-1}$:
$\mathbf c=[c_0 c_1 c_2 c_3 c_4 c_5 c_6]=[0111001]$

$\mathbf c\mathbf H^\top=[0111001][\alpha^0 \alpha^1 \alpha^2 \alpha^3 \alpha^4 \alpha^5 \alpha^6]^\top=$
$=\alpha^1+\alpha^2+\alpha^3+\alpha^6=$
$=\alpha^1+\alpha^2+(\alpha^0+\alpha^1)+(\alpha^0+\alpha^2)=0$

[Without Name]

Понятно, спасибо!