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

(19) (И) СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК З(5 6 06 Р 15/31 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 7Йф ТбатнаЙ т.д . :134)й 3 ЯДР ЯГт Ъ "СТВО ДЛЯ ВЫЧИСВ, содержащее входмаш ающиенова. ГОСУДАРСТВЕННЫИ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Киевский ордена Ленина политехнический институт им. 50 летия Великой .Октябрьской социалисгической революции(56) 1, Патент Японии49-28212кл. 0 06 Г 15/00, опублик. 1974.2. Благовещенский Ю. А., Теслер Г.С.Вычисление элементарных функций на ЗВМ.Киев, "Техника", 1977, с. 68-72.3. Авторское свидетельство СССР451088, кл. С 06 Г 15/31, 1972 е4, Авторское свидетельство СССР556446, кл. ( 06 Г 15/31, 1975 е5. Кнут Д. Искусство программирования для ЭВМ, Т. 2 М., "Мир", 1977,с. 511.6, Шауман А. М. Основы иннойарифметики. Л., изд-во Ле скогоун-гга, 1979, с, 187.7. Полупроводниковые запомниустройства. Под реп, А. Ю. ГордоМ., Радио и связь, 1981, с. 181.8. Авторское свидетельство СССР868767, кл.06 Г 15/31, 1978.(прототип) ь9. Справочник по интегральным микросхемам. Под ред, Б. В, Тарабрина. М., Энергия", 1980, с. 124-186.10. Карцев М. А., Брик В, А. Вычислительные системы и синхронная арифметика. М., "Радио и связь", 1981,с 205.(54)(57) УСТРОЙ ЛЕНИЙМНОГОЧЛЕНО ной регистр, т сумматоров и ( )и + 1) регистров коэффициентов, выходы Ф, изкоторых под,ключены к первым входам соответствуюших сумматоров, вторые входы первого сумматора соединены с выходами входного регистра, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены Ф блоков постоянной памяти первой группы, Ф блоков постоянной памяти второй группы и суммирующий блок, входы которого соединены с выходами блоков постоянной памяти второй группы, входы которых соответственноЕ подключены к выходам сумматоров, пер, вые входы которых соединены с выходами регистров коэффициентов, . а вторые(., входы кал;дого 1 -го сумматора (л: Д,щ) соединены с выходами-го блокапостоянной памяти первой группы, входы блоков постоянной памяти первой группы соединены с выходамч входного регис 1 ра, выходы первого блока постоянной памяти первой группы подключены ко входам суммирующего блока, другие входы которого соединены с выходами ( в+ 1)-го регистра коэффициентов, а выходы суммирующего блока соединены с выходами устройстваИзобретение относится к вычислительной технике и может быть примененов цифровых вычислительных машинах иустройствахИзвестны устройства 1, предназначенные для вычисления многочленов9(х) = д+О,кс 1 гх +, + Ох,представляющие собой универсальные вычислительные машины, содержащие регистры, сумматоры, память, устройства управ 10ления. Вычисление многоиленов в нихосуществляется путем выполнения соответствующих программ, например программвычисления многочлена по схеме Горнера.Для выполнения этих программ необходимо осуществить В слакений и т умножений, где а- степень многочлена, Кроме,того, затрачивается время на обращениек памяти за операндами и командами ина модификацию команд. В слуаях, когда вычисление многсиленов необходимопроизводить многократно для различныхзначений аргумента х при фиксированныхзначениях коэффициентов О;, используются методы предварительной обработки коэффкциентов, что уменьшает требуемоечисло умножений 21,В частностидля вычисления многочленашестой степени в этом случае необходимо выполнить четыре умножения и семь З 0сложений, т;е. на два умножения меньше,чем по схеме Горнера.Недостатком устройств, в которых1реализованы программные методы вычислений, является низкое быстродействие, . 35что объясняется необходимостью не только многократного выполнения операцийумножения и сложения, но и многократного обращения к запоминающему устройству за операндами и командами, модификации команд и т, д.Известны также устройства для вычисления многочленов, в которых реализованы аппаратурные методы вычислений, чтопозволяет производить вычисления бысърее, чем в устройствах, работающих попрограммному принципу. К устройствамтакого типа относятся устройство длявычисления полиномов 3, содержащеерегистры операндов и промежуточных 50результатов, сумматоры, схемы И, блокуправления и устройство для вычисленияполиномов 4, содержащее регистр,сумматоры, реверсивный счетчик, схемусравнения, элементы И, элемент задержкиеНедостатком таких устройств такжеявляется низкое быстродействие, Например, для вычисления,многочлена в первом из,них необходимо выполнитьй.и пиклов вычислений, каждый,из которых сос.тоит из суммирования и сдвига. Второеиз известных устройств производитвычисление многочленов в следящем режиме и обладает низким быстродействием для больших рассогласований аргумента.,Известны табличные устройства длявычисления многочленов, содержащиепостоянные запоминающие устройствадля получения степеней х аргументах дляумножения их на соответствующий коэффициент 0; Я.Однако табличная реализация умножения затруднена тем, что при разрядностиоперандов й ) 6 требуется большой обьемпостоянной памяти, равный 2 " И бит 6,В связи с этим применяют методы умножения с использованием таблиц логарифмов и антилогарифмов, а также (что более экономично) габлиц квадратов чисел,Во втором случае умножения чисел х иу осуществляется по формуле х =,("+ (х-я) г 1Однако в этом случае необходим большой объем постоянной памяти. Так, дляреализации одного умножения необходимо иметь два ПЗУ емкостью 2 + ии+4где п - разрядность операндов. Для построения табличного устройства, предназначенного для вычисления многочлена,например, пятой степени, требуется четырнадцать ПЗУ. Четыре из них используются для вычисления значений Х г, Х , Х 4,х и десять - для умножения следующих%пар чисел ОХ ф 0 г Х э(3Х э О 4 Х эг ъ 4О" Х 5. Суммарный объем постоянной памяти должен состаэлять 4(2 и ) ++ 10(2 И ) бит, что, например при0 12, будет иметь величину 688 бит.Таким образом, известные табличныеустройства требуют для построения боль-.шого объема оборудования. Наиболее близким к предлагаемому является устройство для вычисления многочленов вида.Х А Хг 8, содержащее накапливающие сумматоры, сдвиговые ре- гистры, регистры операидов, регистры коэффициентов, формирователи цйфр, регистры цвфры. Перед .началом вычислений в регистрах коэффициентов и в сумматорах записаны коэффициенты 0;, в регистрах операндов записан )( . Вычисления в известном устройстве производятся/3 : 1048в (2 00 (п 1. 1) 4- 0 ) циклах, каждыйиз которых состоит из суммирования исдвига.Недостатком данного устройства являЬтся низкое быстродействие. Действительно время вычислений составляет: фРоЬ(щфф Чсфср,в 1где 1 с - время суммирования;1 С - время сдвига,0Целью изобретения является повышениебыстродействия,Поставленная цель достигается тем,что в устройство, содержащее входнойрегистр, п сумматоров и ( а1 ) регистров коэффициентов, выходы Е иэ которыхподключены к первым входам соответствующих сумматоров, вторые входы цер;.вого сумматора с выходами входного регистра, введены В блоков постоянной па-, омяти первой группы, Ю бпоков постояннойпамяти второй группы и суммирующийблок, входы которого соединены с выходами блоков постоянной памятй второйгруппы, входы которых соответственноподключены к выходам сумматоров, пврвые входы которых соединены с выходами регистров коэффициентов, а вторыввходы каждого 1 -го сумматора (. = 2,И )соединены с выходами-го блока постоянной памяти первой группы, входы блоков постоянной памяти первой группысоединены с выходами входного регистра,выходы первого блока постоянной памятипервой группы подключены ко входамсуммирующего блока, другие входы которого соединены с выходами ( И+ 4 )-горегистра. коэффициентов, выходы суммфующего блока соединены с выходами устройства.40На чертеже изображена структурнаясхема устройства для вычисления многочленов степени И 1,Выходы входного регистра 1 соедйнв.ны с входами блоков постоянной памяти2-5, чисно которых равно степени многолена щ, и с первыми входами сумма-тора 6. Выходы каждого бпока постоян.ной памяти 3 - 5 подключены к первым.входам сумматоров 7 - 9, Вторые вхо-"ды каждого сумматора 6 - 9 связаны свыходами блока коэффициентов 10. Регистры 11 - 15, число которых равно( Ф Ф 1 ), входят в состав блока коэффициентов 10. Выходы сумматоров 6 - 9 Ысвязаны с входами блоков постояннойпамяти 16 - 19, число которых равнов и выходы которых подключены ко входам суммирующего блока 20, ковходам которого также подключены выходы блока постоянной памяти 2 и выходы регистра коэффициента 15,.Выходысуммирующего блока 20 соединены свыходом устройства 21. В блоке постоянной памяти 2 записана таблица функции - (х + х 4 Ф хбх)В блоке постоянной памяти 3 - 5 записаны таблицы для возведения чисел в степень, причем в блоке постоянной памяти 3 записьны числа, равные х, в блоке постоянной памяти 4 числа, равные х и т. д9а в блоке постоянной памяти 5 записанычисла х . В блоке постоянной памяти16 - 19 записаны таблицы возведениячисел в квадрат. Суммирующий блок 20предназначен для суммирования ( Я+2 )чисел и может быть построен, например,в виде дерева сумматоров,Перед началом вычисления многочлена Г(х) =аоа,х а 2 Х 2 "а хфф аргумент х записан во входном регистре 1, а коэффициенты а; - в блоке коэффициентов 10. При этом в каждом регистре коэффициентов 11 - 14 записан сооьветственно коэффициент О( 4 = 1, е ), а в регистре коэффициентов 15 - коэффи- циент Вычисление многочлена осуществлявъся следующим образом. С выходов входного регистра 1 зна-чение аргумента х поступает на. адресные входы блоков постоянной памяти 2 - 5, а также на одни из входов сумматора 6. На выходах блока постоянной памяти 2 формируется значение функции(хЬхф х" +х 2"), а на выходах блоков постоянной памяти 3 - 5 - соответственно значения Х, Х .Х . В каждом сумматоре 6 - 9 осуществляется сумми рование коэффициента О;, поступающего с соответствующего выхода регистракоэффициентов 11 - 14 и значения Х всоответствии с формулойй;+Х . Слова с выходов сумматоров 6 - 9 поступают на адресные входы бпоков постояннойпамяти 16 - 19, где возводятся в квЮрат. Окончательное значение многочлеааР ( Х ) формируется в следующем блоке 20 путем суммирования слов, поступающнх с выходов блоков постояннойпамяти 2, 16 - 19 и регистра коэффициента 15.,Таким образом, на выходах 21