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

 

Союз Советскик

Соцнапнстнчвскнк

Республик

О П И С А Н И Е (>888106

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22)Заявлено 140676 (21) 2372594/18-24 (51)М. Кл.

G 06 F 7/38 с присоединением заявки М (23) Приоритет

Веудеретюнвй кеввтет сФФр ае аваев взебретееи6 в еткрытв11 (53) УДК 681.325. (088. 8) Опубликовано 07.12.81. бюллетень М 45

Дата опубликования описания 07.1231

В.И. Жабин, В.И. Корнейчук, В.П. Тар и А.А. Щербина (72) Авторы изобретения

Киевский ордена Ленина политехническ им. 50-летия Великой Октябрьской соц революции (7l) Заявитель (54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В СТЕПЕНЬ

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

Известно устройство для возведения в степень t,lj, содержащее rpynny сумматоров, Счетчик блоки сдвига и устройство управления.

Недостатками устройства является относительно низкое быстродействие и значительное увеличение объема аппара10 туры при увеличении показателя степени.

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

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

Цельа изобретения является повышение быстродействия.

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

888106 с седьмыми входами множительных блоков.

Другим отличием предлагаемого устl ройства является то, что в нем множи" тельные блоки содержат регистр промежуточных значений, три сумматора, узел управления множительного блока, два управляющих триггера, входы и выходы которых соединены с соответствующими входами и выходами узла управления множительного блока, информационный вход которого соединен с выходом третьего сумматора, первый и второй входы которого соединены с выходами первого и второго сумматоров соответственно, выход регистра промежуточных значений соеди нен с первыми входами первого и второго сумматоров, вспомогательный регистр, вход которого соединен с информационным выходом узла управления множительного блока, первый выход которого соединен со входом регистра промежуточных значений и первым управляющим входом первого сумматора, второй выход соединен с первым управляющим входом второго сумматора, третий выход узла управления множительного блока соединен с первым управляющим входом третьего и вторым управляющим входом второго сумматоров, а четвертый выход соединен со вторым управляющим входом первого и вторым управляющим входом третьего сумматоров. Пя1ый выход узла управления множительного блока соединен с входом установки единицы третьего разряда первого сумматора. Первый вход множительного блока соединен со вторым входом первого сумматора, второй вход — с третьим входом регистра промежуточных значений и вторым входом второго сумматора, третий вход - с первым входом узла управления множительного блока. Четвертый вход множительного блока соединен со вторым входом узла управления множительного блока, пятый вход - co вторым входом регистра промежуточных значений и третьим входом третьего сумматора, шестой вход - с третьим входом узла управления множительного блока, седьмой вход - с четвертым входом узла управления множительного блока, а выход - с выходом вспомогательного регистра.

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

Устройство содержит блок управления 1, содержащий 2q-разрядный распределитель сигналов 2 (где q - разрядность результата) и пятиразрядный распределитель сигналов 3. Кроме того, в состав устройства входит 2q-разрядный регистр 4 операнда (X), имеющий цепи сдвига вправо на один разряд и обладающий свойствами многовходовоto ro реверсивного счетчика, триггер исходного состояния 5 и и одинаковых множительных блоков 6 (где и+1 - максимальная разрядность операнда у),.

В каждом множительном блоке 6 регистр 7 промежуточных значений, имеющий цепи сдвига вправо на один разряд, и обладающий свойствами многовходового реверсивного счетчика, связан со входами накапливающих сумматоров 8 и 9, выходы которых подключены ко входам накапливающего сумматора 10, имеющего цепи сдвига влево на один разряд. Причем регистр 7 и сумматоры 8, 9 и 10 имеют соответственно по 2q+1, 2q+3, 2q+2, 2q+6 разрядов, и поскольку разрядности указанных узлов не совпадают, то входы остальных старших разрядов всюду соединены с выходом первого ц (знакового) разряда. Для удобства первыми всюду будем считать старшие (левые)разряды. В каждом i-м (i

1- и) множительном блоке б выходы распределителя 2 циклическим сдвигом влево на 4(i- t) разряда соединены со входами регистра 7. Аналогично выходы 2J-х разрядов распределителя

2 (J = 1, 2, ..., q) связаны с j-ми входами сумматора 9. Входы сумматора

8 подключены к выходам регистра 4.

Выход пятого разряда распределителя

3 подключен к цепям сдвига регистров

4,7 и сумматора 10,узел 11 управления множительного блока реализует следующую систему переключательных функций. 33,щ- a23, a<6 "М,г - аг3,z аю

,1 аг4 а (а q аур чагдг а )

,г а4г a (azey аюср аг9,г- аз,г) 391 Щ 15 а29,1 30,4 М,1 р с аю,1 зов агз,г.. а15 а19 . а9о1" И,г. ю

Ой9,e ъод

f < И,4 1 16Ча в).агч . алло

f3sg= аг4, (а1 ча е) age,1 ажz

f ö< = a <4, (a«V а Я ) а гр 1 ° a 3p 2

f>> г = а Ай(анчаре) aze, a3p,< щ = (agq4чаг4,г) agq,z asap à

f39,4= а18,4 а14 а29,1 а304 . иz = алел= а 4-(агя, ча3оz) 888106 4о, = а 14 (aug>" a ) a 7$ g a 3o,1 41,1 = Я аг$, (a т,1 аМ v а И, - Л,1 )

412 = 4 У = э15 (aZ71 aZ8, ча; 2- а ф2 )

41у 1 = 18 2$p4(2Те 1 ф6,2 аут z 29,4 ) где индексы аргументов и функций совпадают с номерами входов и выходов узла 11 управления множительного блока.

Выходная информация формируется на выходах 12,13.К его входу 14 разряда подключен выход 2 -го разряда распределителя 2, входы 15- 18 связаны с выходами четырех первых. разрядов распределителя

3. Входная шина 19 операнда Y и входные шины 20, 20 операнда Х и выходные шины 21А, 22 (i-1)-го блока 6 соединены соответственно со входами

22, 23, 232 и 241, 24Z. Выходы трех старших разрядов сумматора 10 подключены ко входам 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 и 2lg промежуточного результата данного множительного блока 6.

Принцип действия устройства для возведения в степень заключается в том, что в каждом множительном блоке 6 происходит возведение в квадрат промежуточного результата, и при необходимости домножение на Х, т.е. например, возведение числа Х в степень Y = 13 осуществляется по формуле 2 = (((х) х") х ) х". Поэтому в зависимости от значения соответствующей цифры операнда Y каждый множительный блок 6 может работать в одном иэ трех режимов:

1) возведение промежуточного результата в квадрат;

2) возведение промежуточного результата в квадрат и умножение на Х;

3) умножение на единицу.

Тот или иной режим работы i-ro множительного блока 6 задается состоянием его управляющих триггеров 31 и

32, в которых в исходном состоянии записаны соответственно О и 1. Наст1О ройка каждого i-го множительного блока осуществляется триггером исходного состояния 5 и (1+1)-й цифрой операнда У, поступающей в (i- 1)-м цикле по входной шине 19 в инверсном

1$ коде. Третьему режиму соответствует нулевое состояние управляющих триггеров. Он применяется, когда операнд Y содержит нули в старших разрядах. В этом .случае в первых блоках 6, число которых равно числу нулей в старших

ie разрядах, происходит передача цифр операнда Х с входных шин на выходные без изменения, но с задержкой, равной задержке появления результата на вы2$ ходе при первых двух режимах. Первая единица числа У устанавливает в единицу триггер .исходного состояния 5, который в последующих тактах ус танавливает в единицу триггеры 31 остальных множительных блоков 6, $в и в зависимости от того, какое значение О или 1 принимает каждая последующая, записываемая в триггер 32 цифра, операнда У, данный блок 6 настраивает-. ся для работы соответственно в первом

$$ или во втором режиме.

Таким образом, работу устройства для возведения в степень можно пояснить, рассмотрев работу одного множительного блока 6.

В исходном состоянии (цепи установки исходного состояния на чертеже не показаны) во всех регистрах и сум" маторах записаны О, а управляющие

4$ триггеры 31 и 32 находятся в состоянии, задающем определенный режим, поскольку каждый множительный блок 6 настраивается на определенный режим раньше, чем на него поступают остальные операнды. В каждом k-м такте

$0

0-го цикла в блоке управления 1 единица 1 в 2 -м разряде распределителя

2 и в k-м разряде распределителя 3.

При этом на входные шины 20 и 20 в избыточном двоичном коде с цифрами

1, О, 1 поступают очередные цифры операнда Х и промежуточного результата имеющие вес соответственно 2 и 2 ", где i — номер множительно-1+4 (1-Ф2

888106

См. 9

001000

000100

P.ñ, 2

См. 9

0010000000

0101000000

3 См. 10

См. 9

См. 10

ОООООООООООООО

00000010000000

00000101000000 оооооо 1оааоооо

00001001000000 го блока 6. Причем +1 соответствует наличие сигнала на шине 201, - 1 - наличие сигнала на шине 20, а нуль кодируется отсутствием сигнала на обеих шинах.

При работе блока 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.

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

10 с кодом сумматора 8.

14 Кроме того, независимо от режима в четвертом такте узел 11 управления множительного блока, анализируя три первых разряда сумматора 10, формирует очередную цифру следующего промеIS жуточного результата, и помещает ее для временного хранения в регистр

41 (+1 формируется, когда в трех старших разрядах записано 001 или

010, à -l - при записи 110 или 101, йз в остальных случая будет сформирован

02. 8 пятом такте происходит сдвиг на два разряда вправо распределителя, сигналов 2, сдвиг вправо на орин разряд регистров 4 и 7 и сдвиг на один

25 разряд влево содержимого сумматора

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

1О.888106

0110000000

0100000000

0010

0100

4 цикл

3 цикл

Такт

0101110000

0110000000

4 z

0101100000

См. 9

1000

0001

6 цикл

5 цикл

Такт

5 См. 10

См. 9

P.Ñ. 2

См. 9

5 См. 10

P.Ñ. 2

См. 9

P.ñ. 2

См. 9

3 См. 10

См.- 9

См. 10

См. 9

P.с. 2

5 См. 10

P.ñ 2

3 См 10

4 г

001000

00000100000000

000000

00000000000000

00010010000000

000000

0010010000000

00111 100100000

111l1001000000

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

000100

00010010000000

1 11111

11111010010000

00011110010000

11lll1

00111100100000

11111001000000

11110010000000

888106

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

g цикл

7 цикл

Такт

3 См. 10

11100100000000

4 z I1001000000000

5 См. 1О

11100100000000

П р и и е ч а н и е: Настоящий пример выполнен для разрядности q = 4, т.е. начиная с пятого цикла, все цифры, принимаемые на вход. вычислительного блока 6 равны нулю. Поэтому, начиная с пятого цикла, содержимое всех регистров и сумматоров данного вычислительного блока, кроме сумматора 10, не может влиять на результат вычислений и в данной таблице не приводится.

То же относится к таблицам 2 и 3.

Т а б л и ц а 2

Рг. 4

Р.с. 2

Рг. 4

01000000

00100000 00010000

00110000

См. 8

Рг. 4

См. 8

См, 10

См. 9

См. 10

Ф

00000000000

00001000000

00000000000

00011000000

00000000000000

00000001000000

00000009000000

00000011000000

2 а

Рг. 7

Р.с. 2

Pr. 7

См.8

001000000

001010000

+ 00000000000

+ 00011000000

888106. 13

Рг, 4

См. 8

0001000000

000!010000

3 См. 9

0010010000

0001000000

См. 8

См. 10

4 z

Рг. 7

000010000

00!000000

001000000

P.ñ. 2

001100000

Рг. 7

010000000

См. 8

Рг. 4

См. 8

Такт

4 цикл

3 цикл

J30011000

00000000

1 Рг. 4

00001 DO

11111 Л l

P.ñ. 2

Pr. 4

00011000

00001011

См. 8

Рг. 4

Pr. 7

См. 9

См. 10

5 См. 10

P.с. 2.

Pr. 4

Рг. 7

См. 8

См. 10

+ 00001000000

00001000000 оооооооооооооо

00000001000000

00000001000000

О0001О00000

00001000000

00010000000

001000000

00000000000

00100100000

+ 00001101100000

l4

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

+00000!00000

00011110000

000000!1110000

00000110110000

00000110000

00100100000

0О001101100000

00000!00

0001!000

000110000

11111101000

00100001000

@00 01 1 01 1 000000

888106

3 цикл

4 цикл

Такт

См. 9

См, 10

2 а

11 11 11 11 1

000000000

Рг. 7

P.ñ. 2

Рг. 7

000010111

000110000

См. 8

Рг. 4 м. 8

0000000000

1111101001

3См. 9

0001111001.

0010010000

00001011 1

111111111

000010110

000110000

5 См.

P.ñ. 2

Pr. 4

Pr, 7

Рг. 7

См. 9

См. 10

См. 8

См. ТО

Рг. 7

Рс. 2

Рг. 7

См. 8

Рг. 4

См. 8

+.00000000000000

00001101100000

00000000000

OO 1 00100000

00000000000000

00001 101100000

Ф

000000000

00000000000

00100100000

00000001

000011000

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

+ 11111101110000

00011000110000

11111110101

00011111101

ll111100000011

00010100110011

00011111101

11111110101

00011110010

00000101

000001011

888106

6 цикл

Такт

5 цикл

3 См. 10

4 z

5 См. 10

8 цикл

7 цикл

Такт

8 цикл

Такт

7 цикл

3 См. 10

5 См. 10 м.

См. 8

См. 10

17

0010100» 00110

»0100»00»00

00100» 00» 000

» 0O»00»0000

00000100000000

00000100000000

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

t 1010011001100

00100110011000

11001100110000

0001100» 00000

Таблица 3

000001 00000000

00001100000000

888106

0011000000000

00001000000000

5 См. 10

Такт

6 цикл

5 цикл

00» 0000000000

» ll1100000000

000»000000000

00000000000000

3 См. 10

См. 8

0010» 00000000

000 »000000000

См. 10

11011000000000

00110000000000

5 См. 10

6 цикл

5 цикл

Такт

»0»000000000

3 См. 10

00 »0000000000 l

00»0000000000

» 100000000000

5. См. 10

8 цикл

7 цикл

Такт

» 000000000000

1 »00000000000

3 См. 10

4 z

0000000000000

5 См. 10

» 0000000000

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

2 < 41, на выходных шинах 21 формируется очередная цифра результата, имеющая вес 2 (-41. Следовательно, полный результат на выходе всего устройства будет получен после приема

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

Г последней цифры операнда Х с задержкой на время Т1= 4пТ, тогда как аналогичная задержка для известного устройства составляет Т Т1, + Т

TSHv+ оТп, При разрядности q операнда Х, равной 36, и разрядности (и+1) операнда У, равной 5, означает сокращение времени получения результата не менее, чем в 16 раз, Если же сравнивать все время работы устройства от приема первой цифры аргумента до выдачи последней

21

888106

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

Помимо увеличения быстродействия

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

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

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

N 541168, кл. G 06 F 7/38, 1974.

2. Авторское свидетельство СССР

NÃ 425175 кл. G 06 F 7/38, 1972 (прототип).