Устройство для вычисления полиномов Советский патент 1981 года по МПК G06F17/11 

(54) УСТЮЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМОВ

1

Изобретение относится к вычислительной технике и предназначено для вычисления алгебраических полиномов с высокой скоростью.

Известны устройства, ссщержащие регистры, сумматоры и счетчики 1,

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

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

Недостатком такого устройства является низкое его быстродействие

Целью предполагаемого изобретения является повышение быстродействия.

Поставленная цель достигается тем, что в устройство для вычисления полиномов, содержащее первый регистр, выход которого подключен к входу множителя первого умножителя, вход множимого которого соединен с выходом второго регистра, первый вход которого подключен к первому выходу третьего регистра, вход которого соединен с выходом первого сумматора, первый вход которого подключен к выходу первого умножителя, счетчик циклов, первый вход которого соединен с первым входом устройства, а выход - соединен с первым Еыходом устройства, введены три умножителя, три сумматора, регистры, блок задания количества циклов, четыре блока памяти, блок управления записью, формирователь начального адреса, причем выходы блока управления записью соединены соответственно с первыми входами блоков памяти, вторые входы KOTOfXJX подключены к второму входу устройства, и к входу четвёртого регистра, выход первого блока 0 памяти соединен со вторыми входами

второго регистра и первого сумматора, выход вторюго блокапамяти соединен с первыми входами пятого регистра и второго сумматора, первый выход которого соединен через шестой регистр со вторым входом пятого {1егистра, выход первого регистра соединен с первыми входами второго, третьего и четвертого умножителей, выходы которых соединены соответственно со вторым входом вторюго сумматора и первыми входами третьего и четвертого сумматоров, первые выходы которых подключены соответственно к входам седьмого и восьмого регистров, выход .третьего блока памяти соединен с первыми входами девятого регистра и вторым входом третьего сумматора, второй выход которого соединен со вторым входом четвертого сумматора, выход седьмого регистра соединен со вторым входом девятого регистра, первы и вторюй выходы восьмого оегистра подключены соответственно к второму выходу устройства и к первому входу десятого регистра, выход четвертого блока памяти соединен со вторым входом десятого регистра и с третьи входом четвертого сумматора, первый выход второго, умножителя соединен с вторым входом второго сумматора, второй выход которого подключен к. третьему входу третьего сумматора, второй выход третьего регистра соединен с третим входом второго сумматора, первый выход четвертого регистра и выход пятого регистра соединены соответственно со вторым и третьим входами второго умножителя, второй выход которого подключен ко входу первого регистра, второй выход четвертого регистра - к второму и третьему входу четвертого умножителя и ко второму входу третьего умножителя, выход четвертого умножителя соединен с третьим входо третьего умножителя, четвертым и пятым входами второго умножителя и со входом одиннадцатого регистра, выход которого соединен с четвертым входом третьего умножителя, пятый вход которого подключен к выходу девятого регистра, второй выход третьего умножителя соединен через двенадцатый регистр с четвертым входом четвертогЬ умножителя, пятый вхос которого соединен с выходом девятого регистра, третий вход устройства соединен через тринадцатый регистр с входами формирователя начального адреса и блока задания количества циклов, выходы которых соеи ннены соответственно со входом блока управления записью и вторым входом счетчика циклов.

На фиг.1 представлена блок-схема устройства для вычисления плиномов; на фиг. 2 - размещение коэффициентов

полинома степени на фиг.З размещение коэффициентов в ячейках блоков.

Устройство для вычисления полимонов содержит регистры 1 и 2, ум5 ножитель 3,сумматор 4, регистры 5 умножитель 8, сумматор 9 , регистры, 10-12, умножитель 13, сумматор 14, регистр 15-17, умножитель 18, сумматор 19, регистр 20, блоки 21-24 пап мяти, блок 25 управления записью, формирователь 26 начгшьгого адреса, регистр 27, блок 28 задания количества циклов, счетчик 29 циклов, входы 30-32 устройства, выходы 33-34 устройства,

5В устройстве полиномы вида

,.., . .. +а где Y - значение вычисляемого

полинома; а„,а„., .. . - коэффициенты поли-,

нома;

X - независимая переменная;

- степень полинома, целое положительное число, разбиваются на четыре ветви,в которых вычисляются значения Y , Y ,3 , Y сумма которых равна Y.

Причем значения У,У4,Уз,У4 вычисляются одновременно. в устQ ройстве могут вычисляться полиномы любой степени Л415. При и 4 15 коэффициеиты при отсутствукяиих стРарших степенях х( ,ац ,,..ац+-() полагаются равнь1ми нулю. Коэффициенты а, ,... а,ао поступают из памяти на вход 30 устройства и размещаются в блоках 21 - 24,

В случае, когда отсутствующие коэффициенты заменяются в ячейках блоков памяти нулями. При этом, если отсутствуют все коэффициенты, занимающие первые ячейкиблоков памяти, то все оставшиеся коэффициенты сметцаются в своих блоках на одну ячейку вверх до тех пор, пока хотя 5 бы в одном из блоков первая ячейка: будет содержать ненулевой код коэффициента, Иэменение положения коэффициентов в ячейках блоков памяти совмещается с их загрузкой с помощью ч блоков 26 и 25.

Определение количества циклов работы устройства, необходимых для вычисления полинома заданной степени, осуществляется блоком 28. Колиг чество циклов 1 определяется в зависимости от степени заданного полинома п следующим образом при при при

) Счетчик 29 циклов служит для определения момента окончания вычисления полинома.

Работа устройства (на примере вычисления полинома степени ) 5 заключается в следующем. Вычисление полинома начинается с того, что в регистр 27 по входу 31 устройства поступает порядок заданного полинома. Блок 28 определяет необходимое количество циклов вычисления , которое фиксируется в счетчике циклов 29. Блок 26 определяет адрес ячейки, начиная с которого поступающие в устройство коэффициенты полинома размацаются в блоках памяти. Адрес с выхода блока 26 поступает в блок 25 управления записью. По входу 30 устройства поступают значения независимой переменной X, которые записываются в регистр 6 и затем коэффициенте полинома , ад ,а . . . , а,ао. Коэффициенты поступают в устройство в порядке уменьшения их номеров и по сиг налам с выходом блока 25 управления записью размещаются в ячейках блоков 21-24 (фиг.З). Значение независимой переменной х с второго выхода регистра 6 поступае на первые входы множимого и множителя умножителя 18 и на первый вход множимого умножителя 13, Значение х полученное в умножителе 18, с первого его выхода записывается в регистр 11 и поступает на третий вход множителя умножителя 13 и на первые входы множимого и множителя умножителя 8. Полученное на первом выходе умножите ля 13 значение х записывается в регистр 16. На первом выходе умножителя 8 получается значение х, которо записывается в регистр 1, Одновремен но, из блоков 21-24.считываются значения коэффициентов, находящихся в первых ячейках, и записываются, соответственно в регистры 2, 7, 12, 17. Выход регистра 1 подключается к входу множителя умножителя 3 и к входам умножителей 8, 13, 1В, а к входам множимого умножителей 3,8, 13, 18 подключаются соответственно выходы регистров 2,7,12, 17, Затем во всех умножителях одновременно выполняется операция умножения. Результаты умножения с выхода умножителя 3 и с вторых выходов умножителей 8, 13, 18 поступают соответственно на первые входы сумматоров 4, 9, 14, 19, на вторле входы которых подаются значения коэЛфициентов, считанные из вторых ячеек блоков памяти. Результат с первых выходов сумматоров, записывается в регистры 5, 10, 15, 20 и далее на них передается через вторые входы в регистры 2, 7, 12, 17. После чего из задержимого счетчика 29 циклов сигналом, поступающим по входу 32 устройства, вычитается единица. На этом заканчивается первый цикл вычисления, в результате нлпсхпнения которого в регистре 2 находится значение регистре 7 значение , .в регистре 12 значение а..,, в регистре 17 значение а и в счетчике циклов 29значение . Второй цикл вычисления выполняется аналогично первому за исключением того, что результат из регистра 5 не передается в регистр 2, а хранятся так,, до следующего цикла. После выполнения второго цикла вычисления в регистре 5 находится значение ( , в регистре 7 - значение (), в регистре 12 - значение (а ) , в регистре 17 - значение и в счетчике циклов 29 - значение . При выполняется завершающий цикл вычисления, в котором первый выход регистра 6 подключается к второму входу множителя умножителя 8, к третьему входу множимого которого подключен выход регистра 7, выход регистра 11 подключается к четвер,тому входу множителя умножителя 13, пятый вход множимого которого соединен с выходом регистра 12, выход регистра 16 подключается к четвертому входу умножителя 18, пятый вход которого соединен с выходом регистра 17, второй выход регистра 5 подключается к третьем входу сумматора 9, первый вход которого соединен с вторым выходом умножителя 8, второй выход сумматора 9 подключается к третьему входу сумматора 14, первый вход которого соединен с вторым выходом умножителя 13, второй выход сумматора 14 подключается к второму входу сумматора 19, первый вход которого соединен с вторым выходом умножителя 18. Полученное на первом выходе умножителя 8 значение ( + )x поступает на первый вход сумматора 9 и суммируется там с операндом () , поступающим на третий вход сумматора с второго выхода регистра 5. Сумма с второго выхода сумматора 9 поступает на вход сумматора 14 и суммируется там с произведением . (а, ) X а)х, поступающим с первого выхода умножителя 13. Сумма с второго выхода сумматора 14 поступает на тре-тий вход сумматора 19, на первый вход которого поступает произведение )х с первого выхода умножителя 18. С выхода сумматора 19 значение вычисляемого полинома записывается в регистр 20. Из содержимого счетчика циклов 29 вычитается единица, после чего в устройство управления по второму выходу 34 выдается сигнал , по которому вычисление полинома заканчивается и результат с первого выхода регистра 20 по первому выходу 33 вьщается из устройства. Применение предлагаемого устройства позволяет увеличить скорость вычисления алгебраических полиномов в 4 раза. Формула изобретения Устройство для вычисления полино мов, содержащее первый регистр, выход которого подключен к входу множителя первого умножителя, вход мно жимого которого соединен с выходом второго регистра, первый вход которого подключен к первому выходу третьего регистра, вход которого со единен с выходом первого сумматора, первый вход которого подключен к выходу первого умножителя; счетчик циклов, первый вход которого соединен с первым входом устройства, а выход - соединен с первым выходом устройства, о.тличающееся тем, что, с целью повышения быстродействия,, в него введены три умножителя, три сумматора, регистры,блок задания количества циклов, четыре блока памяти, блок управления записью, формирователь начального адреса, причем выходы блока управления записью соединены соответственно с первыми входами блоков памяти вторые входы которых подключены к второму входу устройства, и к входу четвертого регистра, выход первого блока памяти соединен со вторы№1 входами второго регистра и первого сумматора, выход второго блока памя ти соединен с первыми входами пятого регистра и второго сумматора,пер вый выход которого соединен через 1 естой регистр со втопым входом пятого регистра, выход первого регист ра соединен с первыми входами второ го, третьего и четвертого умножите,лей, выходы которых соединены соответственно со вторым входом второго cy 1мaтopa и первыми входами третьего и четвертого сумматоров, первые выходы которых подключены соответст венно к входам седьмого я восьмого регистров, выход третьего блока памяти соединен с первыми входами девятого регистра и вторым входом тре тьего сумматора, второй выход которого соединен со вторым входом четвертого сумматора, выход седьмого регистра соединен со втопым входом девятого регистра, первый и второй выходы восьмого регистра подключены соответственно к второму выходу устройства и к первому входх, десятого регистра, выход четвертого блока памяти соединен со вторым входом десятого регистра и с третьим входом четвертого сумматора, первый выход второго умножителя соединен, с вторым входом второго сумматооа, второй выход которого подключен к третьему входу третьего сумматора, второй выход третьего регистра соединен с. третьим входом второго сумматора, первый выход четвертого регистра и выход пятого регистра соединены соответственно со вторым и третьим входами второго умножителя, второй выход которого подключен ко. входу первого регистра, второй выход четвертого регистра - к второму и третьему входу четвертого умножителя и ко второму входу третьего умножителя , выход четвертого умножителя .соединен с третьим входом тре.тьего умножителя, четвертым и пятым входами второго умножителя, и со входом одиннадцатого регистра, выход которого соединен с четвертым входом третьего умножителя, пятый вход которого подключен к выходу девятого регистра, второй выход третьего умножителя соединен через двенадцатый регистр с четвертым входом четвертого умножителя, пятый вход которого соединен с выходом десятого регистра, третий вход устройства соединен через тринадцатый регистр с- входами формирователя начального адреса и блока задания количества циклов, выходы которых соединены соответственно со входом блока управления записью и вторым входом счетчика циклов. Источники информации, принятые во внимание при экспертизе 1, Авторское свидетельство СССР № 556446, кл. G 06 F 15/32, 1976, 2. Патент США № 3978326, кл. 235-152, 1970 (прототип).

( gfl I yt TT

jff

32

рые.З