Вопрос по разновидностям сверток многочленов

[Paul Kellerman]

Пусть над простым полем Галуа GF(p) заданы два многочлена a(x) и b(x),
и определены операции сложения многолченов, умножения многочленов,
и вычисления остатка одного многочлена по модулю другого многочлена.

Тогда, насколько я помню в общем виде свертка многочленов выглядит:

c(x) = (a(x)*b(x)) mod g(x)

Если deg(g(x)) > deg(a(x)) + deg(b(x)), то имеем линейную свертку, кото-
рая по сути совпадает с произведением многочленов a(x) и b(x), если же
deg(g(x)) <= deg(a(x)) + deg(b(x)), то в случае если g(x) неприводим над
полем GF(p) то имеем полевую свертку, а если g(x) = x^r - 1, то свертка
называется циклической. Однако я нигде не нашел комментариев по по-
воду остальных случаев, когда g(x) не является неприводимым, но в то
же время он не выглядит как x^r - 1. Например, как называется свертка
вида (a(x)*b(x)) mod (x^r), которая легко получается путем вычисления
произведения многочленов a(x) и b(x) с последующим "отбрасыванием"
слагаемых со степенями выше r ? Усеченной сверткой или как-то еще?

[Paul Kellerman]

Итерационно-сдвиговая схема вычисления общего случая свертки многочленов
a(x) и b(x) степени <= m - 1 по модулю нормированного многочлена степени m:
g(x) = x^m + g[m-1]*x^(m - 1) + ... + g[0], заданных над простым полем GF(p).

При g(x) = x^m - 1, имеем циклическую свертку.
При g(x) = x^m, имеем усеченную линейную свертку.
При g(x) неприводимом над GF(p), имеем полевую свертку.

Буду рад комментариям, дополнениям, замечаниям.

[Paul Kellerman]

Аппаратная реализация (электрическая модель в Multisim 10) итерационно-сдвиговой
схемы вычисления свертки для четырехразрядного (m = 4) двоичного случая (p = 2).
Сдвиговый регистр на базе D-триггеров расположен в верхней части схемы. В нижней
части расположены индикаторы (UL1, UL2, UL3) для отображения a(x), b(x) и свертки
c(x)=a(x)*b(x) mod g(x) в эквиваленте четырехразрядного шестнадцатеричного числа,
DIP-переключатели J2, J3, J4 для задания коэффициентов многочленов a(x), b(x), g(x),
а также схема для формирования 4-х тактовых импульсов по линии CLK и последовате-
льной подачи коэффициентов b[4 - s] многочлена b[x] по линии BMS, s - номер такта.

При g = (0001), g(x) = x^4 + 1, имеем циклическую свертку.
При g = (0000), g(x) = x^4, имеем усеченную линейную свертку.
При g = (0011), g(x) = x^4 + x + 1 неприводим над GF(2), имеем полевую свертку.

Буду рад комментариям, дополнениям, замечаниям.