Устройство для вычисления полиномов

 

Союз Советскнх

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

<о813443

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву (22) Заявлено 020678 (2!) 2623220/18-24 с присоединением заявки Ко

{23) Приоритет

Опубликовано 15.0 381. Бюллетень Н910

Дата опубликования описания 15.0 381 (51) М. Кл.з

G 06 F 15/32

Государственный комитет

СССР ио делам изобретеиий и открытий (53) УДК 681. 14 (088. 8) (72) Авторы изобретения

О,н.ньявченко, A A,ëóêoíèí, я.е.Ромм и и.ф.,сурженко!

Таганрогский радиотехнический институт нм, В,J.Калмыкова

Иинистерства высшего и среднего специального. образования РСФСР— . и (7 3 ) Заявитель

{54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОИОВ

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

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

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

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

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

Поставленная цель достигается тем, что в устройство для вычисления полиномов, содержащее первый регистр, выход которого подключен к входу множителя первого умножителя, вход множимого которого соединен с выходОм второго регистра, первый вход которого подключен к первому выходу третьего регистра, вход которого соединен с выходом пе рв о го сумматора, первый вход к оторого подключен к выходу первого

15 умножителя, счетчик циклов, первый вход которого соединен с первым входом устройства, а выход — соедине н с первым выходом ус т ройс т в а, введены три умножителя, три сумма20 тора, регистры, блок задания количеатва циклов, четыре блока памяти, блок управления записью, формирователь начального адреса, причем выходы блока управления записью соединены соответственно с первыми входами блоков памяти, вторые входы которых подключены к второму входу устройства, и к входу четвертого регистра, выход первого блока

30 памяти соединен со вторыми входами

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

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

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

Работа устройства (на примере вычисления полинома степени n=10) заключается в следующем. полинома степени n=15; на фиг. 3 размещение коэффициентов в ячейках блоков °

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

B устройстве и олиномы вида и и-1

Y=a„x +a „> x + ° ° ° +a„x +a p где Y — значение вычисляемого полинома; а„,а„ „,...а.,ар — коэффициенты поли- х — независимая перемен-. ная, п a15 — степень полинома, целое положительное число, разбиваются на четыре ветви,в которых вычисляются значения Yq, Yg, Yy, У4 сумма которых равна Y.

ПРичем значения У< У2, Уз У4 вы числяются одновременно. B устщ ройстве могут вычисляться полиномы любой степени а415. При и 4 15 коэффициенты при отсутствующих старших степенях х(а,,a «,...a„+j) полагаются равными нулю. Коэффициаи,a т-q . a,ap поступают из памяти на вход 30 устройства и размещаются. в блоках 21 — 24

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

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

5,, блоков 26 и 25.

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

1=2 при 1м и< 7

1=3 при 8<п 11

1=4 при 12 п<15

81344 3

Вычисление полинома начинается с того, что в регистр 27 по входу 31 устройства поступает порядок заданного полинома. Блок 28 определяет необходимое количество циклов вычисления п-3, которое Фиксируется в счетчике циклов 29. Блок 26 определяет адрес ячейки, начиная с которого поступающие в устройство коэффициенты полинома размещаются в блоках памяти. Адрес с выхода блока 26 поступает в блок 25 управления записью. По входу 30 устройства поступают значения независимой переменной х, которые записываются в регистр 6; и затем коэффициенты полинома а,р,аэ,аа а(iao. Коэффи- 15 циенты поступают в устройство в порядке уменьшения их номеров и по сигналам с выходом блока 25 управления записью размещаются в ячейках блоков

2l-24 (фиг. 3) . 20

Значение независимой переменной х с второго выхода регистра 6 поступает на первые входы множимого и множителя умножителя 18 и на первый вход множимого умножителя 13, Значение х полученное в умножителе 18, с первого его выхода записывается в регистр

11 и поступает на третий вход множителя умножителя 13 и на первые входы множимого и множителя умножителя 8, 3g

Полученное на первом выходе умножителя 13 значение х записывается в регистр 16. На первом выходе умножителя 8 получается значение х4, которое записывается в регистр 1, Одновременно, из блоков 21-24.считываются значения коэффициентов, находящихся в первых ячейках, и записываются,соответственно в регистры 2, 7, 12, 17.

Выход регистра 1 подключается к входу множителя умножителя 3 и к входам 40 умножителей 8, 13, 18 а к входам множимого умножителей 3,8, 13, 18 подключаются соответственно выходы регистров 2,7,12, 17, Затем во всех умножителях одновременно выполняется 45 операция умножения, Результаты умножения с выхода умножителя 3 и с вторых выходов умножителей 8, 13, 18 поступают соответственно на первые входы сумматоров 4, 9, 14, 19, на вторые входы которых подаются значения коэффициентов, считанные иэ вторых ячеек блоков памяти, Результат с первых выходов сумматоров. записывается в регистры 5, 10, 15, 20 и далее на них передается через вторые входы в регистры 2, 7, 12, 17.

После чего из задержимого счетчика

29 циклов сигналом, поступающим по входу 32 устройства, вычитается единица. На этом заканчивается первый 40 цикл вычисления, в результате выполнения которого в регистре 2 находится значение арх +а,в регистре 7

4 значение а х4+а, в регистре 12 значение а, x4+а, н регистре 17 — 65 значение а и в счетчике циклов 29значение 1=2.

Второй цикл вычисления выполняется аналогично первому за исключением того, что результат из регистра 5 не передается в регистр 2, а хранятся так,. до следукщего цикла. После выполнения второго цикла вычисления в регистре 5 находится значение (а8х4+ а к +ao в регистре 7 — значение (а х +а ) х"+a«s регистре 12 — значение (а вх +а )х +а, в регистре

17 — значение а x4+àз и в счетчике циклов 29 — значение 1 =1.

При 1=1 выполняется завершающий цикл вычисления, в котором первый выход ре гис тра 6 подключается к в торому входу множителя умножителя 8, к третьему входу множимого которого подключен выход регистра 7, выход регистра 11 подключается к четвертому входу множителя умножителя

13, пятый вход множимого которого соединен с выходом регистра 12, выход регистра 16 подключается к четвертому входу умножителя 18, пятый вход которого соединен с выходом регистра 17, второй выход регистра

5 подключается к третьему входу сумматора 9, первый вход которого соединен с вторым выходом умножителя 8, второй выход сумматора 9 подключается к третьему входу сумматора 14, первый вход которого соединен с вторым выходом умножителя 13, второй выход сумматора 14 подключается к второму входу сумматора 19, первый вход которого соединен с вторым выходом умножителя 18. Полученное на первом выходе умножителя 8 значение (а х +

4 о

a x +a ) х поступает на первый вход сумматора 9 и суммируется там с операндом (а х +a4) х +а, поступающим

4 4 на третий вход сумматора с второго выхода регистра 5. Сумма с второго выхода сумматора 9 поступает на третий вход сумматора 14 и суммиру4 4 ется там с произведением (а ох +а ) х а ) х, поступающим с первого выхода умножителя 13. Сумма с второго выхода сумматора 14 поступает на третий вход сумматора 19, на первый вход которого поступает произведение (a>xi+a>jx с первого выхода ум3 ножителя 18. С выхода сумматора 19 значение вычисляемого полинома записывается в регистр 20. Из содержимого счетчика циклов 29 вычитается единица, после чего в устройство управления по втор ому выходу 34 выдается сигнал 1=0, по которому вычисление полинома заканчивается и результат с первого выхода регистра 20 по первому выходу 33 выдается иэ устройства.

В

Применение предлагаемого устройства позволяет увеличить скорость вы81344 3 числения алгебраических полиномов в

4 раз а.

Формула изобретения

Устройство для вычисления полиномов, содержащее первый регистр, выход которого подключен к входу множителя первого умножителя, вход множимого которого соединен с выходом второго регистра, первый вход которого подключен к первому выходу третьего регистра, вход которого соединен с выходом первого сумматора, первый вход которого подключей к выходу первого умножителя, счетчик циклов, первый вход которого соединен с первым входом устройства, а выход — соединен с первым выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия,в него введены три умножителя, три сумматора, регистры, блок задания количества циклов, четыре блока памяти, блок управления записью, формирователь начального адреса, причем выходы блока управлени я з апис ью соединены соответственно с первыми входами блоков памяти, вторые входы которых подключены к второму входу устройства, и к входу четвертого регистра, выход первого блока памяти соединен со вторыми входами второго регистра и первого сумматора, выход второго блока памяти соединен с первыми входами пятого регистра и второго сумматора,первый выход которого соединен через иестой регистр со втопым входом пятого регистра, выход первого регистра соединен с первыми входами второго, третьего и четвертого умножителей, выходы которых соединены соответственно со вторым входом второго сумматора и первыми входами третьего и четвертого сумматоров, первые выходы которых подключены соответственно к входам седьмого И восьмого регистров, выход третьего блока памяти соединен с первыми входами девятого регистра и вторым входом третьего сумматора, второй выход которого соединен со вторым входом четвертого сумматора, выход седьмого регистра соединен со втогым входом девятого регистра, первый и второй выходы восьмого регистра подключены

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

20 выход которого подключен ко входу первого регистра, второй выход четвертого регистра — к второму и третьему входу четвертого умножителя и ко второму входу третьего умножите2 ля, выход четвертого умножителя,соединен с третьим входом третьего умножителя, четвертым и пятым входами второго умножителя. и со входом одиннадцатого регистра, выход которого соединен с четвертым входом третьего умножителя, пятый вход которого подключен к выходу девятого регистра, второй выход третьего умножителя соединен через двенадцатый регистр с четвертым входом четвертого умножителя, пятый вход которого соединен с выходом десятого регистра, третий вход устройства соединен через тринадцатый регистр с. входами формирователя начального адреса и блока за40 дания количества циклов, выходы которых соединены соответственно со входом блока управления записью и. вторым входом счетчика циклов, 45 Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 556446, кл. G 06 F 15/32 1976, 2, Патент США У 3978326, кл. 235-152, 1970 (прототип). !

813443 (Рис. 2

Фас.3

Составитель Н. Палеева редактор И. Касарпа Техред М. Табакович . Корректор Г. Решетник

Заказ 775/6 3 Тираж 745 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открнтиА

11 3035, Москва, Ж-35, РаушскаЯ наб., д .4/5 филиал ППП Патент, r.Óæãîðoä, уп.Проектная, 4