Не могу осознать циклические коды

[Kevsh]

Вот определение циклического кода, оно мне понятно:

Циклическим кодом называют идеал в кольце многочленов $R$, образованный неприводимым порождающим многочленом $g(x)$ степени $n-k$ ($n-1$ - максимальная степень многочлена в кольце $R$; Идеал - подмножество многочленов, которое делится на $g(x)$ без остатка).

Вот абзац из книги, который мне уже не очень понятен:


Со слов про образующую матрицу уже вопросы, такое утверждение не очень очевидно. Но ладно, принимаем на веру. А вот к равенству для $G_i(x)$ у меня уже большие вопросы. По такой логике любой циклический сдвиг порождающего многочлена должен делиться на порождающий многочлен (ну или такой сдвиг уже не будет входить в идеал). Возьмём всё тот же порождающий многочлен $g(x)=x^3+x+1$ в контексте кода (7,4) и умножим его на $x^4$. Получили $x^7+x^5+x^4$. Вот теперь мы должны найти остаток от деления на $x^7+1$, он равен $x^5+x^4+1$. А такой многочлен уже не делится на $g(x)$ без остатка, то есть не входит в идеал. Можно просто умножать $g(x)$ на $x$, пока старшая степень не станет равна $n-1$, но тогда мы получим не все элементы идеала. Я как-то не совсем правильно понял то, что написано в книге?

Также я не очень понял, как они так ловко сразу сделали образующую матрицу для этого кода. По моим представлениям нужно было выписать все возможные многочлены (в примере выше их 128), найти те из них, которые входят в идеал (их должно быть 16) и записать их в матрицу (то есть по идее у нас 16 разрешённых комбинаций). Далее необходимо линейными преобразованиями привести матрицу к тому виду, что мы видим на картинке. Или можно как-то сильно проще?

[mihaild]

Kevsh в сообщении #1690068 писал(а):

$x^5+x^4+1$. А такой многочлен уже не делится на $g(x)$ без остатка

Почему не делится? $g(x) \cdot (x^2 + x + 1) = x^5 + x^4 + 1$

[Kevsh]

mihaild
Это я тупанул...
Но, конечно, всё равно не очень очевидно, почему это так

[mihaild]

Kevsh в сообщении #1690177 писал(а):

Но, конечно, всё равно не очень очевидно, почему это так

Странно, что этого там не написано. Ключевой момент - что $x^7 + 1$ делится на $g(x)$. Докажите, что $(m(x) \cdot g(x) \pmod{k(x) \cdot g(x)}) \equiv 0 \pmod{g(x)}$ Из этого и предыдущего всё следует.