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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 9 06 Г 1 САНИ ИЗОБРЕТЕНИЕТЕЛЬСТВУ АВТОРСКОМУ ко ды суммиодами уст- Зь.е СУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(71 ) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистичес йреволюции(56 ) 1. Патент Японии 9 49-28212,кл, 0 06 Р 15/00, опублик. 1974.2. Благовещенский О.А., Теслер Г.С. Вычисление элементарныхФункций на ЭБМ. Киев "Техника",1977, с. 68-72.3. Авторское свидетельство СССРР 451088, кл. 0 06 у 15/31, 1972,4. Авторское свидетельство СССРР 556446, кл. 0 06 Р 15/31, 1975,5. Кнут Д. Искусство программирования для ЭВМ, Т. 2, М., "Мирф,1977, с, 511.6, шауман А.М. Основы машиннойарифметики. Л., изд-во Ленинградского университета, 1979, с, 187.7. Полупроводниковые запоминающие устройства, Под ред. А.Ю. Гордо;нова. И., "Радио и связь 1, 1981,:с. 181,8, Авторское свидетельство СССРВ 868767, кл. 0 06 Р 15/31, 1978(54 ) (57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМОВ, содержащее ш сумматоров, (ш+1) регистров коэффициентов и регистр аргумента, выходы которого подключены к первым входам сумматоров, вторые входы которых связаны с выходами соответствующих регистров коэффициентов, о т л ич а ю щ е е с я тем, что, с целью повыаения быстродействия, в устройство введены (ш+1) блоков постоянной памяти и суммирующий блок, входы которого соединены с выходами (ш+1 )-гь регистра коэффициентов и с выходами блоков постоянной памяти, входы ш из которых соединены с выходами соответствующих суммато- Е ров, входЫ (ш+1 )-го блока постоянной памяти подключены к выходам регистра аргумента, а выхо рующего блока являются вых ройства.Изобретение относится к вычислительной технике и может быть применено в цифровых вычислительных машинах и устройствах.Известны устройства, предназна-. ченные для вы исления полиндмов 5 у(х)=а +ах + ах +ах, пред.в ставляющие собой универсальные вычислительные машины Г 13 . Такие устройства содержат регистры, сумматоры, блоки управления, оперативное запоминающее устройство. Вычисление полиномов в них осуществляется путем выполнения соответствующих программ, например программ вычисления многочлена по схеме Горнера.для 15 выполнения этих программ необходимо осуществить ш сложений и ш умножений, где ш - степень полинома. Кроме того, затрачивается время на ббращение к памяти за операцдами и 2 О командами и на модиФикацию команд,В случаях , когда вычислЕние полиномов необходимо производить многократно для различных значений аргумента Х при фиксированных зна- .25 чениях коэффициентов а используют-. ся методы предварительйой обработки коэффициентов, что уменьшает требуемое число умножений 123. В частности, для вычисления полинома шестой ЗО степени в этом случае необходимо выполнить, четыре умножения к семь сложений, т.е. на два умножения меньше, чем по схеме Горнера.:Недостатком устройства, в котором реализованы программные методы вычислений, является низкое быстро действие, что объясняется необходимостью не только многократного выполнения операций умножения и сложения, но и многократного обращения 40 к запоминающему устройству за ко" мандами и операндами, модификации команд и т,д. Известны также устройства длявычисления полиномов, в которых,реализованы аппаратурные методывычислений, что поэ воляет,прокэводктьвычисление быстрее,чем в устройствах,работаквих по программному принципу.К устройствам такого типа можноотнести устройс во для вычисленияполинсмов вида х у СЗЧ, содержащее регистры оп рандов и промежуточных результатов, сумматоры,схемы И, блок управления; устройство для вычисления полиномов 143,содержащее регистр, сумматоры, реверсивный счетчик, схему сразненкя,элементы И элемент задержки.Недостатком таких устройств так Оже является низкое быстродействие,Например, для вычисления полиномав первом из них необходимо выполнить ш и циклов вычислений, гдеи - разрядность операндов, каждый из которых состоит из суммирования и сдвига. Второе кз известных устройств производит вычисление поли- нома в следящем режиме и обладает низким быстродействием для больших рассогласований аргумента.Известны также табличные устрой-. ства для вычисления полиномов, содержащие постоянные запоминающие 1устройства для получения степеней х аргумента Х и для умножения их на соответствующий коэффициент а.Г 5). Однако для табличной реализации умножения необходим большой объем постоянной памяти, равный 2 и бит, в связи с чем при разЬрядности операндов и6 применение табличных мнонительных устройств затруднено Г 63.Поэтому применяют методы умножения с использованием таблиц логарифмов и антилогарифмов, а также (что более экономично) таблиц квадратов чисел. Во втором случае умножение чисел Х и Х осуществляется по Формуле С 73хт ( ) -(=) Х+Т Х-У а 2 2 Однако и в этом случае необходимбольшой объем постоянной памяти.Так, для реализации одного умножения необходимо иметь два блока постоянной памяти емкостью 2" и,где и - разность операндов,для построения .табличного устройства, предназначенного.для вычисления полинома, накример, пятой сте- .пени, требуется четырнадцать блоковпостоянной памяти. Четыре из нихиспользуются для вычисления значений Х,ХЗ,Х,Хз к десять - для умножения следуюцнх пар чисел: а ха хф, аз хф, ахф, а хф . СуьвИрныйобъем постояниой памяти долженсоставлять 4(Р и)+10(2 ф и) бит,что, например, прк и12 будетиметь величину 688 К бит, Таким образом, известные табличные устройства требуют для кх построения большого объема оборудования.Наиболее близким к предлагаемомуявляется устройство для вычксленкяиногочленов вкдаД. А; х, содержащее накаплквакщке сумматоры, сдвиговые регистры, регистры операндов,регистры коэффициентов, Формирователи цифр, регистры цифры С 83,Перед йачалом вычислений в регистрах коэффициентов и суиматорахзаписаны коэффициенты а, в регистрах операндов записан код аргумен-та Х. Вычисления в известном устройстве производятся в (2 1 ок(а+1 )+и)циклах, каждый кз которых состоитиз суммирования и сдвига.Недостатком известного устройства является низкое быстродействие,Действительно, время вычисленийсоставляет Т = (2 оК(+2)+п)б(Св + 1, где- время суммирования, Сщд- время сдвига.5Целью изобретения является повышение быстродействия.Поставленная цель достигаетсятем, что в устройство, содержащеее суввнвторов, (ет 1) регистров ковф- (Официентов и регистр аргумента, выходы которого подключены к первьм..входам суьиаторов, вторые входыкоторых связаны с выходами соответствующих регистров коэффициентов, 15введены (щ+1) блоков постоянной памяти и суммирующий блок, входы которого соединены с выходами (щ+1)-горегистра коэффициентов н с выходамиблоков постоянной памяти, входы щ 20из которых соединены с выходами соответствующих сумматоров, входы(щ+1)-го блока .постоянной памяти подключены к выходам регистра аргумента, а выходы суммирующего блока являются выходами устройства,На чертеже изображена структурнаясхема устройства для вычисления полинсиов степени щ.Выходы регистра аргумента 1 подкло-Очены к йервым входам сумматоров 2-4,число которых равно щ (щ - степеньполинома)ф и ко входам блока постоянной памяти 5. Вторые входы каждогосуьиатора 2-4 связаны с выходами регистров коэффициентов 6-8, числокоторых равно щ, Регистры 6-9 входятв состав блока коэффициентов 10. Выходы каждого сумматора 2-4 соединенысо входами блоков постоянной памяти11-13, чиоло которых равно щ. Выходы блоков 5, 11-13 и регистра коэффициентов 9 связаны со входамисуммирующего блока 14, выходы которого подключены к выходам 15 устройства. 45В блоки постоянной памяти 11-13записаны таблицы возведения чиселв степень, причем блок постояннойпамяти 11 предназначен для возведения числа в степень "2", блок постоянной намяти 12 - для возведения в степень 13 ф и т.д., до блокапостоянной памяти 13, который предназначен для возведения числа в степенв щ. В блок постоянной памяти 5записана таблица функции -(хз+хЗ++хаф+ хфф 1).Суммирующий блок 14 предназначендля суммирования (щ+2) .чисел иможет быть построен, например, ввиде дерева суьыаторов.Устройство предназначено для вычисления полинома с предварительнойобработкой коэффициентов. Перед началом вычисления полинома У(х) Вй в + ах + ах+в(в(хф аргу мент Х записан в регистре аргумента 2.В блоке коэффициентов 10 записаны ковффниненты Е,=Г, в 1 ), которые определяются следующим образом:ос(ф- Ьа- Сафа ф(ф(+);Есем =щФ(мим д );а-(ц-С" -с,фу- -оф 4);а= а,-ос, -а- . -ас-о;пффф (фф 3Кфгде Ск т(, -ыГ( в , - бннсынненьныекоэффициенты.(При этом каждый коэффициент 4 А(3. =2, щ + 1) записан соответстевенно в регистры 6-8, а коэффициент Ю записан в регистре 9.В состав блока коэФФициентов 10 может входить, например,запоминающее устройство, в котором хранятся наборы коэффициентов, соответствующих различньм Функциям,;аппроксимнруемых многочленами. Перед началом вычисления определенного много- члена соответствующие коэффициенты находятся в регистрах коэффициентов.Вычисление полинома осуществляется следующим образом.С выходов регистра аргумента 1 значение аргумента Х поступает на входы сумматоров 2-4 и на адресные входы блока постоянной памяти 5, На выходах сумматоров 2-4 образуются соответственно значения (Щ+Х),где2, щ. На выходах блока постоянной памяти 5 Формируется значение функциИ - (х+ хф++ х(ф + х)ф(е.Коды с выходов суьаааторов 2- 4 поступают на адресные входы блоков постоянной памяти 11-13, на выходах каждого 1-го из которых (блоку 11 соответствует номер= 1, а блоку 13 номер 1 = щ ) формируется значение Функции Ифф + Х)"ф. Окончательное значение полинома 7(х) формируется в суммирующем блоке 24 пу-, тем суммирования кодов с выходов блоков постоянной памяти 5, 11-13 и кода с выходов регистра коэффициЕнтов 9. Таким образом, на выходах 15 устройства значение полинома формируется в видеЬЪ сС.ф Оса Х)ф 4 СафХ)з ,+(а .уф1067509 Чл ":в, фЬв+ "Ьв 1 99 Подписно ИИПИ Заказ 11210/52 Тир илиал ППП "Патент"., г.ужгород, ул .Проектная,4 Как следует из описания работы данного устройства, время вычисления многочлена составляет где 1 ь - время возведения в степень;- время суммирования (ш+2)-х кодов в суммирующем блоке.Как уже отмечалось, блоки возведения в степень и функциональный блок можно построить на основе блоков постоянной памяти, Сравним с задержкой в одноразрядном сумматоре 1 л,. Например, задержка сигналов в блоке постоянной памяти, пост, роенном на основе микросхем 155 РЕ 21, составляет 60 нс, а задержка в четырехразрядном сумматоре микросхема 155 ИМЗ) - 55 нс Г 92. В зтом случае можно принять 16 - 5 1. Определнм время с,. При построении суммирующего блока в виде многослойного сумматора Г 101 время сложения в нем (ш+2) чисел составляет(п+2 1 ок(в+2 ) ) с . Тогда времявычисления в известнсм устройстве в аз больше времени вычислений в пред.лагаемом устройстве. Здесь принятапоследовательная организация переносов в сумматорах, временем 1 в, пренебрегаем, Например, для и =. 32,в = 8 получим ръ 16,5. Кроме того,15 предлагаемое устройство требуетдля построения меньшего объема памя-ти, чем табличное устройство 18 3.Действительно, общий объем постоянной памяти в данном случае состав 2 О ляет при ш = 5 и и = 12 величину6(2" 12) = 295 К бит. т.е. на688 - 295=393 К бит меньше, чем визвестном устройстве,