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

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМАm-И СТЕПЕНИ, содержащее сумматор, три входных регистра и. блок управления, отличающеес я тем, что, с целью повьшения быС тродействия, в устройство введены {т-2) входных регистра, (т +О выходных регистра,/ (№+2) (-О Л I ,--- „ 11 сумма- (п +l)rn торов, мультиплексоров, причем первые группы информационных входов входных регистров являются входами коэффициентов полинома устройства , казкдый ч -1 ярус устройства 1 0,... го) содеряшт входной регистр , (J + 1) сумматоров, и +1) мультиплексоров и выз одной регистр, причем в каждом ярусе устройства выходы входного регистра подключены к входам первой группы первого сумматора, выходы j-го сумматора } -го яруса устройства (),..., +0 подкл чены к входам первой группы IJ +1 -гЪ сумматора ( -го яруса устройства, выходы (i +1)-го сумматора i -го яруса устройства соединены с информационными входами выходного регистра . того же яруса устройства, входы второй группы сумматоров каждого яруса устройства подключены к выходам соответствующих мультиплексоров того же яруса устройства, информационные входы которых соединены с выходами соответствующих сумматоров последующего яруса устройства, выходы выходных регистров каждого яруса устройства подключены к вторым группам информационных входных регистров тех же ярусрв устройства, 1блок управления содержит генератор тактовых импульсов, регистр аргумента , счетчик тактов, элемент НЕ, два элемента И, группу элементов И и схему сравнения, выход которой соединен С первым управляющим входом генератора тактовых импульсов, второй управляющий вход которого подключен к шине пуска устройства и перСО 4i вым входам записи входных регистров, выход генератора тактовых импульсов QD соединен с синхронизирующим входом регистра аргумента, со счетным вхо дом счетчика тактов, входом элемен .та НЕ и первым входом первого элемента И, выход которого подключен к вторым входам записи входных регистров , второй вход первого элемента И соединен с первым входом второго элемента И, первыми входами элементов И группы и с выходом старшего разряда регистра аргумента, второй вход второго элемента И подключен к выходу элемента НБ а выход

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

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

РЕСПУБЛИК

Q9) (И),4 (51) С 06 F 15/31

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

1

"1

» (2 l ) 3535264/24-24 (22) 10.01.83 (46) 15.01.85. Бюл. У 2 (72) В.Д.Байков и А.Е.Баканов (71) Ленинградский ордена Ленина электротехнический институт им. В.И.Ульянова (Ленина) (53) 681. 325 (088. 8) (56) 1. Авторское свидетельство СССР

В 487392, кл. G 06 F 15/31, 1975.

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

Ф 675378, кл. G 06 F 7/544, 1981.

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

Ф 792263, кл. G 06 F 7/353, 1980.

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

У 575648, кл. G 06 F 15/31, 1975 .(прототип). (54) (57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ПОЛИИДА п) -Й СТЕПЕНИ, содержащее сумматор, три входных регистра и блок управления, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, в устройство введены (т-2) входных регистра, 1гя +11 выходных регистра, (m+2) (п-11

1 сумма(м +Ilm торов, 2 мультиплексоров, причем первые группы информационных входов входных регистров являются входами коэффициентов полинома устройства, каждый q -1 ярус устройства(=О,... и)) содержит входной регистр,(i +I) сумматоров, (1+1) мультиплексоров и выходной регистр, причем в каждом ярусе устройства выходы

J входного регистра подключены к входам первой группы первого сумматора, \ выходы 1-го сумматора < -го яруса устройства (j =l,..., +1) подключены к входам первой группы lj +I) -го сумматора -ro яруса устройства, » выходы (j +1)-ro сумматора i-ro яруса устройства соединены с информационными входами выходного регистра того же яруса устройства, входы второй группы сумматоров каждого яру. са устройства подключены к выходам соответствующих мультиплексоров того we яруса устройства, информационные входы которых соединены с выходами соответствующих сумматоров последующего яруса устройства, выходы выходных регистров каждого яруса устройства подключены к вторым группам информационных входных ре- O е гистров тех же ярусов устройства, блок управления содержит генератор ! тактовых импульсов, регистр аргумента, счетчик тактов, элемент НЕ, два элемента И, группу элементов И и схему сравнения, выход которой соединен с первым управляющим входом генератора тактовых импульсов, второй управляющий вход которого подключен к шине пуска устройства и первым входам записи входных регистров, выход генератора тактовых импульсов соединен с синхронизирующим входом регистра аргумента, со счетным входом счетчика тактов, входом элемен- Д .та НЕ и первым входом первого элемента И, выход которого подключен к вторым входам записи входных ре- ъ гистров, второй вход первого элемента И соединен с первым входом второго элемента И, первыми входами элементов И группы и с выходом старmего разряда регистра аргумента, второй вход второго элемента И подключен к выходу элемента НЕ а выход

ll г соединен с. входами записи выходных ре гистров, вторые входы элементов И группы подключены к выходам разрядов счетчика тактов и первой группе входов схемы срйвнения, вторая группа вхо34947 дов которои соединена с входами зна-. чения разрядности аргумента устройства1 выходы элементов И группы соединены с управляющими входами мультиплексоров.

Однако его быстродействие ограничено.

Известно устройство для вычисления полиномов Ц

Однако оно вычисляет полиномы только второй и третьей степени и при этом использует число-импульсное, а не цифровое преобразование.

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

:1пелинома в.-й степени, содержащее три элемента И, три регистра сдвига, З5 сумматор, первый вход которого соединен с выходом счетчика переноса,,второй - с выходом третьего регистра сдвига, а выход через второй элемент И вЂ” с входом первого регистра 40 сдвига. Выход последнего подключен к первому входу третьего элемента И, выход которого подключен к входу первого регистра сдвига. Второй вход третьего элемента И, управляющий

1 45

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

Известно устройство для вычисления значений полинома1й-й степени, содержащее два регистра сдвига с цепями циклического переноса, выходы регистров через первый элемент И сое- динены с входом счетчика переноса,,10 блок управления, выходы которого подключены к управляющим входам регистров сдвига, первого элемента И счетчика переноса Pl) .

Недостатком известного устройст.ва является отсутствие возможности совмещения во времени операций сложения и умножения °

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

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

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

Поставленная цель достигается тем, что в устройство для вычисления полиномащ -й степени содержащее сумматор, три входных регистра и блок управления, введеия(п1-2) входных регистра,(%+ l) выходных регистра, Im+2j m-1) (.3тъ + 1) fA

1! сумматоров, 2 мультиплексоров, причем первые группы информационных входов входных регистров являются входами коэффициентов

1 полинома устройства, каждый -й ярус устройства (< =0,... 1п)содержит вход- . ной регистр, (q +1) сумматоров,(+1) мультиплексоров и выходной регистр, причем в каждой ярусе устройства выходы входного регистра подключены к входам первой группы первого суьгматора, выходы j -го сумматора > -го яруса устройства (1 =1,... < +1) подключены к входам первой группы (j l)

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

947 ! где О (g ) — коэффициенты пслинома. о

Для двоичной системы счисления X можно представить как я

X=K, 5.".2 3

Раскрывая (2) по биному Ньютона, 15 запишем

f(.) - а.().

3 1134 подключены к вторым группам информационных входов входных регистров тех же ярусов устройства, блок управления содержит генератор тактовых импульсов, регистр аргумента, счетчик тактов, элемент НЕ, два эле1мента И, группу элементов И и схему сравнения, выход которой соединен с первым управляющим входом генератора тактовых импульсов, второй управляющий вход которого подключен к шине пуска устройства. к первым входам записи- входных регистров,. выход генератора тактовых импульсов соединен с синхронизирующим входом регистра аргумента, со счетным входом счетчика тактов, входом элемента НЕ и первым входом первого элемента И, выход которого подключен к вторым входам записи входных регист- 2О ров, .второй вход первого элемента И соединен с первым входом второго элемента И, первыми входами элементов И группы и с выходом старшего разряда регистра аргумента, второй вход элемента И подключен к выходу эле мента НЕ, а выход соединен с входами записи выходных регистров, вторые входы элементов И группы подключены к выходам разрядов счетчика тактов и первой группе входов схемы сравнения, вторая группа входов которой соединена с входами значеййя разрядности аргумента устройства, выходы элементов И группы соединены с управляющими входами мультиплексоров.

На фиг.1 представлена блок-схема устройства, на фиг.2 - блок-схема управления.

Устройство для вычисления полинома м-й степени(гл =3), содержит вход-ные регистры 1 — 4, выходные регистры 5-8,,комбинационные сумматоры

9. — 18, мультиплексоры 19 — 24, шины для ввода начальных значений коэффициентов полинома.25 — 28, блок управления 29,шину.30 пуска, шину 31 разрядности аргумента и шину 32 аргумента. Блок управления содержит . генератор 33 татовых импульсов, регистр 34 аргумента Y счетчик 35 тактов, элемент НЕ 36, два элемента И 37 и 38, группу элементов И 39 и схему сравнения 4g.

Полиномф(х) степени m имеет вид

Th

0х) Е. а;(хо) (х х о) (1 ) =0 где и — разрядность числа, g Ч 0,1Если сместить начальную гочку а на

1, 2", то получим!

Йх) Еа;(хд)(х-(х ; 2 1 + Я; 2 11,. (2) а (х,+ ; 2 )-Z c „„.Я; 2) а;(хд),(3)

1:б где С, — биномальные коэффициенты, тогда

Йх 12 .аз(х + 21)(к-(хо ;.2 )) Приближая Хо к значению Х, как сле дует из (1), имеем

Тогда основные вычислительные опе- рации состоят в реализации выражения (5), т.е. в вичислении коэффициентов полинома.

Их реализацию рассмотрим для слу чая йъ=3. а;-а,(х, ((1 2 1 -а ; 24, 2 а, "2 .а (4)

,-aô, ßó2) )*а,.5;-2 ау Я а =а (х,1@1 R) 1)-а Я1 2 ag

1 а *о (х +(g 2)1)=аy

1 где ao,а, >О -,Я : — коэффициенты полинома, соответствующие исходному значению ;

Qî, O,, a p коэфФициенты полинома после счещения на(Щ 2)х

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

1134947

В исходном состоянии по сигналупуск(р+1) коэффициентов a (x) загружаютсяя во входные регистры l — 4, а начальное значение j =0 подаетсй иа мультиплексоры 19 — 24, выполняющие функцию сдвига íà j разрядов вправо. Все операции выполняются на структуре вычисления в соответствии с соотношениями (4) с помощью сумматоров 9 — 18, мультиплексо- 10 ров 19 - 24 и представленной системы их связей. Так как мультиплексоры и сумматоры являются комбинационными схемами, то длительность так( та вычислений .выбирается, исходя из 15 самой длительной операции при вычислении коэффициента CID, после этого ((! промежуточный результат а0, О, а который формируется на выходнйх

1 регистрах (5 — 8} передается соответ- 31 ственно на входные регистры. Затем ( значение I увеличивается на единицу, 1 I коэффициенты ао, а,, 0>, Î выступают в качестве исходных для нового цикла, и процесс повторяется. Вычисления 25 завершаются при значении j = A а вычисленное значение полинома 1(х1 на-. ходится в регистре (!) . Таким образом, общее время вычислений равно М тактам, а кажцый такт пропорциона- эр лен nl с ло ж е н и я м, таким gáðàçîì следовательно, выигрыш в быстродействии по сравнению с прототипом соста-З5 вит " + 11 сп h

1 1 ъ1 +cn

Блок управления состоит из генератора 33 тактовых импульсов, выход которого соединен с регистром 34 аргумента )(счетчиком 35 тактов, инвертором 4 и с первым входом элемента И 37, выход элемента 36 подсоединен к первому входу элемента

И 38, а выходы счетчика 35 тактов — . к первым входам группы элементов И 39 . и схемы сравнения 40, второй вход которой служит для занесения значе- N ния разрядности аргумента Н . Выход схемы сравнения 40 соединен с входом генератора тактовых импульсов 33, причем выход старшего разряда регистра 34 аргумента подключен к всем вторым ° входам элементов И 37, 38 и группе элементов 39. Выход элемента 37 подключен к управляющим входам входных регистров устройства, выход элемента

И 38 подключен к управляющим входам выходных регистров, а выходы группы элементов И 39 соединены с управляю-щими входами мультиплексоров устрой.ства. Занесение аргумента X в регистр

34 происходит по шине 32.

Блок управления работает следующим образом.

В начальный момент времени по шине .

32 заносится значение аргумента ) в регистр 34, а в схему сравнения 40 заносится значение разрядности аргумента, равное Й . После этого по сигналу "Пуск" запускается генератор 33 тактовых импульсов и начинает выра- батывать синхроимпульсы, счетчик. тактов начинает считать импульсы, и как только досчитает до значения Й, срабатывает схема сравнения 40 и от. ключает генератор 33 тактовых импульсов, в то же время по заднему фронту импульса синхросерии в каждом так-. те происходит сдвиг содержимого регистра 34 аргумента влево на один разряд. В зависимости от состояния старшего разряда регистра 34 аргумента управление предлагаемого устройства либо происходит, либо нет, т.е. если старший разряд аргумента равен единице, то блок управления управляет работой входных и выходных регистров и мультиплексоров. В за- висимости от показаний счетчика мультиплексоры производят сдвиг на определенное количество разрядов, если же старший разряд аргумента равен нулю,. то никаких изменений в устройстве не происходит, а работает лишь блок управления. считает импульсы,,производит сдвиг аргумента и выпол1няет сравнение значения счетчика со значением разрядности аргумента Н., ll34947

ВЬе. t

Заказ 1009)/42

- -:6од аваа в

Щ/8. Я

Фиаима 36В-ЧМйеаи" j

Уе 3Ъи Оф4Щ 3мВе .ФмиФВ4ВЭ» 4