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

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

Известны устройства l , предназначенные для вычисления многочленов 1 (х) i а о о I-О 2 X i-.,. а m , представляющие собой универсальные вычислительные машины, содержащие регистры, сумматсры, память, устройства у1фав ления. Вычисление многочленов в них осуществляется путем вьшолнения срот ветствующих программ, например 1фограм вычисления многочлена по схеме Горнера. Для Вьшолнения этих программ необходиМО осуществить п сложений и m умножений, где m - степень многочлена. Кроме .того, затрачивается время на обращение к памяти аа операндами и командами и на модификацию команд, В , когда вычисление многочленов необходимо производить многократно для различньхх значений аргумента Ч при фиксированных з ючениях коэффициентов а , используют ся методы предварительной обработки коэффидиентов, что уменьшает требуемое число умножений 2. В частности, для вычисле1шя многочлена шестой степени в этом случае необходиМО вьшолнить четьфе умножения и семь сложений, т;е« на два умножения меньше, чем по схеме Горнера,

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

Известны также устройства для вычисления многочленов, в которых реализованы аппаратурные методы вычислений, что дозволяет производить вычисления быст рее, 4ew в устройствах, работающих по программному принципу, К устройствам такого Т1ша относятся устройство для вычисления полиномов з, содержащее регистры операндов и промежуточных результатов, сумматоры, схемы И, блок управления и устройство для вычисле1шя полиномов 4, содержащее регистр, сумматоры, реверсивный счетчик, схему сравнешш, элементы И, задерж1Ш,

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

Известны табличные устройства для вычисления многочленов, содержащие постоянные запоминающие. устройства для получения степеней х аргументах дл умножения их на соответствующий коэффициент а; б,.

Однако табличная реализация умножения затруднена тем, что при ра; ядности операндов П 6 требуется бопьщой объем постоянной памяти, равш,1й2 И бит б) В связи с этим применяют методы умножения с использованием таблиц логарифмов и антилогарифмов, а также (что более экономично) (таблиц квадратов чисел. Во втором случае умножения чисел X и осуществляется по формуле х

(X ()-)Я

.

22

СЗднако в этом случае необходим большой постоянной памяти. Так, для реализации одного умкомсения необходимо иметь два ПЗУ емкостью 2 -И , где У1 - разрядность операндов. Для построения табличного устройства, предназначенного для вычисления многочлена,например/ пятой степени, требуется четырнадцать ПЗУ, Четыре йэ них используются для вычисления значений Х, х .Х и десять - для умножения следующих

. .j V

пар ,чисел;а4 X ,O,

г

а с Х, Суммарный объем пос янной памяти должен составлять 4( 2 ч ) + 10( 1 ) бит, что, нахфимер iqsH И 12, будет иметь величину 688 бит. Таким образом, известные табличные устройства требуют для построения большогчэ объема обфудования.

Наиболее близким к гфедлагаемому является устройство для вычисления многочленов видах , содержащее накапливающие сумматоры, сдвиговые peгистры, регистры операндов, регистры коэффициентов, формирователи цифр, регистры ци4рьи началом вычнслений в регистрах коэффициентов н в сумматорах записаны коэффициенты О , в регистрах операндов записан Ч , Вычисления в известном устройстве производятся В ( 1) + П ) циклах, каждый из которых состоит из суммирования и сдвига. Недостатком данного устройства явпяiBTCfl низкое быстродействие, Действитель но время вьгаислений составляет (no42lm4i +nV( где tc - время суммирования; сАв - время сдвига, Цепью изобретения является повышени быстродействия. Постатейная цель достигается тем, что в устройство, содержащее входной регистр, m сумматоров и ( w - 1 ) регисгров коэффициентов, выходы m из которы подключены к первым входам соответствующих сумматоров, вторые входы первого сумматора с вь1кодами входного регистра, введены нл блоков постоянной памяти первой группы, щ блоков постоянной памяти второй группы и сумм1фующий блок, входы которого соединены с выхо-дами блоков постоянной памяти второй группы, входы котфых соответственноподключены к выходам сумматс ов, пер вые входы котс5)ых соединены с выходами регистров коэффициентов, а вторые входы каждого i -го сумматора (i 2,tt соединены с выхода ми-i -го блока постеявшой памяти первой группы, входы блоков йостоянной памяти первой грухшы соединены с выходами входного регистра вь1ходы первого блока постоянной памяти первой группы подключены ко входам суммирующего блока, другие входы которого соединены с выходами ( m )-го регистра коэффициентов, выходы суммиру ющего блока соединены с выходами устройства. На чертеже изображена структурная схема устройства для вычисления многочленов степени tn , Выходы входного регистра 1 соедйк©: ны с входами блоков постоянной памяти 2-5, число которых равно степени много«шена ш , и с первыми входами сумма- Tqja 6. Выходы каждого блока постояв ной памяти 3-5 подключены к первым входам сумматоров 7-9, Вторые fficoды каждого сумматора 6-9 связаны с выходами блока коэффициентов 10, Рагю стры 11 - 15, число котсрых равно (im + 1 ), входят в состав блока коэффициентов Ю, Выхс)Ды сумматоров 6-9 связаны с входами блоков постоянной памяти 16 - 19, число которых равно til и выходы которых подключены ко входам суммирующего блока 20, ко входам которого также подключены выходы блока постоянной памяти 2 и выоды регистра коэффициента 15, Выходы суммирующего блока 2О соединены с выходом устройства 21. В блоке постоянной памяти 2 записана таблица функции - (х - X f ), В блоке постоянной памяти 3-5 записаны таблиЩз для возведения чисел в степень, 1ф№чем в блоке постоянной п«1мяти 3 записаны числа, равные х , в блоке постоянной памяти 4 числа, равные х и т, д,, а в блоке постоянной памяти 5 записаны числа . В блоке постоянной памяти 16-19 записаны таблицы возведения чисел в- квадрат. Сумм ующий блок 20 предназначен для суммирования ( W + 2 ) чисел и может быть построен, например, в виде дерева сумматоров. Перед началом вычисления многочленаF(x aota,)( + a7x --tawx аргумент X записан во входном регистре 1, а коэффициенты а 1 - в блоке коэффициентов 10, При этом в каждом регистре коэффициентов 11 - 14 записан соответственно коэффициент а, (л , а в регистре коэффициентов 15 - коэффициент. (). Вычисление многочлена осуществляет ся следующим образом, С выходов входного регистра 1 значение аргумента х поступает на адреоHbie входы блоков постоянной памяти .2 - 5, а также на одни из входов сумма тора 6, На выходах блока постоянной памяти 2 формируется значение функции (х+ч4 .-лК), а на выходах блоков постоянной памяти 3 - 5 - соответстве но значения Х, х .., х, В каждом сумматоре 6-9 осуществляется суммирование коэффициента О , поступающего с соответствующего выхода регистра коэффициентов 11 - 14 и значениях в соответствии с формулой а -fX , Слова с выходов сумматоров 6 - 9 поступают на адресные входы блоков постоянной памяти 16 - 19, где возводятся в квадрат. Окончательное значение многочлена F ( Л ) формируется в следующем блоке 2О путем суммирования слов, поступающих с выходов блоков постоянной памяти 2, 16 - 19 и регистра коэффициента 15, .Таким образом, на выходах 21 устройства аначение многочлена формируется в виде )-0(о (.. а „i)-(x -tx4X ,.)(„,,„),.... )с.„,о.«.„ло,,п„.. Время вычисления многочлена состав ляетл rtj. ;/ 4.L - 0 с Ci где -tg - емй обращения к блоку посто янной памяти; ijjj --фемя суммирования двух чисел в сумматорах 6 - 9j tp.- время сумК41фования (ГП4 g ) чисел в .суммирующем блоке 20.. Время вычисления многочлена в дачном устройстве составляет i-io+tc.4t(.. Сравним Л-о а задержкой в однозарядном сумматоре Например, задержка сигнала в блоке постоянной памяти на основе микросхем К155РЕ1 составляет 6О НС, а задержка в четьгрехзарядном сумматоре (ми1фосхема К155ИМЗ) 55 НС L91. В этом случае можно принять to St. При построении суммирующего блока в вице многослойного сумматора (jlOj емя сложения ( m + 2) чисел в нем .Тогда время вычислений в известном устройстве (прототипе) в J2eo.;()() + tc ni2eo 2())-t4 ((2)) больше времени вычислений в щэед- , лагаемом устройстве (Здесь временем сдв пренебрегаем). Например, для 32, rW 8 быстродействие увеличивается в р ft 16 раз. Кроме Ttaro, 1федложенное устройство требует для построения меньшего объема памяти, чем известное табличное устройство. Так, общий объем постоянной памяти в данном случае составляет при )т 5 и п « 12 величину 10 (2 е 12) 492 К бит, т. е. на 688 К - 492 К « 196 К бет меньше, чем в известном устройстве.

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