Устройство для возведения в степень Советский патент 1981 года по МПК G06F7/38 

Изобретение относится к области цифровой вычислительной техники и мо жет быть использовано в ЦВМ и специализированных устройствах. Известно устройство для возведения в степень fl, содержащее группу сумматоров, dчeтчик блoки сдвига и устройстве управления. Недостатками устройства является относительно низкое быстродействие и значительное увеличение объема аппар туры при увеличении показателя степен Наиболее близким к изобретению решением данной технической задбчи является устройство 2, содержащее группу однотипных последовательно соединенных множительных блоков, блок управления, шины аргумента и ре гистр операнда, выходы которого соединены с первыми входами множительны блоков, первый вход соединен с первым выходом блока управления и со вт рыми входами множительных блоков. Недостатками известного устройства являются относительно невысокое быстродействие, связанное с невозможностью вычислять разряды резуль- тата во время, когда на вход устройства поступили еще не все разряды аргументов и, большая сложность устройства. Целью изобретения является повышение быстродействия. Цель изобретения достигается тем, что устройство содержит триггер исходного состояния, вход которого соединен с шиной показателя степени и третьими входами множительных блоков, четвертые входы которых соединены с выходом триггера исходного состояния. Второй и третий выходы блока управления соединены с пятым и шестым входами множительных блоков. Второй вход регистра операнда соединен с выходом первого множительного блока, шины аргумента соединены 3 с седьмыми входами множительных блоДругим отличием предлагаемого ус ройства является то, что в нем множи тельные блоки содержат регистр промежуточных значений, три сумматора, узел управления множительного блока, два управляющих триггера, входы и выходы которых соединены с соответ ствующими входами и выходами узла управления множительного блока, информационный вход которого соединен с выходом третьего сумматора, первый и второй входы которого соединены с выходами первого и второго сумматоров соответственно, выход регистра промежуточных значений соединен с первыми входами первого и второго сумматоров, вспомогательный регистр, вход которого соединен с информационным выходом узла управления множительного блока, первый выход ко торого соединен со входом регистра промежуточных значений и первым управляющим входом первого сумматора, второй выход соединен с первым управляющим входом второго сумматора, третий выход узла управления множительного блока соединен с. первым управляющим входом третьего и вторым управляющим входом второго сумматоро а четвертый выход соединен со вторым управляющим входом первого и вторым управляющим входом третьего сумматоров. ПяУый выход узла уг авления множительного блока соединен с входом установки единицы третьего разряда первого сумматора. Первый вход NfHOKHTenbHoro блока соединен со вторым входом первого сумматора, второй вход - с третьим входом регистра про межуточных значений и вторым входом второго сумматора, третий вход - с. первым входом узла управления множительного блока. Четвертый вход мно ительного блока соединен со вторым входом узла управления множительного блока, пятый вход - со вторым входом регистра промежуточных значений и третьим входом третьего сум матора, шестой вход с третьим вхо дом узла управления множительного блока, седьмой вход - с четвертым входом узла управления множительног блока, а выход - с выходом вспомогательного регистра. На чертеже изображена структурная схема устройства для возведения в степень. Устройство содержит блок управления 1, содержащий 2q-paзpядный распределитель Сигналов 2 (где q - разрядность результата) и пятиразрядный распределитель сигналов 3- Кроме того, в состав устройства входит 2q-paзpядный регистр It операнда (Х;, имеющий цепи сдвига вправо на один разряд и обладающий свойствами многовходового реверсивного счетчика, триггер исходного состояния 5 и п одинаковых множительных блоков 6 (где п+1 - максимальная разрядность операнда у). В каждом множительном блоке 6 регистр 7 промежуточных значений, имеющий цепи сдвига вправо на один разряд, и обладающий свойствами многовходового реверсивного счетчика, связан со входами накапливающих сумматоров 8 и 9, выходы которых подключены ко входам накапливающего сумматора 10, имеющего цепи сдвига влево на один разряд. Причем регистр 7 и сумматоры 8, 9 и 10 имеют соответственно по 2q+1, 2q+3, 2q+2, 2q+6 разрядов, и поскольку разрядности указанных узлов не совпадают, то входы остальных старших разрядов всюду соединены с выходом первого (знакового) разряда. Для удобства первыми всюду будем считать старшие (левые)разряды. В каждом i-м (i 1-п) множительном блоке б выходы распределителя 2 циклическим сдвигом влево на t(i-l) разряда соединены со входами регистра 7. Аналогично выходы 2J-X разрядов распределителя 2(j 1, 2, ..., q) связаны с j-ми входами сумматора 9- Входы сумматора 8 подключены к выходам регистра . Выход пятого разряда распределителя 3подключен к цепям сдвига регистров ,7 и сумматора 10,узел 11 управления множительного блока реализует следующую систему переключательных функций. 23, 3,2 325Д-а И 24, гч,1 30,V329,2 34,2 2V 17 329, %,1 ZM 9,1- 9o,. °2,1°зо,а )Sfl. 323Д-,15 ZP, Ззо, аг9,1- Чо.г 36,1 14,4 Г 329,1 ЪО.-i ьь,г- a24,iaij,)-a2(),i. Эзод V}, - 32.4, ( ) 57,2 a2.4(a ivafe)-a29,i-a5oi, 38 (,2 3:29,2-а50Д f3V -aa.i-ajoH. f3q.2 a4Q.i (a2Q.4va,o,2) 4о,г 4 it Z-2.,2 o,l , 18 25,1 ( 27,1 9202 3272- ) W 42 918( 320) иг, 19- .r e0,,z- 2e,f Ь где индексы аргументов и функций сов падают с номерами входов и выходов узла 11 управления множительного блока Выходная информация формируется на выходах 12,13.К его входу 1 разряда подключен выход 2-го разряда распределит ля 2, входы 15-18 связаны с выходами четырех первых разрядов распределителя 3. Входная шина 19 операнда Y и входные шины 20., 202 операнда X и выходные шины 21, 222 (i-l)-ro ° соединены соответственно со входами 22, 23, 232. и , . Выходы трех старших разрядов сумматора 10 подключены ко входам 2Sj-27j, с входами 28 29 и 30, связаны выходы триггера 5 и выходы управляющих триггеров 31 и 32 данного множительного блока. Выход 33 узла 11 первого множительного ,блока 6 соединен с управляющим входом регистра 4. Кроме того, выходы 3 всех множительных блоков 6 подведе ны к управляющим входам сумматоров 9 и 10, а к управляющим входам сумматоров 8 и 10 подключены выходы 35. С управляющими входами сумматора 9 также связаны выходы 36. Выходы 37 соединены с управляющими входами регистра 7 и сумматора 8. Выход 38 подведен ко входу установки в единицу третьего разряда сумматора 8, ко входам управляющих триггеров 31 и 32 подключены соответственно выходы ЗЭ и Q, а выходы 12, 13 связаны со входами вспомогательного регистра tl, выходы которого соединены с выходными шинами 21 и212. промежуточного результата данного множительного блока 6. Принцип действия устройства для возведения в степень заключается в том, что в каждом множительном блоке 6 происходит возведение в квадрат промежуточного результата, и при необходимости домножение на X, т.е. например, возведение числа X в степень Y 13 осуществляется по формуле Z (((х)хЯ)х . Поэтому в зависимости от значения соответствующей цифры операнда Y каждый множитель ный блок 6 может работать в одном из трех режимов: 1J возведение промежуточного результата в квадрат; 2)возведение промежуточного результата в квадрат и умножение на Х , 3)умножение на единицу. Тот или иной режим работы i-ro множительного блока 6 задается состоянием его управляющих триггеров 31 и 32, в которых в исходном состоянии записаны соответственно О и 1. Настройка каждого i-ro множительного блока осуществляется триггером исходного состояния 5 и (+1)-й цифрой операнда Y, поступающей в (i-1)-м цикле по входной шине 19 в инверсном коде. Третьему режиму соответствует нулевое состояние управляющих триггеров. Он применяется, когда операнд Y содержит нули в старших разрядах. В этом случае в первых блоках 6, число которых равно числу нулей в старших разрядах, происходит передача цифр операнда X с входных шин на выходные без изменения, но с задержкой, равной задержке появления результата на выходе при первых двух режимах. Первая единица числа Y устанавливает в единицу триггер исходного состояния 5, который в последующих тактах ус;танавливает в единицу триггеры 31 остальных множительных блоков 6, и в зависимости от того, какое значение О или 1 принимает каждая последующая, записываемая в триггер 32 цифра« операнда Y, данный блок 6 настраивает-w ся для работы соответственно в первом или во втором режиме. Таким образом, работу устройства для возведения в степень можно пояснить, рассмотрев работу одного множительного блока 6. В исходном состоянии (цепи установки исходного состояния на чертеже не показаны} во всех регистрах и сумматорах записаны О, а управляющие триггеры 31 и 32 находятся в состоянии, задающем определенный режим, поскольку каждый множительный блок 6 настраивается на определенный режим раньше, чем на него поступают остальные операнды. В каждом k-м такте 6-го цикла в блоке управления 1 единица 1 в 26-м разряде распределителя 2 и в k-M разряде распределителя 3. При этом на входные шины 20 и 20 в избыточном двоичном коде с цифрами 1,0, 1 поступают очередные цифры перанда X и промежуточного результата, имеющие вес соответственно 2 , где i - номер множительного блока 6. Причем +1 соответствует аличие сигнала на шине 20., -1 - наичие сигнала на шине 20, а нуль кодируется отсутствием сигнала на

беих шинах.

I

При работе блока 6 в первом режиме в каждом цикле цифрапринимаемая на входные шины 21 с помощью узла 11 правления множительного блока управляет в третьем такте суммированием содержимого,сумматора 10 с кодом сумматора 9 а во втором и четвертом такте - суммированием содержимого сумматора 9 с кодом распределителя 2, таким образом, что к указанным сумматорам прибавляется прямой код, если прияимаемая цифра равна 1, либо дополнительный кодг если принимаемая цифра равна 1. Код сумматора не изменяется, если принимаемая цифра равна нулю.

Если блок 6 настроен для работы во втором режиме, то вышеописанным образом цифра, принимаемая на входные шины 20 управляет в первом такте прибавлением к сумматору 10 содержимого сумматора 9 и прибавлением к сумматору 8 содержимого регистра 7 (в первом блоке 6 эта цифра управляет также приемом кода распределителя 2 на регистр ), а цифра, принимаемая на входные шины 21, управляет в третьем такте приемом на сумматор 10 кода сумматора 8 и кодарегистра 7 на сумматор 9 а во втором и четвертом такте - приемом на сумматор 8 кода регистра k и кода распределителя 2 на регистр 7.

Когда множительный блок 6 настроен для работы в третьем режиме, во втором такте осуществляется установка в 1 третьего разряда сумматора 8,

если принимаемая по шинам 21 цифра равна 1 или 1. В третьем такте так, как описаны выше, эта цифра управляет сложением содержимого сумматора 10 с кодом сумматора 8.

Кроме того, независимо от режима в четвертом такте узел 11 управления множительного блока, анализируя три первых разряда сумматора 10, формирует очередную цифру следующего промежуточного результата, и помещает ее для временного хранения в регистр 1 (+1 формируется, когда в трех старших разрядах записано 001 или 010, а -1 - при записиЧЮ или 101,

в остальных случая будет сформирован 0. В пятом такте происходит сдвиг на два разряда вправо распределителя сигналов 2, сдвиг вправо на один разряд регистров j и 7 и сдвиг на один

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

Работа устройства для возведения в степень на числов.ом примере иллюстрируется таблицами, составленными для первого множительного блока 6, номеру режима работы которого соответствует номер таблицы где через X, а - обозначены цифры, поступающие по входным шинам 20 и через Z - цифры, выдаваемые из блока по выходным шинам 21.

Таблица 1

9

t z

См. 9 P.С. 2 См. 9

10

.888106 Продолжение таблицы 1

3

о

0101000000 000100

опооооооо

5 См. 10 р.с. 2

Такт

00010010000000

00000100000000 0010 0100

цикл

3 цикл

t1

7 цикл

Такт 3 См, 10 k Z 5 См. 10 примеча Такт 1 X Рг. k Р.с. 2 Рг. Ц См. 8 Рг, ti : См. 8 См. 10 См. 9 См. 10

000000000 f 001000000

001000000

юоооооооооо

888106

12

Продолжение табл. 1

9 цикл

000000000 000010000 001010000

-00011000000 1111001000000011100100000000 ОО 1110010000000011001000000000 Настоящий пример выполнен для разрядности q Ц, т.е. начиная с пятого цикла, все цифры, принимаемые на вход, вычислительного блока 6 равны нулю. Поэтому, начиная с пятого цикла, содержимое всех регистров и сумматоров данного вычислительного блока, кроме сумматора 10, не может влиять на результат вычислений и в данной таблице не приводится. То же относится к таблицам 2 и 3. 0100000000110000 0000000000000010000000 f-f0000000000000001000000OOObbdObOOOOOOIIOQOOOO 0000000000000000000010000000 00000000000000 00000001000000 ООООООО&ОООООО00000011000000 Таблица 2 1 цикл2 цикл 1 1 0000000000100000 f401000000-00010000

IS

88810616

Продолжение таблицы 2

17

Такт

2

00101001100110

3 См. 10

k Z

11010011001100

5 См, 10

Такт

2

Такт

00100110011000

3 См. 10

k Z

11001100110000

5 См. 10

10 8 10

88810618

Продолжение таблицы 2

6 цикл

5 цикл

11010011001100

00100110011000

8 цикл

7 цикл

8 цикл

7 цикл

11001100110000

00011001100000

Таблица 3

00000000000000

00001000000000 00000100000000 00000100000000 00001100000000 00000100000000

19

00001000000000

5 См. 10

Такт

5 цикл

00011000000000

10 В 00000000000000 00011000000000 10 цо 5 См. 1000110000000000 Такт5 цикл 3 См. 1011011000000000 ) ц Z1 5. См. 1000110000000000 Такт7 цикл 3 См. 1011100000000000 ц Zо « - «« - .« - 5 См. 10110000000000

Как видно из примеров, задержка появления на выходе блока 6 соответствующих цифр результата не зависит от разрядности q и составляет 4 цикла т.е. при любом q, в каждом В-м цикле (С « 1, 2, ....q+i), когда на входные шины 21 поступает цифра с весом , на выходных шинах 21 формируется очередная цифра результата, имеющая вес . Следовательно, полный результат на выходе всего устройства будет получен после приема

888106

20 - Продолжение табл. 3

0011000000000

00110000000000

11111100000000 00101100000000

последней цифры операнда X с задержкой на время Т knJ, тогда как аналогичная задержка для известного устройства составляет Т, Т«....+ Т....,

- , л. Оич fVl

febW Я П Ри разрядности q операнда X, равной 36, и разрядности (п+1) операнда Y, равной 5, означает сокращение времени получения результата не менее, чем в 16 раз.

Если же сравнивать все время работы устройства от приема первой цифры аргумента до выдачи последней 1 11011000000000 6 цикл 00110000000000 1 11100000000000 8 цикл 11000000000000 1 н - - 0000000000000

2J

цифры результата, то получим, что дл указанной разрядности предлагаемое устройство превосходит по быстродействию известное в 9,2 раза.

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

Формула изобретения

шины аргумента и регистр операнда, выходы которого соединены с первыми входами множительных блоков, первый вход соединен с первым выходо блока управления и с вторыми входами iнoжитeльныx блоков, отличающееся тем, что, с целью увеличения быстродействия и сокращения количества оборудования, оно содержит триггер исходного состояния, вхо которого соединен с шиной показателя степени и третьими входами множительных блоков, четвертые входы которых соединены с выходом триггера исходного состояния, при этом второй и третий выходы блока управления соединены с пятым и шестым входами множительных блоков, второй вход регистра операнда соединен с выходом первого множительного блока, шины аргумента соединена с седьмыми входами множительных блоков.

06

22

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

Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № , кл. G 06 F 7/38, 197.

2. Авторское свидетельство СССР № 425175, кл. G Об F 7/38, 1972 (прототип.