Схема для умножения на многочлен. В исходном состоянии ячейки памяти регистра содержат нули

h(x) = h₀ + h₁x + … + h_r-1x^r-1 + h_rx^r

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

Когда по первому тактовому импульсу на входе появляется первый коэффициент многочлена а(х), то на выходе появляется первый коэффициент произведения , равный и записывается в первый разряд регистра. В этот момент все остальные разряды регистра сдвига содержат нули. Спустя единицу времени по второму тактовому импульсу на входе появляется . Как видно из рис. 6.2 выход по второму тактовому импульсу равен , т.е. величине второго коэффициента в произведении . К моменту появления третьего коэффициента на входе () разряды регистра содержат элементы Выход по третьему такту равен т.е. третьему коэффициенту произведения . Дальнейшие операции производятся аналогичным образом.

По (r+k)-му такту регистр сдвига содержит элементы 0, 0, …, 0, а₀, а выход равен , т.е. предпоследнему коэффициенту произведения . После (r+k +1)-го такта в регистре остаются одни нули, а на выходе появляется - последний коэффициент произведения , так что произведение получено полностью.

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

Рис 6.3

Дата добавления: 2015-08-02