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

 

УСТРС СТВО ДЛЯ ВЫЧИСЛЕНИЯ МНОГОЧЛЕНОВ, содержащее входной регистр, m сумматоров и ( Vn + 1) регистров коэффициентов, выходы YTI, из которых подключены к входам соответствующих сумматоров, вторые входы первого сумматора соединены с Выходами входного регистра, отличающееся тем, что, сЦепью повышения быстродействия, в устройство введены п блоков постоянной памяти первой группы, т блоков постоянной памяти второй, г руппы и суммирующий блок, входы которого соединены с выходами блоков постоянной памяти второй группы, входы которых соответствехшо (Л подключены к выходам сумматч ов, пер , Bbie входы которых соединены с выходами регистров коэффициентов, а вторые входы каящого i -го сумматчра (- г ,т) соединены с выходами i -го блока постоянной памяти первой группы, входы блоков постоянной памяти первой группы соединены с выходами входного регистра, выходы первого блока постоянной памяти 4: первой группы подключены ко входам ас сумм1фующего блока, другие входы которого соед1шены с выходами ( m 4- 1 )-го регистра коэффициентов, а выходы су мм Иг00 ру ющего блока соединены с выходами устройства.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТ ИЧЕСНИХ

РЕСПЖЛИН (19) (И) 3(59 6 06 F 15/31

- Ñ=È9Ìàìà З и:. rLarne т г p" °,а k.;àú. l aj Iiy(jк я

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2l) 3440742/18-24 (22) 19.05.82 (46) 15.10.83. Бюл. № 38 (72) Б. И. Горшков, B. И. Жабин, В. И. Корнейчук, В. В. Макаров, М. А. Раков и B. П. Тарасенко (7l) Киевский ордена Ленина политехни-. ческий институт им. 50 летия Великой . Октябрьской социалистической революции (53) 681.325 .(088.8) (56) 1. Патент Японии № 49-28212,, кл. Q 06 F 15/OO, опублик. 1974.

2. Благовещенский Ю. А., Теслер Г.С.

Вычисление элементарных функций на ЗВМ.

Киев, "Техн(.ка", 1977, с. 68-72, 3. Авторское свидетельство СССР № 451088, кл. Cj 06 Г 15/31, 1972.

4, Авторское свидетельство СССР № 556446, кл. Cj 06 Р 15/31, 1975.

5- Кнут Д. Искусство программирования для ЭВМ, Т. 2 М., "Мир", 1977, с. 511.

6. Шауман А. М. Основы машинной арифметики. Л., изд-во Ленинградского унга, 1979, с. 187.

7. Полупроводниковые запоминающие устройства. Под реп А. Ю. Гордонова.

М., Радио и связь, 1981, с. 181.

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

¹ 868767, кл. Cj 06 F 15/31, 1978. (прототип) а

9. Справочник по интегральным м)нфосхемам. Под ред. Б. В. Тарабрина. М., Энергия", 1980, с. 124-186. 10. Карцев М. А., Брик В. А. Вычислительные системы и синхронная ариф метика. М., "Радио и связь", 1981, с. 205. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МНОГОЧЛЕНОВ, содержащее входной регистр, m сумматоров и (t ai + 1) регистров коэффициентов, выходы 1д, из которых под,ключены к первым входам соответствуюших сумматоров, вторые входы первого сумматора соединены с выходами входного регистра, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены Ф блоков постоянной памяти первой группы, Ф блоков постоянной памяти второй группы и суммируюший блок, входы которого соединены с выходами блоков постоянной памяти второй группы, входы которых соответственно подключены к выходам сумматоров, пер, вые входы которых соединены с выходами регистров коэффициентов, . а вторые входы каждого (-го сумматора ((= 1,m) соединены с выходами (-го блока

I постоянной памяти первой группы, входы блоков постоянной памяти первой группы соединены с выходамч входного регистра, выходы первого блока постоянной памяти первой группы подключены ко входам суммирующего блока, другие входы которого соединены с выходами (rn+ 1)-го регистра коэффициентов, а выходы суммируюшего блока соединены с выходами устройства

1048481

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

Известны устройства (1), предназна- S ченные для вычисления многочленов

9(х) = До+О,к+Ь2Х + + Ьпзх представляющие собой универсальные вычислительные машины, содержащие регистры, сумматоры, память, устройства управ10 ления. Вычисление многоиленов в них осуществляется путем выполнения соответствующих программ, например программ вычисления многочлена по схеме корнера.

Для выполнения этих программ необходимо осуществить tn сложений и m умножений, где а- степень многочлена. Кроме . ,того, затрачивается время на обращение к памяти за операндами и командами и на модификацию команд. В слуаях, ко да вычисление многсчленов необходимо производить многократно для различных значений аргумента Х при фиксированных значениях коэффициентов Cl;,- используются методы предварительной обработки ко- 5 эффкциентов, что уменьшает требуемое число умножений (21.

В частности, для вычисления многочлена шестой степени в этом случае необходимо выполнить четыре умножения и семь сложений, т;е. на два умножения меньше, чем по схеме Горнера.

Недостатком устройств, в которых

1 реализованы программные методы вычислений, является низкое быстродействие, . 35 что объясняется необходимостью не только многократного выполнения операций умножения и сложения, но и многократного обращения к запоминающему устройству за операндами и командами, моди- 40 фикации команд и т. д. Известны также устройства для вычис- ления многочленов, в которых реализованы аппаратурные методы вычислений, что позволяет производить вычисления бысч 45 рее, чем в устройствах, работающих по программному принципу. К устройствам такого типа относятся устройство для вычисления полиномов (3), содержащее регистры операндов и промежуточных 50 результатов, сумматоры, схемы И, блок управления и устройство для вычисления полиномов (4), содержащее регистр, сумматоры, реверсивный счетчик, схему сравнения, элементы И, элемент задерж- 55 кие

Недостатком таких устройств также является низкое быстродействие. Например, для вычисления.многочлена в первом из,них необходимо выполнитьй .N цик. лов вычислений, каждый,из которых сос» тоит из суммирования и сдвига. Второе из известных устройств производит вычисление многочленов в следящем режиме и обладает низким быстродействием для больших раосогласований аргумента., Известны табличные устройства для вычисления многочленов, содержащие постоянные запоминающие устройства для получения степеней х аргументах для умножения их на соответствующий коэффициент Q; (5J., (однако табличная реализация умножения затруднена тем, что при разрядности операндов и > 6 требуется большой обьем постоянной памяти, равный 2 " п бит (6, В связи с этим применяют методы умножения с использованием таблиц логарифмов и антилогарифмов, а также {что более экономично) габлиц квадратов чисел.

Во втором случае умножения чисел х и у осуществляется по формуле х (х+у) (и-у)2 -, Однако в этом случае необходим боаьmofi объем постоянной памяти. Так, для реализации одного умножения иеобходиМо иметь два ПЗУ емкостью 2 + и

6+4 где 1 - разрядность операндов. Для построения табличного устройства, предназначенного для вычисления многочлена, например, пятой степени, требуется четырнадцать ПЗУ. Четыре из них используются для вычисления значений X г, у, 4, х и десять - для умножения следующих

5 пар чисел а х ф02Х эcl3x lO4X г з 4

0" Х . Суммарный объем постоянной памяти должен состаэлять 4(2 и } +

+ 10(2" ° И ) бит, что, например при

12, будет иметь величину 688 бит.

Таким образом, известные табличные „ устройства требуют для построения боль- . шого объема оборудования.

Наиболее близким к предлагаемому является устройство для вычисления многочленов вида.E А хг $8), содержащее

1 Ъ накапливающие сумматоры, сдвиговые ре- гистры, регистры операидов, регистры коэффициентов, формирователи цйфр, регистры цвфры. Перед .началом вычислений в регистрах коэффициентов и в сумматорах записаны коэффициенты 0;, в регистрах операндов записан Х . Вычисления в известном устройстве производятся

481

3 : 1048 в (2 сО(2 (N 1- 1) - 0 ) циклах, каждый из которых состоит из суммирования и сдвига.

Недостатком данного устройства являЬтся низкое быстродействие. Действитель- 5 но время вычислений составляет

: " ( × 0.с t P,â, где t - время суммирования, 1 „ - время сдвига. . f0

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

Постарленная цель достигается тем, что в устройство, содержащее входной регистр, m сумматоров и (tn 1 ) регистров коэффициентов, выходы Е иэ которых подключены к первым входам соответствующих сумматоров, вторые входы цер-.-. вого сумматора с выходами входного регистра, введены Ю блоков постоянной па-, >0 мяти первой группы, Ю бпоков постоянной памяти второй группы и суммирующий блок, входы которого соединены с выхо-. дами блоков постоянной памятй второй группы, входы которых соответственно. подключены к выходам сумматоров, пер вые входы которых соединены с выходами регистров коэффициентов, а вторые входы каждого -ro сумматора (i = .с,И ) соединены с выходами -го блока посто янной памяти первой группы, входы блоков постоянной памяти первой группы соединены с выходами входного регистра, выходы первого блока постоянной памяти первой группы подключены ко входам суммирующего блока, другие входы которого соединены с выходами (ill+ 4 )-го регистра. коэффициентов, выходы суммиву ющего блока соединены с выходами устройства.

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

Выходы входного регистра 1 соедйне. ны с входами блоков постоянной памяти

2-5, чисно которых равно степени мно. гобелена m, и с первыми входами сумма тора 6. Выходы каждого блока постоян-» ной памяти 3 — 5 подключены к первым. входам сумматоров 7 - 9. Вторые вхо- " ды каждого сумматора 6 - 9 связаны c,, выходами блока коэффициентов 10. Реги стры 11 — 15, число которых равно (VA 1 ), входят в состав блока коэффициентов 10. Выходы сумматоров 6 — 9 Ы связаны с входами блоков постоянной памяти 16 - 19, число которых равно

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

zgm - (x 2 + х 4 < х 6 +x2) ° B блоке постоянной памяти 3 - 5 записаны таблицы для возведения чисел в степень, причем в блоке постоянной памяти 3 эаписа» ны числа, равные Х, в блоке постоян

2 ной памяти 4 числа, равные х и т. д., 9 а в блоке постоянной памяти 5 записаны числа x . В блоке постоянной памяти

16 - 19 записаны таблицы возведения чисел в квадрат. Суммирующий блок 20 предназначен для суммирования (Я+2 ) чисел и может быть построен, например, в виде дерева сумматоров.

Перед началом вычисления многочлена

F(xf = а, а,x а, х2 " а х " аргумент х записан во входном регистре

1, а коэффициенты а, - в блоке коэффициентов 10. При этом в каждом регист ре коэффициентов 11 — 14 записан соответственно коэффициент а „(4 = 1, rn ), а в регистре коэффициентов 15 — коэффициент с- 0 4 (a „ а р+ "+а т ).

1 i г 2 а

Вычисление многочлена осуществляеъся следующим образом.

С выходов входного регистра 1 зна- чение аргумента х поступает на. адресные входы блоков постоянной памяти

2 - 5, а также на одни из входов сумма тора 6. На выходах блока постоянной памяти 2 формируется значение функции(х ФхФФ х6+-+)Р ), а на выходах блоков постоянной памяти 3 - 5 - соответственно значения Х 2, Х ... Х . В каждом сумматоре 6 — 9 осуществляется сумми рование коэффициента 0;, поступающего с соответствующего выхода регистра коэффициентов 11 - 14 и значения Х в соответствии с формулой $ а; +х . Слова с выходов сумматоров 6 — 9 поступают на адресные входы блоков постоянной памяти 16 - 19, где возводятся и KB8ltрат. Окончательное значение многочлеаа

F (Х ) формируется в следующем блоке 20 путем суммирования слов, поступающих с выходов блоков постоянной . памяти 2, 16 — 19 и регистра коэффициента 15.,Таким образом, на выходах 21

1048481 п(28оф (ю ). „) 1, (2п+28одя(в+2) !о) 1+ ,ДНИИПИ Заказ 7934 55 Тираж 706 Подписное

Филиал ЛПГ! "Патент", г. Ужгород, ул. Проектная, 4 устройства значение многочлена формируется в виде

® 0 «4(о >< ° +a )-(х х +х .2,2 я +") (а, х ) + „. +.

+ щг

2 a+ х ) = ао1а, x+a х +о х «„,+

>Отп х и, S0

Время вычисления многочлена составllew BT

С1 ° где о - время обращения к блоку посто янной памяти; !

5 ;« время суммирования двух ч« сел в сумматорах 6 - 9; с,- время суммирования (Из ф ) чисел в суммирующем бло20 ке 20,:

Время вычисления многочлена в дацном устройстве составляет (о с- « с .

Сравним 4о с. задержкой в однозарядном сум маторе Ь+ à Hanp имер задержка сигнала в блоке постоянной памяти на основе микросхем К155РЕ1 составляет

60 нс, а задержка в четырехзарядном сумматоре (микросхема К155ИМЗ)

55 нс (.93;

В этом случае можно принять|о 51+

При построении суммирующего блока в виде многослойного сумматора 10! время сложения (m + 2) чисел в нем с, - (n + 23о, (m+2) ° 4, Тогда время вычислений в известном устройстве (прототипе) и рЕog.(-" ц,+,„,)

Р«3

4, 24 с„ раз больше времени вычислений в пред-,, лагаемом устройстве (Здесь временем амеде пренебрегаем). Например, для

=* 32, п 8 быстродействие увеличивает ся в Р 16 раз. Кроме того, предложенное устройство требует для построения меньшего объема памяти, чем известное табличное устройство. Так, общий объем постоянной памяти в данном случае составляет при и1 5 и п 12 величину 10 {2 Е 12} 492 К бит, т. е. на 688 К вЂ” 492 К *. 196 К бит мень ше, чем и известном устройстве.