Предполагается,что первоначально устройство памяти содержит нули, а на вход поступают коэффициенты полинома a(X) начиная с коэффициента высших порядков,после чего следует r нулей.
Произведение равно
a(X)h(X) = ak hr X^k+r + (ak-1 hr + ak hr-1)X^k+r-1 +
+ (ak-2 hr + ak-1 hr-1 + ak hr-2)X^k+r-2 + ...+
+ (a0 h2 + a1 h1 + a2 h0)X^2 + (a0 h1 + a1 h0)X + a0 h0
Когда на вход подаётся первый коэффициент ak полинома a(X),то на выходе появляетя первый коэффициент произведения a(X)h(X),равный
ak hr.В этот момент все ячейки устройства памяти содержат нули.Спустя единицу времени на входе появляется ak-1,ak находится в первой ячейке,а все остальные ячейки содержат нули.Как можно увидеть из рисунка ПП1 выход будет равен ak-1 hr + ak hr-1,т.е.величине второго коэффициента в произведении a(X)h(X).Аналогично через две единицы времени на входе появится ak-2,а ячейки регистра сдвига будут содержать элементы ak-1,ak,0,...,0,0,0.Выход равен ak-2 hr +
+ ak-1 hr-1 + ak hr-2,т.е.величине третьего коэффициента произведения a(X)h(X).Дальнейшие операции производятся аналогичным образом.
После r+k-1 сдвигов в ячейках регистра содержатся элементы 0,0,0,
,...,0,a0,a1 и выход равен a0 h1 + a1 h0,т.е.предпоследнему коэффициенту произведения a(X)h(X).После r+k сдвигов регистр сдвига содержит элементы 0,0,0,...,0,0,a0 и выход равен a0 h0 - последнему коэффициенту произведения a(X)h(X),так что произведение получено полностью.
Выход │
┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐
┌─│ │─│+│─│ │─│+│─│ │─ ...─│+│─│ │─│+│─│ │─│+│─│ │─│+│
│ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘
│ │ │ │ │ │ │
┌──┐ ┌───┐ ┌───┐ ┌────┐ ┌────┐ ┌────┐ ┌───┐
│h0│ │h1 │ │h2 │ │hr-3│ │hr-2│ │hr-1│ │hr │
└──┘ └───┘ └───┘ └────┘ └────┘ └────┘ └───┘
───┴───────┴────────┴─────────────┴────────┴────────┴─────────┘
Вход
Рис.ПП 2.
ДРУГАЯ СХЕМА произведения показана на рис.ПП.Коэффициенты произведения формируются в регистре сдвига.После подачи на вход первого символа выход равен ak hr,а ячейки памяти содержат только нули.После одного сдвига ячейки содержат элементы ak h0,ak h1,...,ak hr-1 и вход равен ak-1.Поэтому выход равен ak hr-1 + ak-1 hr,т.е.второму коэффициенту.После следующего сдвига ячейки памяти содержат элементы ak-1 h0,ak h0 + ak-1 h1,ak h1 + ak-1 h2,...,ak hr-2 + ak-1 hr-1
и вход равен ak-2.Следовательно,выход равен ak hr-2 + ak-1 hr-1 +
+ ak-2 hr,т.е.третьему коэффициенту произведения.Дальнейшие операции производятся аналогичным образом.
Схема такого вида,как показано на рис.ПП2,могут иметь более чем один вход.Например,схема ,изображённая на рис.ПП а1а2,имеет два входа a1(X) и a2(X),а выход равен
b(X) = a1(X)h(X) + a2(X)k(X), где h(X) = hrX^r + hr-1X^r-1 +...+h0,
k(X) = krX^r + kr-1X^r-1 +...+k0.
Вход a1(X)
───┬───────┬────────┬──────────────┬────────┬────────┐
┌──┐ ┌───┐ ┌───┐ ┌────┐ ┌────┐ ┌───┐
│h0│ │h1 │ │h2 │ │hr-2│ │hr-1│ │hr │
└──┘ └───┘ └───┘ └────┘ └────┘ └───┘
│ │ │ │ │ │
┌─┐ ┌─┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐ ┌─┐
│+│─│ │─│+│─│ │─│+│─│ │─... ─│+│─│ │─│+│─ │ │─│+│──────>
└─┘ └─┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ Выход
│ │ │ │ │ │
┌──┐ ┌───┐ ┌───┐ ┌────┐ ┌────┐ ┌───┐
│h0│ │h1 │ │h2 │ │hr-3│ │hr-2│ │hr │
└──┘ └───┘ └───┘ └────┘ └────┘ └───┘
───┴───────┴────────┴─────────────┴────────┴─────────┘
Вход a2(X)
Рис.ПП a1 a2.
Схема изображена для случая,когда полиномы h(X) и k(X) имеют одну и ту же степень.Однако,если степени многочленов не совпадают,то в качестве r можно выбрать наибольшую степень и положить коэффициенты высших порядков одного из многочленов равными 0.
Заметим,что во всех этих схемах коэффициент при X^r+i поступает на вход в момент времени,когда коэффициент при X^i появляется на выходе.Коэффициент при X^r в произведении появляется на выходе через r
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.