Устройство для вычисления полинома @ -й степени
Изобретение относится к вычислительной технике и может быть использовано при построении специальных вычислительных машин. Целью изобретения является повышение быстродействия. Сущность изобретения заключается в использовании рекурсивного, метода вы числения значений полинома. Постав-- ленная цель достигается тем, что в устройство, содержащее регистр аргумента , m одновходовых регистров (т - степень полинома), т+1 двухвходовых m(m+l) -2- регистров, m(m 1+1 ) мультиплексоров, сумматоров и блок управления , введен блок выделения значимого разряда, а также организованы новые связи между элементами устройства. Блок вьщеления значимого разряда содержит вычитатель, приоритетный шифратор , дешифратор, сумматор, регистр, схему сравнения и триггер. 2 з.п. ф-лы, 5 ил., 3 табл. S (Л
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (11) (ю 4 G 06 F 7/544
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А BTOPCHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4174552/24-24 (22) 09.01.87 (46) 23.08.88, Бюл. В 31 (71) Ленинградский электротехнический институт им.В,И.Ульянова(Ленина) (72) А,А.В лов, Л.M.Âèòêèí и Е.П.Угрюмов (53) 681,325 (088.8) (56) Авторское свидетельство СССР
Ó 1 140115, кл. 0 -06 F 7/544, 1985. Авторское свидетельство СССР
У 1134947, кл. 0 06 F 15/31, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИ НОМА m-Й СТЕПЕНИ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специальных ,вычислительных машин. Целью изобретения является повышение быстродействия.
Сущность изобретения заключается в использовании рекурсивного. метода вычисления значений полинома. Постав ленная цель достигается тем, что в устройство, содержащее регистр аргумента, ш одновходовых регистров (m— степень полинома), m+I двухвходовых ш(ш+1) регистров, ††- -- мультиплексоров, m(m +1 ) — — — — — — сумматоров и блок управле2 ния, введен блок выделения значимого разряда, а также организованы новые связи между элементами устройства..
Блок выделения значимого разряда содержит вычитатель, приоритетный шифратор, дешифратор, сумматор, регистр, схему сравнения и триггер. 2 з.п. ф-лы, 5 ил., 3 табл.
1418708
Изобретение относится к вычислительной технике и может быть использовано в специальных вычислительных ашинах.
Цель изобретения — повышение быстродействия устройства.
На фиг.1 представлена функциональная схема устройства; на фиг. 2 — 5— соответственно узел выделения значи- 10 мого разряда, регистр-мультиплексор, генератор тактовых импульсов, временные диаграммы.
Устройство для вычисления полинома ш-й степени (m = 3) содержит реги- !5 бтры-мультиплексоры 1,1-1.4, мультиплексоры 2.1. — 2.6, сумматоры 3.1—
3.6, выполненные как сумматоры-вычи-. татели, входы 4.1 — 4,4 коэффициентов 1олиномов, вход 5 аргумента устройст- 20 ва, вход 6 значения степени полинома, вход 7 запуска устройства, вход 8 заниси устройства, выход 9 готовности . результата устройства, блок 10 управления, регистр 11 аргумента, регистры 12.1 — 12.3, генератор 13 такто-. вых импульсов, счетчик 14, элемент
И 15, схему 16 сравнения и узел 17 ,п(еления значимого разряда.
Узел 17 выделения значимого раэ- 30 ряда содержит вычитатель 18, приоритетный шифратор 19, дешифратор 20, сумматор 21, регистр 22, схему 23 сравнения и триггер 24.
Вычисленное значение полинома наХодится в регистре-мультиплексоре 1.1.
Регистр-мультиплексор 1 (фиг.3) содержит два регистра 25 и 26 и эле( мент ИЛИ 27, выход которого является выходом регистра-мультиплексора, а gp
1 входы соединены с выходами соответствующих регистров 25 и 26, первый 1 второй информационные входы регистра-мультиплексора 1 соединены соответственно с информационными входами первого 25 и второго 26 регистров, первый синхронизирующий вход подключен к синхрониэирующему входу первого регистра 25 и к входу установки в
"0" второго регистра 26, второй синхронизирующий вход подключен к синхрониэирующему входу второго регистра
?6 и входу установки в "0" первого регистра ?5.
Сумматоры, входящие в состав устройства, являются элементами комбинационного типа. При единичном сигнале на входе режима сумматора он построен на операцию суммирования.
При нулевом сигнале на входе режима на операцию вычитания: данные поступающие по второму входу вычитаются из данных, поступающих по первому входу сумматора. Мультиплексоры выполняют функцию сдвига двоичной информации на заданное по управляющему входу число разрядов.
Коды, присутствующие на входах и выходах приоритетного шифратора 19, шифратора 20, а также мультиплексоров, сдвигающих информацию вправо, при работе с нецелочисленными значениями аргумента или сдвигающих информацию влево при работе с целочисленными значениями аргумента, представлены в табл.1-4.
Работа устройства основана на рекурсивном способе вычисления полиноMR Вычисление значения полинома, определенного рекурсивно, является многошаговым процессом, похожим на метод последовательных приближений,так как при вычислении будет отслеживатьФ ся разность между исходным и заданным значением аргумента путем положительного или отрицательного наращивания исходного значения аргумента.
Это позволяет эффективно применять . рекурсивный метод вычисления значений функции, при небольших рассогласованиях аргументов.
Работа предлагаемого устройства заключается в вычислении по рекуррентным соотношениям последующего значения полинома ш-й степени для заданного аргумента, если известны значение полинома и разделенные разности для предыдущего значения аргумента.Разделенные разности функции определяются следующим образом.
Разделенная разность первого порядка ( Ь; х„+, -х; Разделенная разность k-го порядка 1 (в-il (к-i) (К1 i+i < (1) У X lii где х, — значение аргумента; у; — значение функции для х Из (1) следует, что Ь " = Ь „ — (х; к — х, ) Ь;". (2) Подходя формально к уравнении (2) полагая х; с 0 = x, а также учитывая, что для полинома m-й степени разделенные разности m-го порядка постоян141 ны, разделенные разности порядка выше m равны нулю, можно определить коэффициенты полинома м м-1 P<1= a x + a, х + ... + +ах+а„ следующим образом: a = у,(х„ = О), a„ = 6 „. (3) На основании (1,), (3) можно описать рекуррентными соотношениями процедуру определения значения полинома m-й степени. Z; = X — х,; ° (4.1) х, +, = х, + (; 2 и у 4i у1 + Ь ; 1Х1+ — х,, (4, 2) (x) (к) 1к+0 i Ь q +(j 1 хj+g+2 m .х;,, (., (4 3) где m k степень полинома; 1,2,... — порядок раздельной разности; номер mara вычислений; номер старшего значимого разряда двоичного представления величины Е; + 11 Z1 -" 0 (;= sig z; (4.4) 1,Z (0 + 1, при целочисленном аргументе 1, при аргументе Хб, при условии х )co = х х g p 1к)м = 1к1 м У Э У где r — номер младшего значимого разряда . двоичного представления Z; Начальные условия: P (Х. = О) = ау, (к) = а„. Вычислительный процесс заканчивается через ш тактов после появления условия Х х 4Ф Для упрощения . описания работы устройства для вычисления палинома целесообразно установить соответствие между соотношениями (4) и элементами устройства их реализующими. Выбор значения ; и определение кодов старшего и младшего значимых разрядов величины Е; осуществляется в узле 17 выделения значимого разряда., Если Х> х;, т.е. число на первом входе А схемы 23. сравнения больше числа на ее втором входе В, то на выходе схемы 23 сравнения появляется единичный сигнал, на выходах (" и — нулевые сигналы. 8708 Триггер 24 устанавливается в единичное состояние, на выходе режима узла 17 выделения значимого разряда появляется единичный сигнал, Если Хе.х;, то триггер 24 устанавливается в нулевое состояние, на выходе режима узла 17 появляется нулевой сигнал, Если Х=х, то единица появляется на выходе "=" блока 13, состояние выхода режима узла 7 не изменяется. На выходе вычитателя 18 формируется значение (X-х;(=(Z;(, х, — число, записанное в регистре 22. 15 Выделение старшего значимого разряда числа IZ;(осуществляется в приоритетном шифра-.оре 19, на выходе которого формируется код этого разряда. 20 На сумматоре 21 осуществляется сложение, если Х. х„ или вычитание. если Х х, числа х, записанного в Э регистре 22, и числа 2, где Р, номер старшего значимого разряда веtr, Р личины (Z; ) . Число 2 формируется на выходе дешифратора 20, Таким образом, соотношение (4.1) реализуется с помощью вычитателя 18 соотношение (4.2) — с помощью приоритетного шиф30 ратора 19, дешифратора 20, сумматора 21 и регистра 22, соотношение. (4.4)с помощью схемы 23 сравнения узла 17 выделения значимого разряда. При двоичном представлении чисел, разность х;,q,1 -х„„ соотношения к (4.3) мсйкно представить 2 ,1. )=1 Так как для полинома m-й степени. 40 k„ „ñ=ùý то число слагаемых этой суммы не будет превосходить m. В устройстве числа 2 содержатся в регистрах 12.1-12.m, Первое из соотношений (4,3) реа45 лизуется на нулевом stpyce устройства, второе из соотношений (4.3) для k= .=1,2...,,m-1 — соответственно на первом, втором,...,(m-1)-м ярусе уст,ройства. Так как разность х1,м,г-х;.1 „ в оотношениях 4.3 можно йредставить )+к ,7 2, а значение каждого из слага= 55 емых этой суммы содержится в соответствующем регистре 12.i, то операция умножения в (4.3) заменяется íà onenp ° рации сдвига:«a 2 и суммирования, 1418708 причем количество этих операций определяется величиной m-й степенью полинома. Так в нулевом ярусе устройства ре5 ализуется первое из соотношений (4,3) (б) < Pl у,„=у; +(; 6, 2, где у — содержимое регистра 1.1, первая раздельная (11 разность h, — содержимое регистра 1 2. Умножение содержимого регистра 1,2 на 2 производится на мультиплекГ Г Р соре 2.,1 путем сдвига íà P,, разрядон. При этом, если устройство предназна-. ч Ено для ра бо ты с числами, принадлежа-1 5 щйми (0,1), то сдвиг информации производится вправо. Если устройство работает с целочисленными представлениями аргумента, то сдвиг осуществляется влево, Код количества разрядов, 20 на которое необходимо сдвинуть информацию, поступает на управляющий. вход мультиплексора 2.1 с выхода регистра 12.1. В первом ярусе устройства реализу- 25 ется второе соотношение (4.3) для 1с= 1. Разность (х;„, -х„„„,„) представ) =2 " +2. Таким образом, умножение величины 30 й; на (х „ -х;„,„) осуществляется (Ф1 путем суммирования Ь;, сдвинутой на Р,, с 6,, сдвинутой на Р;„. Сдвиги 6, на Р; и Р;, производятся на П) мультиплексорах 2.3 и 2,2 соответств е нно. В остальных ярусах реализации соотнетствующих рекуррентных соотношений (6.3) произнодится подобным образом. 1 + ) 40 Для полинома m-й степени Ь =О, Ж -А =const=a поэтому для его вычисле3 Ill ) ния необходимо наличия m ярусов устройства (О,l,...,m-l ярусы). Устройство для вычисления полинома m-й степени (m=3) работает следую-, щим образом. B исходном состоянии в регистрах )2,1-12.3 н старшем разряде содержится "1", в младших — "0" регистр 22 находится в нулевом состоянии, на выходе 12 готовности результата— единичный сигнал. На выходах мультиплексоров присутствуют нулевые коды, согласно табл. 3. По сигналу записи с входа 8 записи устройства в регистры мультиплексоры l.l-l.4 заносятся значения коэффициентон полинома с входов 6.1-6.4 коэффициентов полинома. На выходах сумматоров i-ro .яруса появляется информация о соответствующем коэффициенте полинома а Поступление данных на вход 5 аргумента устройства сопровождается стробирующим сигналом пуска на входе 7 запуска устройства. По сигналу пуска в устройстве осуществляется запись значения аргумента в регистр 11 ар" гумента, установка счетчика 14 в нулевое состояние, а также по заднему фронту импульсного сигнала пуска производится запуск генератора 13 тактовых импульсов. На выходе 9 готовности результата устройства появляется ну- левой сигнал. При такой дисциплине запуска дина- . мическая погрешность ныполнения вычислительных операций вычисления значений полинома равна нулю, если скорость поступления новых значений аргумента не выше скорости формирования результата по предыдущему значению б Так как значение аргумента Х не совпадает со значением, содержащимся в регистре 22 узла 17 выделения значимого разряда (исходно регистр 22 в нулевом состоянии), то нулевым сигналом с выхода "=" узла 17 элемент И 15 закрыт для прохождения импульсов с генератора 13 на счетчик 14. Если X > х, (исходно х,=О), то единичный сигнал с выхода " ) " узла 17 настраивает сумматоры устройства на режим суммирования. На информационном выходе узла 17 появляется код старшего значимого разряда величины Х-х; согласно табл. 1. После появления очередного тактоаого импульса производится запись в регистр 12.3 кода старшего значимого разряда с информационного выхода узла 17, запись в регистры 12,i информации с выхода регистра 12.i+1 и запись в регистр-мультиплексор каждого яруса устройства информации с выхода последнего сумматора того же яруса устройства. После изменения содержимого регистров устройства срабатывают комбинационные схемы-сумматоры 3, мультиплексоры 2, вычитатель 18> приоритетный шифратор 19, дешифратор 20, подготавливая информацию для записи 14!8708 8 а ло сигналу со входа 8 записи устм ройства. Однако в ряде случаев необходимо вычислять значения полинома m-й степени с одними и теми же коэффициентами для некоторого набора аргументов, являющихся близкими ppYt к другу числами, т,е. необходимо организовать работу устройства в динамическом режиме, для малых приращений аргумента. В этом случае сигнал записи на вход 8 записи устройства не выдается, запись коэффициентов полинома а, в регистры 1.i не производится. В регистре 1.1 хранится информация о значении полинома для предыдущего значения аргумента, в регистрах 1,io значениях разделенных разностей для предыдущего значения аргумента. В регистре 22 блока выделения значимого разряда содержится предыдущее значение аргумента. После записи в реI гистр 11 нового значения аргумента Х и запуска устройства по входу 7 пуска устройства устройство будет функционировать также, как было рассмот,рено выше за исключением того, что узел 17 выделяет на каждом такте работы устройства. старший значимый разряд не числа Х,, а числа Е=X -Х. 1 При значениях Х и Х близких друг к другу такой режим работы устройства позволяет существенно уменьшить время вычислений значений полинома. в регистры по очередному тактовому импульсу. При этом на выходе узла 17 выделения значимого разряда формируется очередной старший разряд (сле5 дующей за разрядом, выделенным на прерыду) ем такте работы устройства ); на каждом ярусе устройства осуществляется параллельная реализация рекуррентных соотношений (4.3). После очередного тактового импульса в регистр 22 узла 17 выделения значимого разряда записывается число с выхода сумматора 21, совпадающее со значением аргумента Х. В 15 этом случае, на выходе вычитателя 18 появляется нулевой код, на выходе — схемы 23 сравнения и узла 7 единичный сигнал..Так как на выходе вычитателя 18 нулевой код (табл, 1 20 и 2), то нулевой код будет и на втором входе сумматора 21, а следовательно, в последующих тактах работы устройства изменение содержимого сумматора 21 и регистра 22 не происхо.дит. Единичный сигнал с выхода "=" узла 17 разблокирует элемент 15 И блока !0 управления для прохождения так- 30 товых импульсов с генератора 13 на счетный вход счетчика 14. При появлении очередного тактового импульса работа устройства осуществляется также, как было описано вьппе, а кроме того производится подсчет тактовых импульсов на счетчике 14. После появления единичного сигнала на выходе "=" узла 17 формируется единичный сигнал на выходе схемы 40 1.6 сравнения блока 10 управления. Этот сигнал поступает на первый управляющий вход генератора 13 тактовых импульсов, останавливая его. КроФ ме того, этот сигнал поступает на выход 9 готовности результата устройства, свидетельствуя об окончании вычислительного процесса. Вычисленное значение полинома находится в регистре 1.1, 50 Временная диаграмма работы устрой- ° ства для случая Х > Х„,„.приведена на фиг, 5. При Х Х„,„сигнал с выхода режима (ОР} узла 17 имеет нулевой уровень. Перед вычислением значения полинома m-й степени для нового значения аргумента Х в регистры 1,1-1.4 заносятся новые коэффициенты лолинома а Формула изобретения 1. Устройство для вычисления полинома m-й степени„ содержащее ш+1 m(m+1) регистров-мультиплексоров, ш(ш+1) 2 мультиплексоров, ††-- сумматоров2 вычитателей и блок управления, первые информационные входы регистровмультиплексоров являются входами коэффициентов полинома устройства, каждый i-й ярус устройства (i†= m-1) содержит регистр-мультиплексор,,i+1) сумматоров-вычитателей, (i+1) мультиплексоров, в каждом ярусе устройства выходы регистра-мультиплексора соединены с первыми входами первого сумматора-вычитателя, выходы i-го сумматора-вычитателя i-ro яруса устройства ()=1...,i) cnединены с перBblM входом ()+1)-го сумматора-вычитателя i-го яруса устройства, второй 1 вход k-го сумматора-вычитателя каждо1418708 i0 го яруса устройства соединен с выходом k-го мультиплексора того же яруса устройства (k=1 °,1+1), управляющий вход k-го, мультиплексора i-го 5 яруса устройства соединен с управляющим входом (k+1)-го мультиплексора (i+1)-ro яруса устройства (при i+m-l), первые синхровходы всех регистровмультиплексоров объединены между собой, вторые синхровходы регистровмультиплексоров каждого яруса устройства, кроме последнего, объединены между собой, вход аргумента устройства соединен с входом аргумента бло- 15 ка управления, о т л и ч а è щ ее с я тем, что, с целью повышения бЫстродействия устройства, выход (i+ +I)-ro сумматора-вычитателя i-ro яруса устройства соединен с вторым ин- 20 формационным входом регистра=мультиппексора того же яруса, первые синхровкоды всех регистров-мультиплексоров срединены с входом сброса блока управления и являются входом записи устрОйства, входы режима всех сумматоров-вычитателей объединены и соединены с выходом управления операцией блока управления, информационные входы мультиплексоров i-го яруса устрой- З0 ства (при i+-1) объединены и соединены с выходом регистра-мультиплексо,ра (i+I)-го яруса устройства, информационные входы мультиплексоров (m-1)-ro яруса устройства объединены и соединены с выходом .(m+1)-ro регистрамультиплексора, управляющий вход i-го мультиплексора Р-го яруса устройства соединен с (i-k+2)-м выходом режима блока управления, синхровыход 40 блока управления соединен с вторыми синхровходами регистров-мультиплексоров каждого яруса устройства, вход запуска блока управления является входом запуска устройства. 2, Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что блок управления содержит регистр аргумента, узел выделения значимого разряда, элемент И, счетчик, схему сравнения, m регистров и генератор импульсов, 50 вход запуска которого является входсм запуска блока управления и соединен с входом сброса счетчика и синхронизирующим входом регистра аргумента, информационный вход которого явля ется входом аргумента блока, выход регистра аргумента соединен с информационным входом узла выделения значимого разряда, вход сброса которого соединен с входом сброса блока, синхровход узла выделения значимого разг ряда соединен с синхровходами регистров, вторым входом элемента И, выходом генератора импульсов и с синхровыходом блока, информационный вход и-го регистра (n=l,...,m-l) соединен с выходом (n+1)-ro регистра, информа-. ционный вход m-ro регистра соединен с информационным входом узла выделения значимого резряда, выход режима которого является выходом управления операцией блока, выход равенства уз ла выделения значимого разряда соединен с первым входом элемента И, выход которого соединен со счетным входом счетчика, выход которого соединен с вторым входом схемы сравнения, первый вход которой является входом значения блока, выход схемы сравнения соединен с входом останова генератора импульсов и выходом готовности блока, выходы с первого по ш-й регистров соединены с первого по m-й выходами задания режима блока соот" ветственно. 3. Устройство по п. 2, о т л ич а ю щ е е с я тем, что узел выде-! ления значимого разряда содержит вычитатель, приоритетный шифратор, дешифратор сумматор-вычитатель, регистр, схему сравнения и триггер, входы сброса установки которого соединены с выходами "Меньше" и "Больше" схемы сравнения соответственно, выход "Равно" которой является выходом "Равно" узла, первый вход суммы сравнения соединен с информационным входом узла и .первым входом вычитателя, а второй вход соединен с вторым входом вычитателя, первым входом сумматора и выходом регистра, выход вычитателя соединен через приоритетный . шифратор с входом дешифратора и информационным выходом узла, второй вход сумматора соединен с выходом дешифратора, вход режима сумматора соединен с прямым выходом триггера и выходом режима узла, выход соединен с информационным входом регистра, синхронизирующий вход которого соединен с синхронизирующим входом узла, вход установки в "0" соединен с входом установки в "0" узла. В 5 ходы управл. Выходь Входы D5 D4 Выходы Ц2 ф! ЦО СЗ Р2 Dl Рб Ц4 ЦЗ Q2 Q1 СО С2 О О ° Х Х Х Х D4 D3 D0 Р2 Dl D3 D2 Р4 DÇ Рб D7 Х Х Х Х Р5 Р4 Рб D5 D7 Рб О D7 D7 -О 1 Х Р7 1 О О К Х Х Х Х О О О 1 О О 1 Р5 Р4 О 1 О О Х Х Рб D5 Р7 Рб О D7 О О О 1 О О 1 Х Р5 О О О 1 20 О О О 25 1 О О О 1 О О.О Рб О О. О 0 О О О О О О О О О 0 О О О О Х вЂ” любое Входы управл. Выходы Входь Выходы -Ч D2 Q5 Q4 Q1 Q0 Q3 Q2 Q4 ЯЗ СЗ С2 О 1 О О О О О D2 DI D4 D3 О 1 D3 D2 О О D1 D О О О 1 1 О D0 О Р2 Dl О 1 0 1 О О D1 DO О О О О О О О О DO. О О 0 О О О О О О О О 0 О О О О О О О О О О О О О О О О О 1.О О О О О О О О О D1 DO Q7 Яб 1 1 1 О 1 О О 1 О 1 О О О О О О 1 1 О О 1 О О О О 1 О О О О О 0 О О 0 О 1418708 Таблица ! Т а блица 2 О О 40 О О О 50 1 СО Qj Qá Q5 О Dj Dá Р5 l Рб D5 D4 О D5 D4 DÇ 1 D4 DÇ Р2 О РЗ D2 Dl 1 D2 Dl DO О Dl DO O 1 DO 0 О О О О О Та блица 3 Таблица4 1418708 1418708 1418708 Ь В у, Ъй ь в ь ы Ю О 3 су 4 44 С4 Составитель А.Богословских Редактор Г.Волкова Техред И.Верес Корректор М.Демчик Заказ 4154/46 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, r, Ужгород, ул. Проектная, 4
