Устройство для возведения в степень

(23) Приорит Опубликовано 07,12.81, бюллетень М 4Дата опубликования описания 071231 ае велев взебретееи и еткрыти.П. Та иевский ордена Ленина политехническм. 50-летия Великой Октябрьской соцреволюции(7 ) Заявитель 54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В СТ Недостатками известного ва являются относительно не быстродействие, связанное с можностью вычислять разряды тата во время, когда на вхо ства поступили еще не все р гументов и, большая сложнос ства. устроистысокое не резуль- . устройзряды арь устройвы Изобретение относится к областицифровой вычислительной техники и мо"жет быть использовано в ЦВИ и специализированных устройствах.Известно устройство для возведения в степень 1, содержащее группусумматоров, Счетчикблоки сдвига иустройство управления,Недостатками устройства являетсяотносительно низкое быстродействиеи значительное увеличение объема аппара"10туры при увеличении показателя степени,Наиболее близким к изобретениюрешением данной технической задачиявляется устройство 2, содержащеегруппу однотипных последовательносоединенных множительных блоков,блок управления шины аргумента и регистр операнда, выходы которого соединены с первыми входами множительныхблоков, первый вход соединен с первым выходом блока управления и со вторыми входами множительных блоков. Целью изобретения является по шение быстродействия,Цель изобретения достигается тем,что устройство содержит триггер исходного состояния, вход которого соеди"нен с шиной показателя степени итретьими входами множительных блоков, четвертые входы которых соеди"иены с выходом триггера исходногосостояния. Второй и третий выходыблока управления соединены с пятым ишестйм входами множительных блоков,Второй вход регистра операнда соединен с выходом первого множительного блока, шины аргумента соединены00101100000000 00011000000000 См. 10 11011000000000 00110000000000 5 См. 10 6 цикл 5 цикл Такт 11 ооооаооооо 3 См. 10 00110000000000 00110000000000 11100000000000 5. См. 10 8 цикл 7 цикл Такт 11000000000000 11100000000000 3 См. 10 4 г 0000000000000 5 См. 10 110000000000 Как видно из примеров, задержка появления на выходе блока 6 соответствующих цифр результата не зависит от разрядности о и составляет 4 цикла т,е. при любом о, в каждом с-м цикле (Е 1, 2, ,о+4), когда на входные шины 21 поступает цифра с весом2-И 41, на выходных шинах 21 формируется очередная цифра результата, имеющая вес 2 ф-ф. Следовательно, полный результат на выходе всего устройства будет получен после приема Продолжение табл. 3 последней цифры операнда Х с задержкой на время Т 1= 4 пТ, тогда как аналогичная задержка для известного устройства составляет Т Т + Т ТИ+ цТп, При разрядности ц операнда Х, равной 36, и разрядности (и+1) операнда У, равной 5, означает сокращение времени получения результата не менее, чем в 16 раз,бсли же сравнивать все время работы устройства от приема первой цифры аргумента до выдачи последнейцифры результата, то получим, что дл указанной разрядности предлагаемое устройство превосходит по быстродействию известное в 9,2 раза.Помимо увеличения быстродействия которое достигается для любого У, предлагаемое устройство также позволяет уменьшить аппаратурные затраты при больших значениях т.Формула изобретения1. Устройство для возведения в степень, содержащее группу однотипных последовательно соединенных множительных блоков, блок управления, шины аргумента и регистр операнда, выходы которого соединены с первыми входами множительных блоков, первый вход соединен с первым выходом блока управления и с вторыми входами множительных блоков, о т л и ч аю щ е е с я тем, что, с целью увеличения быстродействия и сокращения количества оборудования, оно содержит триггер исходного состояния, вход которого соединен с шиной показателя степени и третьими входами множительных блоков, четвертые входы которых соединены с выходом триггера исходного состояния, при этом второй и третий выходы блока управления соединены с пятым и шестым входами множительных блоков, второй вход регистра операнда соединен с выходом первого множительного блока, шины аргумента соединена с седьмыми входами множительных блоков.2. Устройство по п,1 , о т л и ч а ю щ е е с я тем, что множительный блок содержит регистр промежуточных значений, три сумматора, узел управления множительного блока, два управляющих триггера, входы и выходы которых соединены с соответствующи- ми входами и выходами узла управления множительного блока, информационный вход которого соединен с выходом третьего сумматора, первый и второй входы которого соединены с выходами пер.вого и второго сумматоров соответственно, при этом выход регистра промежуточных значений соединен с первымивходами первого и второго .сумматорови промежуточный регистр, вход которого соединен с информационным выхоо дом узла управления множительного блока, первый выход которого соединен свходом регистра прОмежуточных значений и первым управляющим входом первого сумматора, второй выход - с первым управляющим входом второго сумматора, третий выход - с первым управляющим входом третьего и вторым управляющим входом второго сумматоров, четвертый выход - с вторым управляющим20 входом первого и вторым управляющимвходом третьего сумматоров, а пятыйвыход - с входом установки единицытретьего разряда первого сумматора,при этом первый вход множительного25 блока соединен с вторым входом пер-ового сумматора, второй вход - стретьим входом регистра промежуточных значений и вторым входом второгосумматора, третий вход - с первымзо входом узла управления множительного блока, четвертый вход - с вторымвходом узла управления множительного блока, пятый вход - с вторымвходом регистра промежуточных значений и третьим входом третьего сумма,тора, шестой вход - с третьим входомузла управления множительного блока, седьмой вход - с четвертым входомузла управления множительного блока,40 а выход множительного. блока соединенс выходом вспомогательного регистра.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРй 541168, кл. О 06 Г 7/38, 1974.2. Авторское свидетельство СССРМ 425175 кл. 6 06 Г 7/38, 1972888106 с седьмыми входами множительных блоков.Другим отличием предлагаемого устГройства является то, что в нем множи"тельные блоки содержат регистр промежуточных значений, три сумматора,узел управления множительного блока, два управляющих триггера, входыи выходы которых соединены с соответствующими входами и выходами узлауправления множительного блока, информационный вход которого соединенс выходом третьего сумматора, первый и второй входы которого соединены с выходами первого и второгосумматоров соответственно, выход регистра промежуточных значений соеди нен с первыми входами первого и второго сумматоров, вспомогательный регистр, вход которого соединен с информационным выходом узла управлениямножительного блока, первый выход которого соединен со входом регистрапромежуточных значений и первым управляющим входом первого сумматора,второй выход соединен с первым управляющим входом второго сумматора,третий выход узла управления множительного блока соединен с. первым управляющим входом третьего и вторымуправляющим входом второго сумматоров,а четвертый выход соединен со вторымуправляющим входом первого и вторымуправляющим входом третьего сумматоров, Пя 1 ый выход узла управлениямножительного блока соединен с входом установки единицы третьего разряда первого сумматора. Первый входмножительного блока соединен со вторым входом первого сумматора, второйвход - с третьим входом регистра промежуточных значений и вторым входомвторого сумматора, третий вход - спервым входом узла управления множительного блока. Четвертый вход множительного блока соединен со вторымвходом узла управления множительного блока, пятый вход - со вторымвходом регистра промежуточных значений и третьим входом третьего сумматора, шестой вход - с третьим входом узла управления множительногоблока, седьмой вход - с четвертымвходом узла управления множительногоблока, а выход - с выходом вспомогательного регистра.На чертеже изображена структурная схема устройства для возведенияв степень,4Устройство содержит блок управления 1, содержащий 2 о-разрядный распределитель сигналов 2 (где о - разрядность результата) и пятиразрядныйраспределитель сигналов 3. Кроме того,в состав устройства входит 2 о-разрядный регистр 4 операнда (Х), имеющийцепи сдвига вправо на один разряд иобладающий свойствами многовходово О го реверсивного счетчика, триггер исходного состояния 5 и и одинаковыхмножительных блоков 6 (где и+1 - максимальная разрядность операнда у),.В каждом множительном блоке 6 ре 1 э гистр 7 промежуточных значений, имеющий цепи сдвига вправо на один разряд, и обладающий свойствами многовходового реверсивного счетчика, связан со входами накаплиаающих сумматоров 8 и 9, выходы которых подключены ко входам накапливающего сумматора 10, имеющего цепи сдвига влевона один разряд. Причем регистр 7 исумматоры 8, 9 и 10 имеют соответственно по 2 о+1, 2 о+3, 2 о+2, 20+6разрядов, и поскольку разрядностиуказанных узлов не совпадают, товходы остальных старших разрядоввсюду соединены с выходом первого ц (знакового) разряда. Для удобствапервыми всюду будем считать старшие(левые)разряды. В каждом 1-м (11- и) множительном блоке б выходыраспределителя 2 циклическим сдвигомвлево на 4(1- 1) разряда соединенысо входами регистра 7. Аналогичновыходы 2 1-х разрядов распределителя2= 1, 2, , с) связаны с -мивходами сумматора 9. Входы сумматора8 подключены к выходам регистра 4,Выход пятого разряда распределителя3 подключен к цепям сдвига регистров4,7 и сумматора 10,узел 11 управлениямножительного блока реализует следующую систему переключательных функций.ээ,л" агу,ла 1 Ъ,г" агь,гаюаг 4 а 17 (аг 91 аэрлчагд,г а 1 г)а 24 г а 1 т (аг 01 аэлча 29,2. аэрг)щ 1 - агэ,1 а 1 ащ 1. ао,л чаил а,аг 91 аэо,гЫ Ъг= аа,а 16" аг 9 л аэР,лЧИЯВаг 9, авэо,2.Гз 61 аг 4 л ,а 1 ч алв) аг 91аэогэы амг (ал 1 алв ) аг 91а мгЬ,1 - аа 4,1 (аНЧа 1 В) аг 91,аэо,гэ,г = аг 4,г(аНЧа 1 Е) а 29,1 аГЯ ( а г 4 цча 24 г )д г 9 га эо гГэ,л = агу Иг 9,г аэо,лГэ 9 л = аале= а 14.(а 29,лба цг)40,2 14(аМЗ агг) аг,г аЗо,1411= а 1 Я агь 1(а 2 т,1 а 2 ВгчаИ,г а 29,1) 1412= Г 4 г,г= аюВ (агт 1 аг чагтг агв,г)42,1= 18 ж,А 2 М В,г, 2 т,2 28,1 где индексы аргументов и функций совпадают с номерами входов и выходов узла 11 управления множительного блока. Выходная информация формируется на выходах 12,13.К его входу 14 разряда подключен выход 2 -го разряда распределителя 2, входы 15- 18 связаны с выходами четырех первых. разрядов распределителя 3. Входная шина 19 операнда У и входные шины 20 , 20операнда Х и выходные шины 21 А, 22 (1-1)-го блока 6 соединены соответственно со входами 22, 231, 232 и 241, 242. Выходы трех старших разрядов сумматора 1 О подключены ко входам 25, -271, с входами 28, 29 и 30, связаны выходы триггера 5 и выходы управляющих триггеров 31 и 32 данного множительного блока. Выход 33 узла 11 первого множительного ,блока 6 соединен с управляющим вхо"дом регистра 4. Кроме того, выходы 34 всех множительных блоков 6 подведены к управляющим входам сумматоров 9 и 10, а к управляющим входам сумматоров 8 и 10 подключены выходы 35. С управляющими входами сумматора 9 также связаны выходы 36. Выходы 37 ,соединены с управляющими входами регистра 7 и сумматора 8. Выход 38 подведен ко входу установки в единицу третьего разряда сумматора 8, ко входам управляющих триггеров 31 и 32 подключены соответственно выходы 39 и 404, а выходы 12, 13 связаны со входами вспомогательного регистра 41, выходы которого соединены с выходными шинами 214 и 21промежуточного результата данного множительного блока 6.Принцип действия устройства для возведения в степень заключается в том, что в каждом множительном блоке 6 происходит возведение в квадрат промежуточного результата, и при необходимости домножение на Х, т.е. например, возведение числа Х в степень У = 13 осуществляется по формуле Е = х)х") х ) х 1. Поэтому в зависимости от значения соответствующей цифры операнда У каждый множительный блок 6 может работать в одном иэ трех режимов:1) возведение промежуточного результата в квадрат; 2) возведение промежуточного результата в квадрат и умножение на Х;3) умножение на единицу.Тот или иной режим работы 1-гомножительного блока 6 задается состоянием его управляющих триггеров 31 и32, в которых в исходном состояниизаписаны соответственно 0 и 1. Наст 1 Оройка каждого 1-го множительногоблока осуществляется триггером исходного состояния 5 и (1+1)-й цифройоперанда У, поступающей в (1- 1)-мцикле по входной шине 19 в инверсномкоде, Третьему режиму соответствуетнулевое состояние управляющих триггеров. Он применяется, когда операнд Усодержит нули в старших разрядах. Вэтом .случае в первых блоках 6, числокоторых равно числу нулей в старших 20разрядах, происходит передача цифроперанда Х с входных шин на выходныебез изменения, но с задержкой, равнойзадержке появления результата на выходе при первых двух режимах. Перваяединица числа У устанавливает в единицу триггер .исходного состояния 5,который в последующих тактах устанавливает в единицу триггеры 31остальных множительных блоков 6, Зф и в зависимости от того, какое значение 0 или 1 принимает каждая последующая, записываемая в триггер 32 цифра,операнда У, данный блок 6 настраивает-.ся для работы соответственно в первом 35 или во втором режиме. Таким образом, работу устройствадля возведения в степень можно пояснить, рассмотрев работу одного множительного блока 6.В исходном состоянии ( цепи установки исходного состояния на чертежене показаны во всех регистрах и сум"маторах записаны О, а управляющие 43триггеры 31 и 32 находятся в состоянии, задающем определенный режим, пос.кольку каждый множительный блок 6настраивается на определенный режимраньше, чем на него поступают остальные операнды. В каждом К-м такте %0-го цикла в блоке управления 1 единица 1 в 2-м разряде распределителя2 и в Е-м разряде распределителя 3.При этом на входные шины 204 и 202 визбыточном двоичном коде с цифрами1, О, 1 поступают очередные цифрыоперанда Х и промежуточного результата имеющие вес соответственно 2и 2 " ф , где 1 - номер множительно-)+Ф И888106 0000000000001000 0100000000 Р,с,00100 1000000 010100000еюе в 000000000000 000000100000 00000100000000 00000101000000 м, 9м. 1 О 000 10000000 0010010000 го блока 6, Причем +1 соответствуетналичие сигнала на шине 201, - 1 - наличие сигнала на шине 20 г., а нулькодируется отсутствием сигнала наобеих шинах.1 При работе блока 6 в первом режиме в каждом цикле цифрапринимаемая на входные шины 21 с помощью узла 11 управления множительного блока управляет в третьем такте суммированием содержимого. сумматора 10 с кодом сумматора 9, а во втором и четвертом такте - суммированием содержимого сумматора 9 с кодом распределителя 2, таким образом, что к укаэанным сумматорам прибавляется прямой код, если принимаемая цифра равна 1, либо до-: полнительный код, если принимаемая цифра равна 1, Код сумматора не изменяется, если принимаемая цифра равна нулю.Если блок 6 настроен для работы во втором режиме, то вышеописанным образом цифра, принимаемая на входные шины 20 управляет в первом такте прибавлением к сумматору 10 содержимого сумматора 9 и прибавлением к сумматору 8 содержимого регистра 7 ( в первом блоке 6 эта цифра управляет так, же приемом кода распределителя 2 на регистр 4 ), а цифра, принимаемая на входные шины 21, управляет в третьем такте приемом на сумматор 10 кода сумматора 8 и кодафрегистра 7 на сумматор 9, а во втором и четвер" том такте - приемом на сумматор 8 кода регистра 4 и кода распределителя 2 на регистр 7 8Когда множительный блок 6 настроен для работы в третьем режиме, вовтором такте осуществляется установка в 1 третьего разряда сумматора 8,если принимаемая по шинам 21 цифраравна 1 или 1. В третьем такте так,как описаны выше, эта цифра управляет сложением содержимого сумматора10 с кодом сумматора 8.0 Кроме того, независимо от режима. в четвертом такте узел 11 управлениямножительного блока, анализируя трипервых разряда сумматора 10, формирует очередную цифру следующего проме 13 жуточного результата, и помещает еедля временного хранения в регистр41 (+1 формируется, когда в трехстарших разрядах записано 001 или010, а -1 - при записи 110 или 101,20 в остальных случая будет сформирован01. 8 пятом такте происходит сдвигна два разряда вправо распределителя, сигналов 2, сдвиг вправо на один разряд регистров 4 и 7 и сдвиг на один25 разряд влево содержимого сумматора10, Причем при сдвиге в сумматоре 10значение третьего разряда переписывается не только во второй, но и впервыи разряд,зю Работа устройства для возведенияв степень на числовом примере иллюстрируется таблицами, составленнымидля первого множительного блока 6,номеру режима работы которого соответствует номер таблицы, где черезх, а - ббозначены цифры, поступающиепо входным шинам 20 и через 2 - цифры, выдаваемые из блока по выходнымшинам 21.,с. 2г. 4ф 0110000 См, 8 00000000000 00 ООООООООО 00010000000 00001000000 Рг. 4 См. 8 000000000 0001100000 См,00000000000000 00000000000000 00000009000000 00000010000000 00000001000000 См. 9 0000011000000 М Рг. 7 Р.с. Рг 7 ооооооаоо ОО 1 ОООООО 001000000 + 00000000000 000000000 000010000 00101000000011000000 П р и и е ч а н и е: Настоящий пример выполнен для разрядности о = 4, т.е.начиная с пятого цикла, все цифры, принимаемые на вход.вычислительного блока 6 равны нулю. Поэтому, начиная с пятого цикла, содержимое всех регистров и сумматоров данного вычислительного блока, кроме сумматора 10, не может влиять на результат вычислений и в данной таблице не приводится.То же относится к таблицам 2 и 3.888106 Рг. 4 0000100000 00111100 0000100000 0000000000 0001000000 0001010000 Рг. 7 См. 10 См. 8 См. 1 Рг. 7 00000000 001000000 Р.с. 10000000 Г е 0000110000 10010000 0010000000 5 См. Р.с.Рг. 10000 ООО 1 ООО 00110000 00100000 01000000 4 цикл акт ци Рг. 4 0011000 00001 ОО 11111 Л 1 00000 Рг. 4 011000 См. 10 См.Рг.С См. 8 Рг. 4 См. 8 001000000ооооеооооооо 00000001000000 00000001000000 00001000000 00001000000 000010000000 0010010000000000000000 00100100000