Перемножение и деление полиномов

Рассмотрим умножение полиномов, например, информационного полинома

и образующего полинома

.

Произведение этих полиномов равно:

Пусть, например, , , тогда , а . Произведение полиномов:

Операция умножения полиномов может быть выполнена схемами, приведенными в общем виде на рис. 20.1 (а, б). Обратные связи определяются видом образующего полинома .

Первоначально ячейки памяти схемы, приведенной на рис. 2.3а находятся в нулевом состоянии. На первом такте на вход схемы поступает первый коэффициент полинома и на выходе появляется первый коэффициент произведения, равный . На следующем такте на выход поступит сумма и т.д. На -ом такте все ячейки, кроме последней, будут в нулевом состоянии и на выходе получим последний коэффициент . В каждом такте необходимо учитывать сигналы на входах и выходах схем сложения по mod 2.

Аналогично работает схема умножения полиномов, приведенная на рис.20.1б.

Пример.

В качестве примера рассмотрим перемножение полиномов , которому соответствует код 1101 и , которому соответствует код 1101.

или 1010001.

Для умножения используется схема, приведенная на рис. 20.2

Рис.20.2. Схема умножения полиномов и .

Для упрощения на схеме не показаны тактовые сигналы.

Процесс перемножения поясняется таблицей 1 состояния ячеек.

В исходном состоянии все ячейки схемы находятся в нулевом состоянии. В течение текущего такта из ячеек выталкивается записанный в предыдущем такте сигнал и записывается сигнал текущего такта. Коэффициенты полинома 1101, начиная со старшего, подаются на вход схемы.

В первом такте единица старшего разряда записывается в ячейку 1 и проходит на выход схемы, т. к. из ячеек 2 и 3 выталкиваются нули.

Состояния ячеек схемы при перемножении полиномов и

Таблица 1

Во втором такте 1 выталкивается из первой ячейки и записывается во вторую, а из второй и третей ячеек выталкиваются нули. Входной нулевой сигнал проходит через элементы сложения по mod2 на выход схемы и записывается в первую ячейку.

В третьем такте из ячеек 2 и 3 выталкиваются, соответственно 1 и 0, а входная 1 складывается по mod2 c 1 из второй ячейки, поэтому на выходе схемы будет 0. В третью ячейку записывается 1 из второй ячейки.

В четвертом такте из первой, второй и третьей ячеек выталкиваются, соответственно, 1, 0 и 1 и поскольку на вход поступает 1, то на выходе формируется 0. Входная 1 записывается в первую ячейку, 1 из первой ячейки записывается во вторую ячейку.

В последующие три такта на вход схемы ничего не поступает и информация из ячеек поступает на выход схемы.

В результате на седьмом такте на выходе схемы формируется кодовая комбинация 1010001.

Рассмотрим деление полиномов. В качестве делимого возьмем полином , в качестве делителя выберем полином . Обратные связи регистра соответствуют виду многочлена . Рассмотрим деление полиномов на примере.

Пусть , a .

Частное от деления равно (00011000), а остаток от деления (101).

Деление полиномов осуществляется схемой, приведенной на рис. 20.3.

Рис. 20.3. Схема деления полиномов на

Процесс деления поясняется таблицей 2 состояния ячеек схемы.

Состояния ячеек схемы при делении полиномов на

Таблица 2

Остаток деления - это состояния ячеек схемы на -ом такте (8-ом такте).