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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 4 С 06 Г 7/5 ПИСАНИЕ ИЗОБРЕТЕНИ ЯКИ у." т% 1. да вытаво в вного.мет инома. 11 о ся тем, ч е регистр аргув (ш регистр 1 двухвх довых ультиплексоро лок управлея значимого ваны новые тройства;разряда сотетный шиф- Я ор, регистр,2 в,п. Я ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ К А ВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Ленинградский электротехнический институт им,В,И.Ульянова(Ленина) (72) А,А.Влов, Л.М.Виткин и Е.П.Угрюмов(56) Авторское свидетельство СССР У 1140115, кл. С 06 Р 7/544, 1985.Авторское свидетельство СССР У 1134947, кл. О 06 Р 15/31, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИ-НОМА ш-Й СТЕПЕНИ(57) Изобретение относится к вычислительной технике и может быть использовано при построении специальных ,вычислительных машин. Целью изобретения является повышение быстродействия ность изобретения заключае использовании рекурсчисления значений поленная цель достигаеустройство, содержащмента, ш одновходовыстепень полинома), шш(ш+1)регистров2ш(ш +1 )- - ---- сумматоро2 ния, введен блок выделен разряда, а также организ связи между элементами у Блок выделения значимого держит вычитатель, приор ратор, дешиФратор, сумма схему сравнения и тригге ф-лы, 5 ил., 3 табл.1418708 фЬ В у, фЪВ ф 3 Ь фЬФ 4 В Щю Щ 1 О фФфэ Составитель А.БогословскихВолкова, Техред И.Верес Коррект Редакт емчик 54/4 к Производственно-полиграфическое предприятие од, ул. Проектная,Тираж 704 ВНИИПИ Государственного по делам изобретений 3035, Москва, Ж, РаущИзобретение относится к вычислительной технике и может быть использовано в специальных вычислительныхашинах.5Цель изобретения - повышение быстродействия устройства.На фиг,1 представлена функциональная схема устройства; на фиг, 2 - 5 -соответственно узел выделения значимого разряда, регистр-мультиплексор,генератор тактовых импульсов, временные диаграммы.Устройство для вычисления полинома ш-й степени (ш = 3) содержит регибтры-мультиплексоры 1,1-1.4, мультиплексоры 2,1. - 2,6, сумматоры 3.1 -3.6, выполненные как сумматоры-вычи-.татели, входы 4,1 - 4,4 коэффициентов1 олиномов, вход 5 аргумента устройства, вход б значения степени полинома,вход 7 запуска устройства, вход 8 заиси устройства, выход 9 готовности .результата устройства, блок 10 управления, регистр 11 аргумента, регистры 12,1 - 12,3, генератор 13 тактовых импульсов, счетчик 14, элементИ 15, схему 16 сравнения и узел 17деления значимого разряда.Узел 17 выделения значимого раэ- ЗОряда содержит вычитатель 18, приоритетный шифратор 19, дешифратор 20,сумматор 21, регистр 22, схему 23сравнения и триггер 24,Вычисленное значение полинома наХодится в регистре-мультиплексоре 1,1,Регистр-мультиплексор 1 (фиг.З)содержит два регистра 25 и 26 и элемент ИЛИ 27, выход которого являетсявыходом регистра-мультиплексора, авходы соединены с выходами соответствующих регистров 25 и 26, первыйИ второй информационные входы регистра-мультиплексора 1 соединены соответственно с информационными входами 45первого 25 и второго 26 регистров,первый синхронизирующий вход подключен к синхрониэирующему входу первого регистра 25 и к входу установки в"0" второго регистра 26, второй синхронизирующий вход подключен к синхрониэирующему входу второго регистра26 и входу установки в "0 первогорегистра 25,Сумматоры, входящие в состав устройства, являются элементами комбинационного типа, При единичном сигнале на входе режима сумматора онпостроен на операцию суммирования,При нулевом сигнале на входе режимана операцию вычитания: данные поступающие по второму входу вычитаютсяиз данных, поступающих по первомувходу сумматора. Мультиплексоры выполняют функцию сдвига двоичной информации на заданное по управляющемувходу число разрядов.Коды, присутствующие на входах ивыходах приоритетного шифратора 19,шифратора 20, а также мультиплексоров, сдвигающих информацию вправо,при работе с нецелочисленными значениями аргумента или сдвигающих информацию влево при работе с целочисленными значениями аргумента, представлены в табл,1-4,Работа устройства основана на рекурсивном способе вычисления полинома. Вычисление значения полинома, определенного рекурсивно, является многошаговым процессом, похожим на метод последовательных приближений,таккак при вычислении будет отслеживаться разность между исходным и заданным значением аргумента путем положительного или отрицательного наращивания исходного значения аргумента.Это позволяет эффективно применять .рекурсивный метод вычисления значений функции, при небольших рассогласованиях аргументов.Работа предлагаемого устройствазаключается в вычислении по рекуррентным соотношениям последующегозначения полинома ш-й степени длязаданного аргумента, если известнызначение полинома и разделенные разности для предыдущего значения аргумента.Разделенные разности функции определяются следующим образом,Разделенная разность первого порядкаР) У+ УЬ;х+, -х;Разделенная разность 1 с-го порядка1(к(к-)(к 1+Ь (1)х - хгде х, - значение аргумента;у, - значение функции для х;.Из (1) следует, что Ь 1"= Ь;"+(х;,к - х,) Ь,. (2)Подходя формально к уравнении (2) полагая х; с 0 = х , а также учитывая, что для полинома ш-й степени разделенные разности ш-го порядка постоян141ны, разделенные разности порядка выше ш равны нулю, можно определить коэффициенты полиномам м Р,=ах+а,х+ а,х + аоследующим образом:а, = у,(х = О), а = Ь . (3)На основании (1,), (3) можно описать рекуррентными соотношениями процедуру определения значения полинома ш-й степени.Е, = Х - х . (4.1)х+, =х;+ ;2йу 1. = у + Ь ; 1 х 1+2-м- х; (4, 2)(4,3) где ш степень полинома;1,2, - порядок раздельной разности;номер шага вычислений; номер старшего значимого разряда двоичного представления величины Е;+ 1, при целочисленномаргументе1, при аргументеХ, (0,1) при ус.ловии х о со х о э х я1.Ь 1"1 = 0хэР Угде г - номер младшего значимого разряда . двоичного представления Е;,Начальные условия: Р (Х = О) = ау,1 к)= а.Вычислительный процесс заканчивается через ш тактов после появленияусловия Х х",ФДля упрощения . описания работыустройства для вычисления палиномацелесообразно установить соответствие между соотношениями (4) и элементами устройства их реализующими.Выбор значения , и определениекодов старшего и младшего значимыхразрядов величины Е; осуществляетсяв узле 17 выделения значимого разряда.,Если Хъ х;, т.е. число на первом входе А схемы 23. сравнения больше числа на ее втором входе В, то на выходесхемы 23 сравнения появляетсяединичный сигнал, на выходах (" и- нулевые сигналы,8708Триггер 24 устанавливается в единичное состояние, на выходе режимаузла 17 выделения значимого разрядапоявляется единичный сигнал, Если5Хх;, то триггер 24 устанавливаетсяв нулевое состояние, на выходе режима узла 17 появляется нулевой сигнал,Если Х=х , то единица появляется навыходе "=" блока 13, состояние выходарежима узла 7 не изменяется.На выходе вычитателя 18 формируется значение 1 Х-х;( =(Е;(, х; - число,записанное в регистре 22,15 Выделение старшего значимого разряда числа (Е;( осуществляется в приоритетном шифраторе 19, на выходекоторого Формируется код этого разряда.20 На сумматоре 21 осуществляетсясложение, если Х. х или вычитание,если Х( х, числа х , записанного в)регистре 22, и числа 2 р где Рномер старшего значимого разряда ве 25 личины Е, . Число 2Формируетсяна выходе дешифратора 20, Таким образом, соотношение (4,1) реализуетсяс помощью вычитателя 18 соотношение(4,2) - с помощью приоритетного шиф 30 ратора 19, дешифратора 20, сумматора21 и регистра 22, соотношение, (4,4)- с помощью схемы 23 сравнения узла17 выделения значимого разряда.При двоичном представлении чисел,разность х;. -х соотношения1+к)=1Так как для полинома ш-й степени.40 1;-ш, то число слагаемых этой суммы не будет превосходить ш. В устройстве числа 2 содержатся в регистрах12.1-12.ш,Первое из соотношений (4,3) реа"45 лизуется на нулевом ярусе устройства,второе из соотношений (4.3) для к=, 2 , а значение каждого из слага=55емых этой суммы содержится в соответствующем регистре 12. то операцияумножения в (4.3) заменяется на опепррации сдвига на 2и суммирования, 1418708причем количество этих операций определяется величиной ш-й степенью полинома.Так в нулевом ярусе устройства ре 5ализуется первое из соотношений (4,3)1 а 1Рзу =у; +; Ь; 2, где у - содержимоерегистра 1,1, первая раздельная(1разность Ь , - содержимое регистра12 . Умножение содержимого регистра1 , 2 на 2производится на мультипл ексоре 2 .,1 путем сдвига на Р разрядов .При этом , если устройство предназ на-.чЕно для рабо ты с числами, и ринадлежа5щйми ( О ,) , то сдвиг информации производится вправ о . Если устройствоработает с целочисленными пр едставл ениями аргумента , то сдвиг о сущес твляется влево , Код количества разрядов , 20на которое необходимо сдвинуть информацию , поступает на управляющий. входм 1 ль типлексора 2 . 1 с выхода регистра1 2, 1 ,В первом ярусе устройства реализует ся второе соотношение ( 4 , 3 ) дляЫ . Разно сть( х;, -х, ) представ) = 2 " + 2 .Таким образом , умножение величиный ; на ( х-х;+, , ) осуществляетсяФ)(опутем суммирования Ь сдвинутой наР с Ь сдвинутой на Р;, Сдвиги 6, на Р; и Р;, производятся на)мультиплексорах 2.3 и 2,2 соответственно.В остальных ярусах реализации соответствующих рекуррентных соотношений (6.3) производится подобным образом.1+1 40Для полинома ш-й степени Ь: =О,ЖА =сопят=а поэтому для его вычисле 5 Ъз )ния необходимо наличия ш ярусов устройства (0,1шярусы).45Устройство для вычисления полинома ш-й степени (к=3) работает следую", щнм образом.В исходном состоянии в регистрах 12.1-12.3 в старшем разряде содержится "1", в младших - "0" регистр 22 находится в нулевом состоянии, на выходе 12 готовности результата - единичный сигнал, На выходах мультиплексоров присутствуют нулевые коды, согласно табл. 3.По сигналу записи с входа 8 записи устройства в регистры мультиплексоры 1.1-1,4 заносятся значения коэфФициентов полинома с входов 6,1-6,4 коэффициентов полинома. На выходах сумматоров -го .яруса появляется информация о соответствующем коэффициенте полинома аПоступление данных на вход 5 аргумента устройства сопровождается стробирующим сигналом пуска на входе 7 запуска устройства, По сигналу пуска в устройстве осуществляется запись значения аргумента в регистр 11 ар" гумента, установка счетчика 14 в нулевое состояние, а также по заднему фронту импульсного сигнала пуска производится запуск генератора 13 тактовых импульсов. На выходе 9 готовности результата устройства появляется ну-левой сигнал.При такой дисциплине запуска динамическая погрешность выполнения вычислительных операций вычисления значений полинома равна нулю, если скорость поступления новых значений аргумента не выше скорости Формирования результата по предыдущему значе- ниюе Так как значение аргумента Х несовпадает со значением, содержащимсяв регистре 22 узла 17 выделения значимого разряда (исходно регистр 22в нулевом состоянии), то нулевым сигналом с выхода "=" узла 17 элементИ 15 закрыт для прохождения импульсов с генератора 13 на счетчик 14.Если Хх, (исходно х,=0), то единичный сигнал с выхода " ) " узла 17настраивает сумматоры устройства нарежим суммирования. На информационном выходе узла 17 появляется кодстаршего значимого разряда величиныХ-х; согласно табл. 1,После появления очередного тактового импульса производится запись врегистр 12.3 кода старшего значимогоразряда с информационного выхода узла 17, запись в регистры 12, информации с выхода регистра 12.х+1 и запись в регистр-мультиплексор каждогояруса устройства информации с выхода последнего сумматора того же яруса устройства.После изменения содержимого регистров устройства срабатывают комбинационные схемы-сумматоры 3, мультиплексоры 2, вычитатель 18, приоритетный шифратор 19, дешифратор 20,подготавливая информацию для записи148708 8а ло сигналу со входа 8 записи устмройства. Однако в ряде случаев необходимо вычислять значения полиномат-й степени с одними и теми же коэфФициентами для некоторого набора аргументов, являющихся близкими другк другу числами, т,е, необходимо организовать работу устройства в динамическом режиме, для малых приращений аргумента. В этом случае сигналзаписи на вход 8 записи устройства невыдается, запись коэффициентов полинома а, в регистры 1, не производится,В регистре 1.1 хранится информацияо значении полинома для предыдущегозначения аргумента, в регистрах 1,хо значениях разделенных разностей дляпредыдущего значения аргумента, Врегистре 22 блока выделения значимого разряда содержится предыдущее значение аргумента, После записи в регистр 11 нового значения аргумента Хи запуска устройства по входу 7 пуска устройства устройство будет функционировать также, как было рассмот,рено выше за исключением того, чтоузел 17 выделяет на каждом такте работы устройства старший значимый разряд не числа Х а числа Е=Х -Х.11При значениях Х и Х близких другк другу такой режим работы устройства позволяет существенно уменьшитьвремя вычислений значений полинома. в регистры по очередному тактовому импульсу. При этом на выходе узла 17 выделения значимого разряда Формируется очередной старший разряд (сле 5 дующей за разрядом, выделенным на прерыдушем такте работы устройства); на каждом ярусе устройства осуществляется параллельная реализация рекуррентных соотношений (4,3).10После очередного тактового импульса в регистр 22 узла 17 выделения значимого разряда записывается число с выхода сумматора 21, совпадающее со значением аргумента Х. В 15 этом случае, на выходе вычитателя 18 появляется нулевой код, на выходе - схемы 23 сравнения и узла 7 единичный сигналТак как на выходе вычитателя 18 нулевой код (табл, 1 20 и 2), то нулевой код будет и на втором входе сумматора 21, а следовательно, в последующих тактах работы устройства изменение содержимого сумматора 21 и регистра 22 не происхо .дит. Единичный сигнал с выхода "=" узла 17 разблокирует элемент 15 И блока 10 управления для прохождения тактовых импульсов с генератора 13 насчетный вход счетчика 14,При появлении очередного тактового импульса работа устройства осуществляется также, как было описановьппе, а кроме того производится подсчет тактовых импульсов на счетчике14. После появления единичного сигнала на выходе "=" узла 17 формируется единичный сигнал на выходе схемы 401.6 сравнения блока 10 управления.Этот сигнал поступает на первый управляющий вход генератора 13 тактовых импульсов, останавливая его, Кроме того, этот сигнал поступает на выход 9 готовности результата устройства, свидетельствуя об окончаниивычислительного процесса. Вычисленноезначение полинома находится в регистре 1,1,50Временная диаграмма работы устройства для случая Х 1Хприведена на Фиг, 5. При Х ( Х, сигнал свыхода режима (ОР) узла 17 имеет нулевой уровень.Перед вычислением значения полинома ш-й степени для нового значения аргумента Х в регистры 1,1-1,4 заносятся новые коэффициенты лолинома а Формула изобретения 1, Устройство для вычисления полинома ш-й степени содержащее ш+1ш(ш+1) регистров-мультиплексоров,ш(тп+1)ф 2 мультиплексоров, в всумматоров 2вычитателей и блок управления, первые информационные входы регистров- мультиплексоров являются входами коэффициентов полинома устройства, каждый .-й ярус устройства (3.=0 ш) содержит регистр-мультиплексор, (+1) сумматоров-вычитателей, (+1) мультиплексоров, в каждом ярусе устройства выходы регистра-мультиплексора соединены с первыми входами первого сумматора-вычитателя, выходы -го сумматора-вычитателя -го яруса устройства (=1,) соединены с первым входом +1)-го сумматора-вычитателя -го яруса устройства, второй 1вход 1-го сумматора-вычитателя каждо 1418708 10го яруса устройства соединен с выходом К-го мультиплексора того же яруса устройства (К=1,,+1), управляющий вход К-го, мультиплексора -го яруса устройства соединен с управляю 5 щим входом (К+1)-го мультиплексора (+1)-го яруса устройства (при 1+в), первые синхровходы всех регистров- мультиплексоров объединены между собой, вторые синхровходы регистров- мультиплексоров каждого яруса устройства, кроме последнего, объединены между собой, вход аргумента устройства соединен с входом аргумента бло15 ка управления, о т л и ч а ю щ е - е с я тем, что, с целью повышения бЫстродействия устройства, выход (1+ +1)-го сумматора-вьгчитателя -го яруса устройства соединен с вторым ин О формационным входом регистра-мультиппексора того же яруса, первые синхровкоды всех регистров-мультиплексоров срединены с входом сброса блока управления и являются входом записи уст рОйства, входы режима всех сумматоров-вычитателей объединены и соединены с выходом управления операцией блока управления, информационные входы мультиплексоров -го яруса устрой- ЗО ства (при /и) объединены и соединены с выходом регистра-мультиплексо;ра (+1)-го яруса устройства, информационные входы мультиплексоров (ш- -1)-го яруса устройства объединены и соединены с выходом .(ш+1)-го регистра- мультиплексора, управляющий вход -го мультиплексора У-го яруса устройства соединен с (-К+2)-м выходом режима блока управления, синхровыход 4 О блока управления соединен с вторыми синхровходами регистров-мультиплексоров каждого яруса устройства, вход запуска блока управления является входом запуска устройства.452, Устройство по п. 1, о т л и - ч а ю щ е е с я тем, что блок управления содержит регистр аргумента, узел выделения значимого разряда, элемент И, счетчик, схему сравнения, ш регистров и генератор импульсов, вход запуска которого является входом запуска блока управления и соединен с входом сброса счетчика и синхронизирующим входом регистра аргумента, информационный вход которого явля ется входом аргумента блока, выход регистра аргумента соединен с информационным входом узла выделения значимого разряда, вход сброса которогосоединен с входом сброса блока, синхровход узла выделения значимого разгряда соединен с синхровходами регистров, вторым входом элемента И, выходом генератора импульсов и с синхровыходом блока, информационный входи-го регистра (п=1ш) соединенс выходом (и+1)-го регистра, информа".ционный вход ш-го регистра соединенс информационным входом узла выделения значимого резряда, выход режимакоторого является выходом управленияоперацией блока, выход равенства узла выделения значимого разряда соединен с первым входом элемента И, выход которого соединен со счетным входом счетчика, выход которого соединен с вторым входом схемы сравнения,первый вход которой является входомзначения блока, выход схемы сравнениясоединен с входом останова генерато"ра импульсов и выходом готовностиблока, выходы с первого по т-й регистров соединены с первого по ш-йвыходами задания режима блока соот"ветственно,3. Устройство по п. 2, о т л и" ч а ю щ е е с я тем, что узел выделения значимого разряда содержит вычитатель, приоритетный шифратор, дешифратор сумматор-вычитатель, регистр, схему сравнения и триггер, входы сброса установки которого соединены с выходами "Меньше" и "Больше" схемы сравнения соответственно, выходРавно которой является выходомРавно узла, первый вход суммы сравнения соединен с информационным входом узла и .первым входом вычитателя, а второй вход соединен с вторым входом вычитателя, первым входом сумматора и выходом регистра, выход вычитателя соединен через приоритетный . шифратор с входом дешифратора и информационным выходом узла, второй вход сумматора соединен с выходом дешифратора, вход режима сумматора соединен с прямым выходом триггера и выходом режима узла, выход соединен с информационным входом регистра, синхронизирующий вход которого соединен с синхронизирующим входом узла, вход установки в "О" соединен с входом установки в "О" узла.Выходь Входы Выходы Ц 2 ф ЦОСЗ РО РЗ Р 2 Р 5 Р 4 Рб.15 0 10 0 1 0 0 1 Х Х Р 4 РЗ Рб Р 5 Р 7 0 1 1 Х 0 0 Х Рб Р 5 Р 7 0 1 0 1 0 0 Р 5 Рб 0 Р 7 020000025 1 Х 0 0 0 0 0 0 0 Рб 0 Р 7 0 0 0 0 О 0 0 0 0 0 0 0 0 0 Х - любое Входыуправл. Выходы 30 Входь Выходы СО ч 7 Р 2 РО Я,7 Яб Я ЯО ЯЗ Я 2 2 О 0 Р 2 Р 1 РО й 4 ЯЗ СЗ С 2 0 0350 0 0 Р 4 РЗ О Р 7 РЗ Р 2 1 Рб РР 0 0 0 0 Р 5 Р 2 Р 1 1 Р 4 Р 1 РО 0 0 0 РО. 0 0 РЗ 0450 0 0 1 Р 2 0 0 РО 0 0 Р 1 0 0 0 0 0 1 1 РО 0 0 0 0 0 0 50 0 0 0 0 0 О 0 1 1 0 0 0 1 1 0 0 0 О 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1418708ТаблицаТ а блица 2 0 0 40 0 Рб Р 5 Р 5 Р 4 Р 4 РЗ РЗ Р 2 Р 2 Р Р 1 РО Та блица 3 Таблица 4 РОО 0 0 0 0 00 0 0 0 0 О 0 0 0 0 0 00.0