Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

4.2. Умножение и деление многочленов

В этом разделе описываются схемы, используемые для умножения или деления любого многочлена на некоторый фиксированный многочлен. Схема, изображенная на рисунке 2, используется для умножения любого многочлена на входе:

на фиксированный многочлен

.

Предполагается, что первоначально устройство памяти содержит нули, а на вход поступают коэффициенты многочлена а(Х), начиная с коэффициентов высших порядков, после чего следуют r нулей.

Произведение равно

Когда на вход схемы подается первый коэффициент ak многочлена а(x), то на выходе появляется первый коэффициент произведения a(x)h(x), равный akhr. В этот момент все ячейки устройства памяти содержат нули. Спустя единицу времени, на входе появляется ak-1, ak находится в первой ячейке, а все остальные ячейки содержат нули. Как можно увидеть на рисунке 2, выход схемы будет равен т. е. выход равен величине второго коэффициента в произведении a(x)h(x). Аналогично через две единицы времени на входе появится аk-2, а ячейки регистра сдвига будут содержать элементы ak-1, ak, 0, ..., 0, 0, 0. Выход схемы равен , т. е. величине третьего коэффициента произведения а(x)h(x). Дальнейшие операции производятся аналогичным образом. После r + k - 1 сдвигов в ячейках регистра содержатся элементы 0, 0, 0, ..., 0, а0, а1 и выход схемы равен, т. е. предпоследнему коэффициенту произведения a(x)h(x). После r + k сдвигов регистр сдвига содержит элементы 0, 0, 0, ..., 0, а0 и выход равен a0h0 - последнему коэффициенту произведения a(x)h(x), так что произведение получено полностью.

  

Рисунок 2. Схема для умножения многочленов.

Другая схема для умножения многочленов показана на рисунке 3.


Рисунок 3. Другая схема для умножения многочленов.

Пример: С помощью схем, изображенных на рисунках 4а и 4б, производится умножение входного многочлена на многочлен h(x) = x6 + +х5 + x4 + x3 + 1 над полем из двух элементов. Имеет смысл записать содержимое устройства памяти для каждого шага процесса вычисления и сравнить запись с промежуточными результатами обычного вычисления произведения.

Рисунок 4. Схема для умножения на многочлен  x6 + х5 + x4 + x3 + 1.

Деление многочлена  на многочлен  осуществляется с помощью линейных переключательных схем с обратной связью. Устройство памяти вначале должно содержать нули. Выходной символ принимает значения, равные 0, для первых r сдвигов, т. е. до тех пор, пока первый входной символ не достигнет конца регистра сдвига. После этого появляется первый ненулевой выходной символ, который равен  - первому коэффициенту частного. Для каждого коэффициента частного  необходимо вычесть из делимого многочлен . Это вычитание производится с помощью обратной связи. После всех п сдвигов на выходе появится частное от деления, а остаток от деления будет находиться в регистре сдвига. Работу схемы легче всего понять с помощью подробных примеров.

Рисунок 5. Схема для деления на многочлен x6 + х5 + x4 + x3 + 1.

Пример: Схема, изображенная на рисунке 5, предназначена для деления многочлена на входе на многочлен g (x) = x6 + х5 + x4 + x3 + 1 над полем из двух элементов. Таблица 1 содержит результаты всех промежуточных операций.


Содержимое регистра

сдвига после j сдвигов

Выходной символ после j -го сдвига

Обратная связь в момент j -го сдвига

Входной символ в момент j -го сдвига

0

000000

0

-

-

1

100000

0

000000

1

2

010000

0

000000

0

3

101000

0

000000

1

4

110100

0

000000

1

5

011010

0

000000

0

6

001101

1

000000

0

7

000001

1

100111

1

8

100111

1

100111

0

9

110100

0

100111

0

10

111010

0

000000

1

11

111101

1

000000

1

12

111001

1

100111

0

13

011011

1

100111

1

14

001010

0

100111

1

             
Таблица 1. Последовательные операции в схеме для деления.