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

 

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

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

«п868767 (61) Дополнительное и авт. свид-ву (22) Заявлено 20,1078 (21) 2675964/18-24

М Кпа с присоединением заявки М (23) Приоритет

G F 15/31

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

СССР по делам изобретений н открытий

Опубликовано 300981, Бюллетень Ио 36

Дата опубликования описания 3009.81 (5З) НЖ 681. 3 (088.8) В.И. Жабин, В.И. Корнейчук, А.В. Супрун, B„II. ТарасейКст « (72) Авторы изобретения и A.À. Щербина

М А Зализ НП ,Я1 н эГ д 4 ь|,1

Я Г с

° гЛ и

Киевский ордена Ленина политехнический инстйтуг Ъ4М. 58 — летия--:>

Великой Октябрьской социалистической революции (7! ) Заявитель (54) УСТРОЙСТВО ДЛВ ВЫЧИСЛЕНИЯ МНОГОЧЛЕНОВ ф

ВИДА W A ° X1

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

Известны устройства, предназначенные для вычисления многочленов,представляющие собой универсальные цифровые вычислительные машины, и вычисле- 10 ние многочленов вида А Х + А „Х +

Ь-1

+ ...+ A X + A«X в них осуществляется путем выполнения соответствующей программы 111 и 2 .

Однако программному способу вычисления многочленов в ЦВМ требуются 15 многократное умножение и сложение операндов, многократное обращение к запоминающему устройству, дополнительные затраты времени на модификацию команд, кроме того, возникают 20 трудности при получении результата повышенной точности, что обуславливает низкое быстродействие известных устройств.

Наиболее близким к предлагаемому является вычислительное устройство для вычисления многочленов вида й1 4; g содержащее регистры степеней

Х, связанные со входами накапливаю- 30 щих сумматоров, тактирующую шину, соединенную со входами сдвига накапливающих сумматоров 33J .

Это устройство обладает более высоким быстродействием по сравнению с вышеуказанными, так как при вычис% лении многочленов вида „ А"Х" здесь

=c не требуется многократного обращения к запоминающему устройству, многократного умножения и сложения операндов.

Быстродействие известного устройства определяется по формуле

T1 % (3 С в.) где л — разрядность Х и A, ф — степень,многочлена, .

t - время суммирования;. асср„ — время сдвига.

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

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

Поставленная цель достигается тем, что в устройство для вычисления мно% гочленов вида;" A Х", содержащее ре.— та В 1 гистр операнда Х, выход которого соединен с первыми информационными входами накапливающих сумматоров, входы

868767 и = 2, 3, 4), S сдвиговых n" ðàçðÿäíûõ регистров 2 коэффициентов А„ и регистров 3 сперандов со (U=max9; f=Q 0Я Р="Л .)=0

О, если Х вЂ” дробное, F(x) если Х " целое, 40 количество входов накапливающего сумматора),S формирователей 4 цифры,S двухразрядных регистров 5 цифры, тактирующую шину 6, выходную шину. ?. Каждый р-ый накапливающий сумматор 1 содержит 4+2 "n разрядов, если f «r, 2, и n + 3 разрядов, если

1. Каждый r-ый (r =1,u) регистр

3 содержит 2 ° и разрядов. — 50

Выход )-го разряда (1 = 1,и) первого регистра 3 (первыми всюду будем считать старшие разряды) соединен со входом J+3-ro разряда каждого накапливающего сумматора 1. Выход i-го разряда (i = 1,2 ° и) r--го регистра

3 соединен со входом fj+4+2(f-z)j -го разряда 2 ° р-ro накапливающего сумматора 1. Выход старшего разряда р-го регистра 2 подключен ко входам -приема кода первого регистра 3 на р-ый О накапливающий сумматор 1. Каждый р-ый формирователь 4 цифры содержит. логические элементы, связанные с прямыми и инверсными выходами трех первых разрядов р-го накапливающего суммато- g5 сдвига которых соединены с тактирующей шиной устройства, введены регистры цифр, формирователи цифр, сдвиговые регистры коэффицяентов А1, соединенные выходами с первыми управляющи/ ми входами соответствующих накапливающих сумматоров и регистры операндов

Х "(i = 1,2... ), выходы каждого иэ которых соединены с (i+1)-м информационным входом каждого 2 j-ro (j

1,2...) накапливающего сумматора, причем вход j-го формирователя цифры l0 соединен с выходом j-го накапливающего,сумматора, а выход — со входом

J"-гр регистра цифры, выход которого подключен к (f+1)-му управляющему входу г

%=Q ЕМ1ег.(En(1ez(- — )J 2 i -ro в=о накапливающего сумматора, тактирующая шина устройства, соединена со входами сдвига сдвиговых регистров коэффициентов А„ и входами приема кода регистров цифр, а выходная шина. устройства соединена с вь1ходом пос- . леднего регистра цифры.

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

Устройство содержит S накапливаюЧ +.I щих сумматоров 1 (Я = и, 9 = 2 -1; ра 1; в соответствии с системой переключательных функций

„=а,(а аЗ ч а а.)

1= а„Я а Ч а а ) где индексы аргументов соответствуют номерам разрядов сумматора 1, а индексы функций — номерам выходов формирователя 4 цифры. Выходы р-ro формирователя 4 цифры связаны со входами р-ro регистра 5, выход которого (кроме S-го регистра 5) связан со входами приема кода f+1-го регистра

3 на р+2 -ый накапливающий сумматор

1 ° Выход S-ro регистра 5 связан с выходной шиной 7.

Многовходовой параллельный накапливающий сумматор 1 содержит узлы приема кода 8, выполненные,.например, в виде элементов 2И-2ИЛИ, соединенные со входами комбинационного параллельного многовходового сумматора 9, выполненного, например, в виде матрицы или дерева сумматоров, выходы которого соединены со входами сдвигающего регистра 10, выполненного, например, на D-триггерах с внутренней задержкой, выходы которого подключены ко входам сумматора 9. Разрядные входы узлов приема кода 8 соединены с прямыМи и инверсными выходами регистров 3, а их управляющие входы соединены с выходами регистров 2 и 5. Кроме того, управляющие входы выдачи инверсных кодов регистров соединены со входами переносов в младший разряд сумматора 9, выходы трех старших разрядов которого подключены ко входам формирователя цифры 4, а управляющие входы регистра 10 связаны с тактирующей шиной 6.

Устройство работает следующим образом.

В исходном состоянии в каждом р-ом сумматоре 1 записан коэффициент

Аи(з р), начиная с третьего разряда, если сумматор 1 одновходовой, и с

2(f+i)-ro разряда, если сумматор 1fвходовой, в каждом р-ом регистре 2 записан коэффициент А1(З р)+„, в каж дый z. --ый регистр 3 занесено число

Х, в регистры 5 записаны нули.

В каждом i-ом цикле вычисления цифра, записанная в старшем разряде р+2- ro регистра 2, и цифра промежуточного результата, записанная в р-м регистре 5, управляют типом операции, выполняемой р+2 ""-ым сумматором 1, таким образом, что к его содержимому прибавляется код регистра

ЗГ+1, если в регистре 5 записана плюс единица или из его содержимого вычитается код регистра Çf+1, если в регистре 5 записана минус единица.

Аналогичным образом цифра, записанная в старшем разряде регистра 2, управляет

868767 прибавлением или вычитанием кода регистра 3.

В результате анализа трех старших разрядов р+2 " -го сумматора 1 р+2 -"-ый формирователь цифр 4 формирует очередную цифру промежуточного результата. Эта цифра равна, плюс единице, если содержимое трех старших разрядов сумматора 1 равно 001 или 010, минус единице — если содержимое трех старших разрядов равно

110 или 101, нулю — в остальных случаях. Затем по сигналу в тактирующей .шине 6 происходит сдвиг влево на один разряд содержимого регистров 2 и сумматоров 1, причем содержимое третьего разряда каждого сумматора 1 при 15 сдвиге заносится не только во второй разряд, но и в первый, а на первые

S — 1 регистров 5 принимаются коды цифр промежуточных результатов, сформированные соответствующими формирователями цифр 4. Код цифры окончательного результата, сформированный

5-ым формирователем цифры 4, принимается на S-ый регистр 5 и поступает на выходную шину 7. Для получения результата с точностью до п разрядов после запятой необходимо выполнить

2 log<(9+1)+n циклов вычисления.

Предлагаемое устройство позволяет вычислять значение многочлена с точ-, ностью до п цифр после запятой за вре- () мя

7 =(, ИО g+ )+n)(

Следовательно, предлагаемое устройство превосходит по быстродействию известное в т„

Т 1 ?.РО (g+1)+Yl

40 . Например, при разрядности n = 32 предлагаемое устройство позволяет вычислять многочлен 3-ей степени в

2,67 раз быстрее известного, 7-ой степени — в 5, 89 раз, 15-ой степени -, в 12 раз быстрее.

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

Устройство для вычисления много% членов вида3:, А;Х, содержащее регистр

-0 операнда Х, выход которого соединен с первыми информационными входами накапливающих сумматоров, входы сдвига которых соединены с тактирующей шиной устройства, о т л и ч а ю щ е е ,с я тем, что, с целью повышения

;быстродействия, в устройство введены регистры цифр, формирователи цифр, сдвиговые регистры коэффициентов A ° соединенные выходами с первыми управляющими входами соответствующих накапливающих.сумматоров.и регистры операндов Х (i = 1, 2... ), выходы каждого из которых соединены с (i+1 ) -м информационным входом каждого 2 j-го (j

1,2...) накапливающего сумматора, причем вход )-го формирователя цифры соединен с выходом j-го накапливаю,щего сумматора, а выход — со входом

j-ro регистра цифры, выход которого подключен к (f+1)-му управляющему

1 =Ь "" Г "" (-l)I (2 + ))-го накапливающего сумматора, тактирующая шина устройства соединена со входами сдвига сдвиговых регистров.коэффициентов A и входами приема кода регистров цифр, а выходная шина устройства соединена с выходом последнего регистра цифры.

Источники информации, принятые во внимание при экспертизе

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

Р 170218, кл. G 06 F 15/00, 1964.

2. Патент США 9 3740722, кл. 340-172.5, 1973.

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

Р 451088, кл. G 06 F 15/20, 1972 (прототип).