Устройство для вычисления значения полинома @ -й степени Советский патент 1985 года по МПК G06F17/10 

соединен с входами записи выходных ре™ гистров,вторые входы элементов Hrpyir пы подключены к выходам разрядов счет чика тактов и первой группа входов схемы сравнения, вторая группа входов которой соединена с входами значения разрядности аргумента устройства выходы элементов И группы соединены с управляющими входами мультиплексоров.

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМАm-И СТЕПЕНИ, содержащее сумматор, три входных регистра и. блок управления, отличающеес я тем, что, с целью повьшения быС тродействия, в устройство введены {т-2) входных регистра, (т +О выходных регистра,/ (№+2) (-О Л I ,--- „ 11 сумма- (п +l)rn торов, мультиплексоров, причем первые группы информационных входов входных регистров являются входами коэффициентов полинома устройства, казкдый ч -1 ярус устройства 1 0,... го) содеряшт входной регистр, (J + 1) сумматоров, и +1) мультиплексоров и выз одной регистр, причем в каждом ярусе устройства выходы входного регистра подключены к входам первой группы первого сумматора, выходы j-го сумматора } -го яруса устройства (),..., +0 подкл чены к входам первой группы IJ +1 -гЪ сумматора( -го яруса устройства, выходы (i +1)-го сумматора i -го яруса устройства соединены с информационными входами выходного регистра . того же яруса устройства, входы второй группы сумматоров каждого яруса устройства подключены к выходам соответствующих мультиплексоров того же яруса устройства, информационные входы которых соединены с выходами соответствующих сумматоров последующего яруса устройства, выходы выходных регистров каждого яруса устройства подключены к вторым группам информационных входных регистров тех же ярусрв устройства, 1блок управления содержит генератор тактовых импульсов, регистр аргумента, счетчик тактов, элемент НЕ, два элемента И, группу элементов И и схему сравнения, выход которой соединен С первым управляющим входом генератора тактовых импульсов, второй управляющий вход которого подключен к шине пуска устройства и перСО 4i вым входам записи входных регистров, выход генератора тактовых импульсов QD соединен с синхронизирующим входом регистра аргумента, со счетным вхо дом счетчика тактов, входом элемен.та НЕ и первым входом первого элемента И, выход которого подключен к вторым входам записи входных регистров, второй вход первого элемента И соединен с первым входом второго элемента И, первыми входами элементов И группы и с выходом старшего разряда регистра аргумента, второй вход второго элемента И подключен к выходу элемента НБ а выход

Изобретение относится к вычисли- тельнвй технике и может быть исполь зовано при построении специальных вычислительных машин. Известно устройство для вычислеНИН значений полиномаПТ Й степени, содержащее два регистра сдвига с це пями циклического переноса, выходы регистров через первьй элемент И со динены с входом счетчика переноса, блок управления, выходы которого по ключены к управляющим входам регист ров сдвига, первого элемента И счет чика переноса l 1. Недостатком известного устройст.ва является отсутствие возможности совмещения во времени операций сложения и умножения. Известно также устройство для вы числения полинома, позволяющее вычислять полином с комплексными корними 2j . Однако его быстродействие ограничено. Известно устройство для вычисления полиномов 3j Однако оно вычисляет полиномы только второй и третьей степени и при этом использует число-импульс ное, а не цифровое преобразование. Наиболее близким по технической сущности к предлагаемому является устройство для вычисления значения 1п©линома рп-и степени, содержащее тр элемента И, три регистра сдвига, сумматор, первый вход которого соединен с выходом счетчика переноса, зторой - с выходом третьего регистр сдвига, а выход через второй элемент И - с входом первого регистра сдвига. Выход последнего подключен к первому входу третьего элемента И выход которого подключен к входу пе вого регистрасд)вига. Второй вход третьего элемента И, управляющий вход сумматора, и у правляющий вход третьего регистра сдвига подключены к выходу блока управления 4j. Недостатком устройства является низкое быстродействие, так как вычисления полинома выполняются по схеме Горнера и носят последовательный характер. Цель изобретения - повьшение быстродействия за счет распараллеливания процесса вычислений. Поставленная цель достигается тем, что в устройство для вычисления полинома m -и степени содержащее сумматор, три входных регистра и блок управления, введены{ш-2)входных регистра,ш+l) выходных регистра, (т+2)() л (trn-l)m I„J-- „п сумматоров, -г- мультиплексоров, причем первые группы информационных входов входных регистров являются входами коэффициентов полинома устройства, каждый -и ярус устройства (i 0,...,(И) содержит вход- ной регистр, ( +1 сумматоров, ( i +1) мультиплексоров и выходной регистр, причем JB каждой ярусе устройства выходы входного регистра подключены к входам первой группы первого сумматора, выходы j-го сумматора -го яруса устройства-}j 1,... +1) подключены к входам первой группы ( j l) -го сумматора i -го яруса устройства, выходы (« +1)-го сумматора -го яруса устройства соединены с информационными входами выходного регистра того же яруса устройства, входы второй группы сумматоров каждого яруса устройства подключены к выходам соответствующих мультиплексоров того же яруса устройства, информационные входы которых соединены с выходами соответствующих сумматоров последующего яруса устройства, выходы выходных, регистров каждого яруйа устройтсва 3 подключены к вторым группам информационных входов входных регистров тех же ярусов устройства, блок управления содержит генератор тактовых импульсов, регистр аргумента, счетчик тактов, элемент НЕ, два эле(Мента И, группу элементов И и схему сравнения,выход которой соединен с первым управляющим входом генератора тактовых импульсов, второй управляющий вход которого подключен к шине пуска устройства к первым входам записи входных регистров,, выход генератора тактовых импульсов соединен с синхронизируюпшм входом регистра аргумента, со счетным входом счетчика тактов, входом элемента НЕ и первым входом первого элемента И, выход которого подключен к вторым входам записи входных регистров, .второй вход первого элемента И соединен с первым входом второго эле мента И, первыми входами элементов И группы и с выходом старшего разряда регистра аргумента, второй вход элемента И подключен к выходу эле мента НЕ, а выход соединен с входами записи выходных регистров, вторые входы элементов И группы подклюг чены к выходам разрядов счетчика тактов и первой группе входов схеtitu сравнения, вторая группа входов которой соединена с входами значе- ййя разрядности аргумента устройства, выходы элементов И группы соединены с упразляющими входами мультиплексоров. На фиг.1 представлена блок-схема устройства; на фиг,2 - блок-схема управления. Устройство для вычисления полинома ш-и степени(гл 3), содержит вход- ные регистры 1 - 4, выходные регистры 5 8, .комбинационные сумматоры 9 - 18, мультиплексоры 19 - 24, шины для ввода начальных значений коэф фициентов полинома 25 - 28, блок управления 29, шину JO nycka, шииу 31 разрядности аргумента и шину 32 аргумента. Блок управления содержит генератор 33 татовых импульсов, регистр 34 аргумента X, счетчик 35 так тов, элемент НЕ 36, два элемента И и 38, группу элементов. И 39 и схему сравнения 4Q. Полиномt(x) степени m имеет вид iCx1-. (1) 47 . 4 , где о; (КоУ - коэффициенты полинома, -f f -г Для двоичной систекы счисления X можно представить как .Г,-2 )-0 где п - разрядность числа, i 0,1. Если ,сместить начальную to4Ky о на , то получим iW.i:a;Uol x-Ue V,-2J,. (2) Раскрывая (2) по биному Ньютона, запишем V5U-5). a5lxo ;-2-M-ZctC,-2r -a;Uoi;(3) биномапьные коэффициенты. ,i-Xo ;i-rhlK-Uo i-2 il. Приближая XQ к значению X , как следует из СП, имеем, , (хУ. . Тогда основные вычислительные one- рации состоят в реализации выражения {5) , т.е. в вичислении коэф циёнтов полинома. -J . Их реаггазацию рассмотрим для слу . а; аДх„;(,«2-Ч..,,-г.аз , ,; i(4) а:.а,(хоЧ%2ТПа,.2 --г1а2 3 -а- -с, ;а;.аг(у, (xo(fj2y)a3 де GO ,а, ja.Q-j - коэффициенты полинома, соответ- ствукицие исходному значению if ; д Q ,alj ,а J- коэффициенты полинома после с}4еще- ния на (5. 2) , Устройство работает следукящм o6iазом. В исходном состоянии по сигналу пуск(гп + 1) коэффициентов а/ (vo) загружаются во входные регистры 1-4, а начальное значение 0 подаетerf на мультиплексоры 19 - 24, выпол няющие функцию сдвига на j разрядов вправо. Все операции выполняют-ся на структуре вычисления в соответствии с cootнoшeниями (.4) с помощью сумматоров 9 - 18, мультиплексоров 19 - 24 и представленной системы их связей. Так как мультиплексоры и сумматоры являются комбинационными схемами, то длительность такта вычислений выбирается, исходя из самой длительной операции при вычислении коэффициента dо, после-этого промежуточный результат 0,а , al , :oi, который формируется на выходных регистрах(5 - 8 передается соответственно на входные регистры. Затем увеличивается на единицу, значение t коэффицие нты 0(3 , Q , 02. з ьгступают l.m, .г. В качестве исходных для нового цикла и процесс повторяется. Вычисления завершаются при значении | 1 а вьгчисленное значение полинома i(x) на ходится в регистре (I) . Таким образом, общее время вычислений равно И тактам, а каждый такт пропорционален 1 сложениям, таким 9,бразом следовательно, выигрьш в быстродейс вии по сравнению с прототипом соста вит ,.г...и.н„ N-m-lift Блок управления состоит из генератора 33 тактовых импульсов, выход которого соединен с регистром 34 аргумента X , счетчиком 35 тактов, инвертором 4 и с первым входом элег ента И 37, выход элемента 36 подсоединен к первому входу элемента И 38, а выходы счетчика 35 тактов г к первым входам группы элементов И 3 и схемы сравнения 40, второй вход которой служит для занесения значения разрядности аргумента N . Выход 1 76 схемы сравнения 40 соединен с входом генератора тактовых импульсов 33, причем выход старшего разряда регистра 34 аргумента подключен к всем вторым входам элементов И 37, 38 и группе элементов 39. Выход элемента 37 подклюгчен к управляющим входам входных регистров устройства, вьлход элемента И 38 подключен к управляющим входам выходных регистров, а выходы группы элементов И 39 соединены с управляю - щими входами мультиплексоров устройства. Занесение аргумента X в регистр 34 происходит по шине 32. Бпок управления работает следующим образом. В начальный момент времени по шине 32 заносится значение аргумента X в регистр 34, а в схему сравнения 40 заносится значение разрядности аргумента, равное N , После этого по сигналу Пуск запускается генератор 33 тактовых импульсов и начинает вырабатывать синхроимпульсы, счетчиктактов начинает считать импульсы, и как только досчитает до значения N , срабатывает схема сравнения 40 и отключает генератор 33 тактовых импульсов, в то же время по заднему фронту импульса синхросерии в каждом так- те происходит сдвиг содержимого регистра 34 аргумента влево на один разряд. В зависимости от состояния старшего разряда регистра 34 аргумента управление предлагаемого устройства либо происходит, либо нет, т.е. если старший разряд аргумента равен единице, то блок управления управляет работой входных и выходных регистров и мультиплексоров. В зависимости от показаний счетчика мультиплексоры производят сдвиг на определенное количество разрядов, если же старший разряд аргумента равен нулю, то никаких изменений в устройстве не происходит, а работает лишь блок управления: считает импульсы, производит сдвиг аргумента и выпол- няет сравнение значения счетчика со значением разрядности аргумента N,