Устройство для вычисления полинома @ -й степени Советский патент 1988 года по МПК G06F7/544 

00

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

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

На фиг,I представлена функциональная схема устройства; на фиг. 2 - 5 - роответственно узел выделения значи- разряда, регистр-мультиплексор, г|енератор тактовых импульсов, временные диаграммы.

Устройство для вычиспения полино- йа т-й степени (т 3) содержит реги- с{тры-мультиплексоры 1.1-1.4, мульти- гшексоры 2.Ь - 2.6, сумматоры 3,1 - 3.6, выполненные -как сумматоры-вычи- т атели, входы 4.1 - 4.4 коэффициентов л(олиномов, вход 5 аргумента устройства, вход 6 значения степени полинома, вход 7 запуска устройства, вход 8 за- г|иси устройства, выход 9 готовности . результата устройства, блок 10 управления, регистр 11 аргумента, регист- Е|Ы 12.1 - 12.3, генератор 13 такто- в|ьгх импульсов, счетчик 14, элемент И 5, схему 16 сравнения и узел 17 деления значимого разряда.

Узел 17 вьщеления значимого разряда содержит вычитатель 18, приоритетный шифратор 19, дешифратор 20, с;умматор 21, регистр 22, схему 23 с|равнения и триггер 24.

Вычисленное значение полинома на- йодится в регистре-мультиплексоре 1, Регистр-мультиплексор 1 (фиг.З) с одержит два регистра 25 и 26 и элемент ИЛИ 27, выход которого является в|ыходом регистра-мультиплексора, а выходы соединены с выходами соответствующих регистров 25 и 26, первый Ц второй информационные входы регистра-мультиплексора 1 соединены соответственно с информационными входами первого 25 и в-торого 26 регистров, первьй синхронизирующий вход подключен к синхронизирующему входу первого регистра 25 и к входу установки в О второго регистра 26, второй синхронизирующий вход подключен к синхронизирующему входу второго регистра 26 и входу установки в О первого регистра 25.

Сумматоры, входящие в состав уст- рюйства, являются элементами комбинационного типа. При единичном сигнале на входе режима сумматора он построен на операцию суммирования.

0

5

0

0

5

5

0

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

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

Работа устройства основана на рекурсивном способе вычисления полинома. Вычисление значения полинома, оп- редеденного рекурсивно, является мно- гогааговым процессом, похожим на метод последовательных приближений,так как при вычислении будет отслеживаться разность между исходным и заданным значением аргумента путем положительного или отрицательного наращивания исходного значения аргумента. Это позволяет эффективно применять рекзфсивный метод вычисления значений функции, при небольших рассогла- сованиях аргументов.

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

Разделенные разности функции определяются следующим образом.

Разделенная разность первого по

рядка

-ZitLХ-,

- у;

Разделенная разность k-ro порядка

й г:; -й г

- X

(О

где X; - значение аргумента;

У; - значение функции для Xj.

Из (О следует, что Л { SVi - - (х;.к - х;)-л71 (2)

Подходя формально к уравнению (2) полагая х, а также учитьшая, что для полинома т-й степени разделенные разности т-го порядка постоян3 41

ны, разделенные разности порядка выше m равны нулю, можно определить коэффициенты полинома

Р(«1 . - а., + ...+

+ а,х + Эо

следующим образом:

у„(х„ 0),

к Л

(к1

-к

Сз)

-о

На основании (1,), (3) можно описать рекуррентными соотношениями процедуру определения значения полинома т-й степени.

- ;; fi (-1)

X . тг + t 2 Л1 + ( л, TI .,

У,Ч, у; + ; - vV |xua-,n

. U+i)

(4.2)

. ,lK+i) 1

+f; u , |х;+ц г-т .,(4.3)

де m - степень полинома;

k 1,2,... - порядок раздельной

раяности;

i - номер шага вычислений; Р - номер старшего значимого

разряда двоичного представления величины Z;

Г+ 1, Z 5: О ; Sifen Z; J , . (4.4)

- 1, z; О

+1, при целочисленном

аргументе

- 1, при аргументе

Х (0,1)

при условии хв,п X.,, const

65 Х, U const, 0,

где г - номер младшего значимого разряда .двоичного представления Z;. Начальные условия: Р (Х 0) а, Л ац.

Вычислительный процесс заканчивается через m тактов после появления условия X X;:.

Для упрощения описания работы устройства для вычисления полинома целесообразно установить соответствие между соотношениями (4) и элементами устройства их реализующими.

Выбор значения и определение кодов старшего и младшего значимых разрядов величины Z осуществляется IB узле 17 выделения значимого разряда.. Если , т.е. число на первом входе А схемы 23.сравнения больше числа на ее втором входе В, то на выходе схемы 23 сравнения появляется единичный сигнал, на выходах и - нулевые сигналы.

1

8708

Триггер 24 устанавливается в единичное состояние, на выходе режима узла 17 выделения значимого разряда появляется единичный сигнал.. Если X«ix;,. то триггер 24 устанавливается в нулевое состояние, на выходе режима узла 17 появляется нулевой сигнал.- Если , то единица появляется на

10 выходе блока. 13, состояние выхода режима узла 7 не изменяется.

На выходе вычитателя 18 формируется значение (x-x;(|Z;| , х; - число, записанное в регистре 22.

15 Выделение старшего значимого разряда числа /Z-/ осуществляется в приоритетном шифраторе 19, на выходе которого формируется код этого разряда .

20 На сумматоре 21 осуществ.пяется сложение, если Х х, или вычитание,, если X , числа х , записанного в регистре 22, и числа , где Р - номер старшего значимог о разряда ве25 личины (Z l , Число 2 формируется на выходе дешифратора 20. Таким образом, соотношение (4.1) реализуется с помощью вычитателя 18, соотношение

(4.2)- с помоЕцью приоритетного шиф- 30 ратора 19, дешифратора 20, сумматора

21 и регистра 22, соотношение; (4.4)- с помощью схемы 23 сравнения узла 17 выделения значимого разряда.

.При двоичном представлении чисел, 2g разность x;+kti. соотнощения

.UK

(4.3)MCteHo представить 2

Так как для полинома т-й степени. 40 д,с(кс число слагаемых этой суммы не будет превосходить т. В устройстве числа 2 содержатся в. регистрах 12.1-12.т.

Первое из соотношений (4.3) рва 45 лизуется на нулевом Ярусе устройства, второе из соотношений (4.3) для k 1,2,...,m-l - соответственно на первом, втором,...,(т-1)-м ярусе уст- ,ройства.

50

Так как разность .-x,v, в

соотношениях 4.3 можно представить

Ir IZPi

2l 2 , а значение каждого из слага55

емых этой сумкы содержится в соответствующем регистре 12.1, то операция умножения в (4.3) заменяется на операции сдвига на и суммирования,

причем количество этих операций определяется величиной т-й степенью полинома.

Так в нулевом ярусе устройства реализуется первое из соотношений (4.3)

м Р У,1 Ут ; 1 2 , где у - содержимое

регистра

14187086

фициентов полинома с входов 6.1-6.4 коэффициентов полинома. На выходах сумматоров i-ro -яруса появляется информация о соответствующем коэффициW

первая раздельная рфзностьй - содержимое регистра Ц2. Умножение содержимого регистра 1|2 на 2 производится на мультиплек- сфре 2.,1 путем сдвига на разрядов. этом, если устройство предназнаенте полинома а,.

Поступление данных на вход 5 аргумента устройства сопровождается стробирующим сигналом пуска на входе 10 7 запуска устройства. По сигналу пуска в устройстве осуществл; ется запись значения аргумента в регистр 11 аргумента, установка счетчика 14 в нулевое схэстояние, а также по заднему

чфно для работы с числами, щйми (0,1), то сдвиг информации производится вправо. Если устройство работает с целочисленньми представлениями аргумента, то сдвиг осуществляется влево. Код количества разрядов, 20 на которое необходимо сдвинуть инфор- м4цию, поступает на управляющий, вход мультиплексора 2.1 с выхода регистра lil.

принадлежа- фронту импульсного сигнала пуска производится запуск генератора 13 тактовых импульсов. На выходе 9 готовности результата устройства появляется ну- - левой сигнал.

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

енте полинома а,.

Поступление данных на вход 5 аргумента устройства сопровождается стробирующим сигналом пуска на входе 7 запуска устройства. По сигналу пуска в устройстве осуществл; ется запись значения аргумента в регистр 11 аргумента, установка счетчика 14 в нулевое схэстояние, а также по заднему

Изобретение относится к вычислительной технике и может быть использовано при построении специальных вычислительных машин. Целью изобретения является повышение быстродействия. Сущность изобретения заключается в использовании рекурсивного, метода вы числения значений полинома. Постав-- ленная цель достигается тем, что в устройство, содержащее регистр аргумента, m одновходовых регистров (т - степень полинома), т+1 двухвходовых m(m+l) -2- регистров, m(m 1+1 ) мультиплексоров, сумматоров и блок управления, введен блок выделения значимого разряда, а также организованы новые связи между элементами устройства. Блок вьщеления значимого разряда содержит вычитатель, приоритетный шифратор, дешифратор, сумматор, регистр, схему сравнения и триггер. 2 з.п. ф-лы, 5 ил., 3 табл. S (Л

В первом ярусе устройства реализу- 25 гумента не вьше скорости формировает|ся второе соотношение (4.3) для . Ра-зность-(х- -xi,,m) представ n-l-m+iт г- - +ьмл)+(x;.v

VW-f1

и производятся на

3 и 2.2 соответстл; ется как (х ,

J. )2 Ч2 -л,,.,; т.

. : Таким образом, умножение величины зо (х.,,„ ) осуществляется путем суммирования U , сдвинутой на 2P i ) с U; , сдвинутой На Р;,. Сдвиги Р; мультиплексорах BeJHHo.

В остальных ярусах реализации со- от ветствующих рекуррентных соотношений (6,3) производится подобным образом..

Для полинома т-й степени Л j 0, /i const a поэтому для его вычислений необходимо наличия m ярусов устройства (о, 1,-.,. ,т-1 ярусы).

35

40

ния результата по предьщущему значению.

Так как значение аргумента X не совпадает со значением, содержащимся в регистре 22 узла 17 выделения значимого разряда (исходно регистр 22 в нулевом-состоянии), то нулевым сиг налом с выхода узла 17 элемент И 15 закрыт для прохождения импульсов с генератора 13 на счетчик 14.

Если (исходно ), то еди ничный сигнай с вьгхода узла 17 настраивает сумматоры устройства на режим суммирования. На информационном выходе узла 17 появляется код старшего значимого разряда величины Х-х; согласно табл. 1.

После появления очередного тактового импульса производится запись в регистр 12.3 кода старшего значимого разряда с информационного вьжода узла 17, запись в регистры 12.1 информации с выхода регистра 12.1+1 и запись в регистр-мультиплексор каждого яруса устройства информации с выхода последнего сумматора того, же яруса устройства.

Устройство дпя вычисления полинома т-й степени () работает следуюЩИ14 образом.

В исходном состоянии в регистрах 12.1-12.3 в старшем разряде содержится 1, Б младших - О регистр 22 находится в нулевом состоянии, на выосоде 12 готовности результата - единичный сигнал. На выходах мультиплексоров присутствуют кулевые коды, согласно табл. 3.

По сигналу записи с входа 8 записи устройства в регистры мультиплексоры 1.1-1.4 заносятся значения коэфо

5

0

5

0

5

ния результата по предьщущему значению.

Так как значение аргумента X не совпадает со значением, содержащимся в регистре 22 узла 17 выделения значимого разряда (исходно регистр 22 в нулевом-состоянии), то нулевым сигналом с выхода узла 17 элемент И 15 закрыт для прохождения импульсов с генератора 13 на счетчик 14.

Если (исходно ), то единичный сигнай с вьгхода узла 17 настраивает сумматоры устройства на режим суммирования. На информационном выходе узла 17 появляется код старшего значимого разряда величины Х-х; согласно табл. 1.

После появления очередного тактового импульса производится запись в регистр 12.3 кода старшего значимого разряда с информационного вьжода узла 17, запись в регистры 12.1 информации с выхода регистра 12.1+1 и запись в регистр-мультиплексор каждого яруса устройства информации с выхода последнего сумматора того, же яруса устройства.

После изменения содержимого регистров устройства срабатывают комбинационные схемы-сумматоры 3, мультиплексоры 2, вычитатель 18, приоритетный шифратор 19, дешифратор 20, подготавливая информацию для записи.

в регистры по очередному тактовому импульсу. При этом на выходе узла 17 выделения значимого разряда формируется очередной старший разряд (следующей за разрядом, выделенным на прерыдуя-ем такте работы у 5тройс.тва 5 ; на каждом ярусе устройства осуществляется параллельная реализация рекуррентных соотношений (4.3).

очередного тактового импульса в регистр 22 узла 17 вьщеле- ния значимого разряда записывается число с выхода сумматора 21, совпадающее со значением аргумента X. В этом случае, на выходе вычитателя 18 появляется нулевой код, на выходе схемы 23 сравнения и узла 7 - единичный сигнал..Так как на выходе вьп1итателя 18 нулевой код (табл. 1 и 2) , то нулевой код будет и на втором входе сумматора 21, а следовательно, в последующих тактах работы устройства изменение содержимого сумматора 21 и регистра 22 не происходит.

Единичный сигнал с выхода узла 17 разблокирует элемент 15 И блока 10 управления для прохождения тактовых импульсов с генератора 13 на счетный вход счетчика 14.

При появлении очередного тактового импульса работа устройства осуществляется также, как было описано выше, а кроме того производится подсчет тактовых импульсов на счетчике 14. После появления единичного сигнала на выходе узла 17 формируется единичный сигнал на выходе схемы 16 сравнения блока 10 управления. Этот сигнал поступает на первый управляющий вход генератора 13 тактовых импульсов, останавливая его. Кроме того, этот сигнал поступает на выход 9 готовности результата устройства, свидетельствуя об окончании вычислительного процесса. Вычисленное значение полинома находится в регистре 1 . 1 .

Временная диаграмма работы устройства для случая .приведена на фиг. 5. При сигнал с выхода режима (ОР) узла 17 имеет нулевой уровень.

Перед вычислением значения полинома т-й степени для нового значения аргумента X в регистры 1.1-1.4 заносят- .ся новые коэффициенты полинома ао ,...

а по сигналу со входа о записи устг

ройства. Однако в ряде случаев необходимо вычислять значения полинома т-й степени с одними и теми же коэффициентами для некоторого набора аргументов, являющихся близкими друг к другу числами, т.е. необходимо организовать работу устройства в динамическом режш-ш, для малых приращений аргумента, В этом случае сигнал записи на вход 8 записи устройства не вьщается, запись коэффициентов полинома а; в регистры l.i не производится.

В регистре 1.1 хранится информация о значении полинома для предыдущего значения аргумента, в-регистрах l.i- о значениях разделенных разностей для

предыдущего значения аргумента. В регистре 22 блока выделения значимого разряда содержится предьздущее значение аргумента. После записи в регистр 11. нового значения аргумента X

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

- При значениях X и X близких друг к другу такой режим работы устройства позволяет существенно уменьшить время вычислений значений полинома.

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

40m(m+l)

регистров-мультиплексоров, m(m+)

мультиплексоров.

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

cy tмaтopa-fiычитaтeля 1-го яруса устройства (,.,,i) соединены с первым входом (j+l)-ro сумматора-вычитателя 1-го яруса устройства, второй вход k-ro сумматора-вычитателя каждого яруса устройства соединен с выходом k-ro мультиплексора того же яруса устройства (,.., ,1+1), управля- 1ёщий вход k-ro. мультиплексора 1-го йруса устройства соединен с. управляю- и(им входом (k+l)-ro мультиплексора (i+l)-ro яруса устройства (при i-+tn-l) первые синхровходы всех регистров- мультиплексоров объединены между со- бой, вторые синхровходы регистров- мультиплексоров каждого яруса устройства, кроме последнего, объединены м ежду собой, вход аргумента устройства соединен с входом аргумента бло-jj которого является выходом управления

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

ка управления, отличающееся тем, что, с целью повьшения быстродействия устройства, выход (i+ +l)-ro сумматора-вычитателя i-го яру- ср устройства соединен с вторым ин- 20 фррмационным входом регистра-мульти- пЬексора того же яруса, первые синхро- всех регистров-мультиплексоров соединены с входом сброса блока управ- лЬния и являются входом записи уст- 25 ррйства, входы режима всех суммато- ров-вычитателей объединены и соединены с выходом управления операцией 6JioKa управления, информационные вхо- дь1 мультиплексоров 1-го яруса устрой- Q ства (при ) объединены и соеди- .некы с выходом регистра-мультиплексо- |ра (14-1)-го яруса устройства, инфор- мационные входы мультиплексоров (т- -1)-го яруса устройства объединены и

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

соединены с выходом .(m+l)-ro регистра- схему сравнения и триггер, входы

40

мультиплексора, управляющий вход мультиплексора яруса устройства соединен с (i,- k+2}--M выходом р гжима блока управления, синхровыход блока управления соединен с вторыми синхровходами регистров-мультиплексоров каждого яруса устройства, вход запуска блока управления является входом запуска устройства..е

2„ Устройство по п. 1, отличающееся тем, что блок управления содержит регистр аргумента, у;|ел вьщеления значимого разряда, элемент И, счетчик, схему сравнения, m регистров и генератор импульсов, вход запуска которого является входом запуска блока управления и соединен с входом сброса счетчика и синхронизирующим входом регистра аргумен50

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

информационньй вход которого явля динен с синхронизирующим входом узется входом аргумента блока, выход регистра аргумента соединен с информационным входом узла выделения значи Moi o разряда, вход сброса которого соединен с входом сброса блока, син- хровход узла выделения значимого разряда соединен с синхровходами регистров, вторым входом элемента И, выходом генератора импульсов и с синхро- выходом блока, информационный вход п-го регистра (,...,т-1) соединен с выходом (п+1)-го perHCTiJa, информационный- вход т-го регистра соединен с информационным входом узла выделения значимого разряда, выход режима

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

схему сравнения и триггер, входы

0

е

0

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

111418708

Таблица 1

X - любое

Таблица 2

12

ТаблицаЗ

.15 О

Таблица 4

Фив.Э

Фи9.1

Ф1/г.