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

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

Известны устройства, предназначенные для вычисления полиндмов F(x) a, -; +...ачх, пр ед-ставляющие собой универсальные вычислительные машины tl3 . Такие устройства содержат регистры, cjrMMaторы, блоки управлений, оперативное запоминающее устройство. Вычисление полиномов в них осуществляется путем выполнения соответствукицих программ, например программ вычисления многочлена по схеме Горвера.Для выполнения этих программ необходимо осуществить m сложений и m умножений, где m - степень полинсма. Кроме того, затрачивается время на Обращение к памяти за операндами и командами и на модификацию ксжланд,

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

Недостатком устройства, в котором реалцзоваш Е программные методы вычислений, является низкое быстро действие, что объясняется необходга остью не только многократного вьтолнения операций умножения и сложения, но и многократного обращения к запсялинаквдег/iy устройству за командами и операндами, модификации команд и т.д.

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

.реализованы аппаратурные методы вычислений, что позволяет .производить

вычисление быстрее,чем в устрсЛствйх,

работающих по программному щжнцнпу. К устройствам такого типа можно

ЙЬтнести устройство для вычисления полиномов вида 1 х у, t31, содержащее регистлйл опе:рандов и промежуточных результатов, сумматоры, схемы И, блок управления; устройство для вычисления полиномов С41, содержащее регистр, сумматоры, реверсивный счетчик, схет«у сравнения, элементы И, элемент задержки.

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

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

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

аргумента X и для умножения их

на соответствукйций коэффициент aj, С51. Однако для табличной реализации умножения необходим большой постоянной памяти, равный

2. п

бит, в связи с чем при разрядности операндов п 6 применение табличных мнозхительных устройств затруднено Сб1.

Поэтому применяют методы умножения с использованием таблиц логарифмов и антилогарифмов, а также (что более экономично) таблиц квадратов чисел. Во втором случае умножение чисел X и Y осуществляется

по С71

V V f2LtI 2 , X-Y X Y « (-g-г )

Однако и в этсж случае необходим большой объетл постоянной памяти. Так, для реализации одного умножения необходимо иметь два блока постоянной памяти &лкостъю 2 п,

где п - разность операндов.

для построения .табличного устройства, предназначенного.для-вычисления полинсмвд напр}О4ер, пятой сте- . пени, требуется четырнадцать блоков

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

jX , Si.x , ajX . Суммарный

а, X

2 Зобъем постоя1 ной пгикяти должен

составлять п)+10(2. п) бит, что, например, при п 12 будет иметь величину 688 К бит. Таким образом, известные табличные устройства требуют дяя их построения больтого обсФ удования.

Наиболее близким к преялагаемоыу является устройство для вычисления многочленов вида,Д, А Х, содержащее накапливакщие: сумматоры/ сдвиговые регистры, регистры операндов, регистры коэффициентов, формирователи цифр, регистры циФ1Я 8}.

Перед началом вычислений в регистрах коэффициентов и сумматорах

записаны коэффициенты а), в регистрах операндов записан код аргумента X. Вычисления в извесфисмх устройстве прсжзводятся в (2 togg (m-i-l )) циклах, кгикдый из которых состоит

из суммирования и сдвига. Недостатком известного устройства является низкое быстродействие. Действительно, время вычислений составляет Т (2 tog( (ip+1 )+п) (te. + tcx) , где tt - время сугдаиро вания, оф время сдвига. Целью изобретения является повышение быстродействия. Поставленная це/н достигается тем, что в устройство, содержащее im сумматоров, (т+1) регистров коэффициентов и регистр аргумента, выходы которого подключены к первым , входам сукматоров, входы которых связаны с выходс1ми срответствуюь1их регистров коэффициентов, введены (m+l) блоков постоянной памяти и суммирукяций блок, входы которого соединены с выходами (т+1)-г регистра коэффициентов и с выходами блоков постоянной памяти, входы m из которых соединены с выходами соо ветствуюишх сумматоров, входы (m-bl)-ro блока постоянной памяти по ключены к выходсш регистра аргумента, а выходы суммирующего блока являются выходами устройства. На чертеже изображена структурна схема устройства для вычисления пол номов степени т. &1Ходы регистра аргумента 1 ПОДК чешл к первым входам сумматоров 2-4 число которфс равно ш (т - степень полинома), и ко входам блока постоя ной памяти 5. Вторые входы каждого сукматора 2-4 связаны с выходами ре гистров коэффициентов 6-3, число которых равно т. Регистры 6-9 входя в состав блока коэффициентов 10. Вы ходы каждого сумматора 2-4 соединен со входами блоков постоянной памяти 11-13, чивпо которых равно т. Выходы блоков 5, 11-13 и регистра коэффициентов 9 связаны со входами суммирую1цего блока 14, выхопд которого подключены к выходам 15 устройства. В блоки постоянной памяти 11-13 записаны таблицы возведения чисел в степень, причет блок постоянной памяти 11 предназначен для возведения числа в степень 2, блок пос тоянной памяти 12 - для возведения в ст&пенъ 3 и т.д., до блока постоянной памяти 13, пред- назначен для возведения числа в сте пень ш. В блок постоянной ПсШЯТЙ 5 згшисана таблица функции -(.. . .. х. Су)ф ирук11ций блок 14 предназначен для суммирования (m-t-2) .чисел и может быть построен, например, в виде дерева сумматоров. Устройство предназначено для вычисления полинома с предварительной обработкой коэффициентов. Перед началом вычисления полинома F(x) а а« + + ... а„х аргуент X записан в регистре аргумента 1 В блоке коэффициентов 10 записаны коэффициенты oL;(, m+l), которые определяются следующим образом: ж Сотн о-т+О i sibr (P«bi-C,«-Vi - Л,) -, ос -(aн :; oL:i cr%r -... - с) , лг-|-:ои-с;1,-(С, -... -с VS); Q« -оС«-ал - .. - CLl-OL ; где C.J - биноминальные коэффициенты.I При этом каждый коэффициент o{,i(i 2, m + 1) записан соответственно в регистры 6-8, а коэффициент (tii записан в регистре 9. В состав блока коэффициентов 10 может входить, например, запоминающее устройство, в котором хранятся наборы коэффициентов, соответствующих различньм функциям, аппрокси-мируемых многочленами. Перед началом вычисления определенного многочлена соответствующие коэффициенты находятся в -регистрах коэффициентов. Вычисление полинома осуществляется следующим образом. С выходов регистра аргумента 1 значение аргумента X поступает на входы су1Ф1аторов 2-4 и на адресные входы блока постоянной памяти 5. На выходах сумматоров 2-4 образуются соответ-ственно значения (г+Х),где 1 2, т. На выходах блока постоянной памяти 5 формируется значение функции - (х + X + .. . + х + ). - - . Коды с выходов сумматоров 2-4 поступают на адресные входы блоков постоянной памяти 11-13, на выходах каждого i-ro из котсфых (блОку 11 соответствует номер i 1, а блоку 13 иомер i т) формируется значение функции (etiti -f X) . Окончательное значение полино(4а F(x) формируется в суммирующем блоке 14 пу- , тем суммирования кодов с выходов блоков постоянной памяти 5, 11-13 и кода с выходов регистра коэффициентов 9. Таким образом, на выходах 15 устройства значение полинома формируется в виде f v{oL2+x)VcC,...+ ( -6t«.xVx4...) ... 4-awX. Как следует из описания работы данного устройства, время вычисления многочлена составляет Т/, -tut., где tft - время возведения в степен сл время суммирования ()-x кодов в суммирующем блоке. Как уже отмечалось, блоки возведения в степень и функциональный блок можно построить на основе блоков постоянной памяти. Сравним 1j с задержкой в одноразряднсм сумматоре t. Например, задержка сигналов в блоке постоянной памяти, nocT роеннсм на основе микросхем 155РЕ21 составляет 60 не, а задержка в четы рехразрядном сумматоре (микросхема 155ИМЗ) - 55 НС С91. В этом случае можно принять tg 5 t. Определим время tc. При построении суммирующего блока в виде многослойного сумматора D101 время сложения в нем (т+2) чисел составляет (п+2toga(ra+2) t. Тогда время вычисления в известном устройстве в р (28оаг6У И Х-Ьй ч-t UA) , -fcft vte. -tai n иг Cbcjz Н4 Canf2.ecx3iO()i-SHv |заз больше времени вычислений в пред;лагаемом устройстве. Здесь принята последовательная организация переносов в сумматорах, временем t.qb пренебрегаем. Напршлер, дпя п 32, m 8 получим ,5. Кроме того, предлагаемое устройство требует для построения меньшего объема пггмяти, чем табличное устройство 83. Действительно, общий объем постоянной памяти в данном случае составляет при величину 6( 12) 295 К бит. т.е. на 688 - К бит меньше, чем в известном устройстве.

ю

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ iПОЛИНОМОВ, содержащее m сумматоров, , (т+1) регистров коэффициентов и регистр аргумента, выходы которого подключены к первым входам сумматоров, вторые входы которых связаны с выходами соответствукидах регистров коэффициентов, о т л и - чающееся тем, что, с целью повьшения быстродействия, в устройство введены (m+l) блоков постоянной памяти и суммирующий блок, входы которого соединены с выходами (m+I)-го регистра коэффициентов и с выходами блоков постоянной памяти, входы m из которых соединены с выходами соответствукндих сумматоров, входы (тч-1)-го блока пЪстоян(Л ной памяти подключены к выходам регистра аргумента, а выходы сумми- . рующего блока являются выходами устройства. СП О о

/5

f4

-И