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

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 7/552

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

СО

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4607028/24 (22) 22.11.88 (46) 07.03.92. Бюл. N. 9 (72) А. А. Мельник и И. Г. Цмоць (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 1246092, кл. G 06 F 7/552, 1986, Авторское свидетельство СССР

М 1383343, кл. G 06 F 7/552, 1986. (54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В

СТЕПЕНЬ (57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных устройствах обработки цифровой информации для вычис.. Ж 1718217А1 ления функции А. Цель изобретения — повышение быстродействия. Цель достигается благодаря тому, что в устройство, содержащее блоки 31...3к-z возведения в степень (к — количество одновременно анализируемых разрядов показателя степени), L .комм таторов 4, L-1 умножителей, ! 2m) (L=

К где m — показатель степени, введены L-1 блоков возведения в степень корректирующих множителей, а L-1 умножителей объединены в древовидную матрицу, состоящую из R ступеней умножителей с соответствующими связями

R (гО 21 -ПРЙ 1.. - 2

Я=

R (Lo >L)+1 при L>2 ил, 1718217

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

ABl

Известно устройство для возведения в степень, содержащее регистр аргумента, m шифраторов произведений разрядов аргументов (m — разрядность аргумента), m коммутаторов, шифратор показателя степени, сумматор и шифратор, Недостатком известного устройства является большие затраты оборудования.

Наиболее близким к заявляемому является устройство для возведения в степень, содержащее 2" — 2 блоков возведения в степень (k — количество анализируемых разрядов показателя степени в одном вычислительном блоке, коммутатор, L вычислительных блоков (1=

К где m — показатель степени), каждый из которых содержит 2 +1 регистров, коммутаk тор, блок возведения в 2 степень и умножитель, причем вход основания степени устройства соединен с входами блоков возведения в степень, с вторым входом коммутатора и с входом первого регистра корректирующего множителя первого вычислительного блока, вход регистра результата которого соединен с выходом коммутатора, первый выход которого соединен с входом логической "1", k старших разрядов входа показателя степени устройства соединены с управляющим входом коммутатора устройства, выход (i — 2)-го (i=1, 2, ..., 2 ) блока возведения в степень соединен с

i-м информационным входом коммутатора и входом (i — 1)-го регистра корректирующего множителя первого вычислительного блока, (logjam)+1 — k младших разрядов входа показателя степени устройства соединены с входом регистра показателя степени первого вычислительного блока, в каждом j-м (j=1, 2, ..., 1 ) вычислительном блоке k старших разрядов регистра показателя степени соединены с управляющим входом коммутатора блока, первый информационный вход которого соединен с входом логической "1" устройства, выход (i — 1)-го регистра корректирующего множителя соединен с i-м информационным входом коммутатора блока и входом (i — 1)-го регистра корректирующего множителя (j+1)-го вычислительного блока, выход коммутатора блока соединен с первым входом умножителя, выход регистра результата соединен с входом блока возведения в 2 -ю степень, выход которого

k подключен к второму входу умножителя, вы о

По Д+" п и L >

15 вход основания степени устройства соединен с вторыми информационными входами второго, ..., (=го коммутаторов, управляющие входы которых соединены соответст20 венно с одноименными группами разрядов

5 ход которого соединен с входом регистра результата (j+1)-го вычислительного блока, выхода (logjam)+1 — (j+1)k младших разрядов регистра показателя степени соединены с входом регистра показателя степени (j+1)-ro вычислительного блока, синхровходы всех регистров подключены к тактовому входу устройства, выход умножителя L-го вычислительного блока является выходом устройства.

Быстродействие данного устройства для случая, когда операнды поступают не массивами, определяется временем прохождения информации через устройство и равно Tt=L(tp2+t6+tyMa) где срт — время записи информации в регистр; ta — время задержки информации на блоке возведения в

Степень; tyMH — время умножения.

Целью изобретения является увеличение быстродействия.

Цель достигается тем, что в устройство для возведения в степень, содержащее L — 1 (1Оф2 m ) умножителей (L= ), где пав показатель степени; k — количество одновременно анализируемых разрядов в группе, 2 — 2 блоков частных результатов

k возведения в степень и L коммутаторов, причем вход основания степени устройства соединен с входами блоков частных результатов возведения в степень и с вторым информационным входом первого коммутатора, первые информационные входы всех коммутаторов соединены с входом логической "1" устройства, k младших разрядов входа показателя степени устройства соединены с управляющим входом первого коммутатора, (i+2)-й вход которого (i=1, 2, ..., 2 — 2) соединен с выходом i-го блока частных

k результатов возведения в степень, введены

L — 1 блоков возведения в степень корректирующих множителей, а L — 1 умножителей объединены в древовидную матрицу, состоящую из R ступеней умножителей причем входы L/2 умножителей первой ступени являются входами матрицы, а выходы соединены с входами L/4 умножителей второй ступени матрицы, выход умножителя Rй ступени соединен с выходом матрицы, 1718217 входа показателя степени устройства, выход i-го блока частичных результатов возведения в степень (i=1, 2, ..., 2 — 2) соединен с (+2)-и информационными входами 2, .;; L-го коммутаторов,. выход (j+1)-го коммутатора (j=1, 2, ..., 1=1) соединен с входом j-ro блока 5 возведения в степень корректирующего множителя, выход которого соединен с(j+1)м входом матрицы, первый вход которой соединен с выходом первого коммутатора, выход матрицы является выходом устройст- 10 ва.

Сущность изобретения по сравнению с прототипом заключается в увеличении быстродействия, которое достигается за счет распараллеливания процесса возведения в степень, 15

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

Однако при введении в устройство блоков возведения в степень корректирующих 40 множителей и умножителей, объединенных в древовидную матрицу в указанной связи, вышеуказанные элементы позволяют распараллелить процесс возведения в степень, что ведет к повышению быстродействия, 45

Это позволяет сделать вывод о соответствии технического решения критерию "существенные отличия".

На фиг. 1 представлена функциональная схема устройства для возведения в сте- 50 пень; на фиг. 2 — схема блока умножения.

Устройство содержит вход 1 основания степени, вход 2 показателя степени, блоки

31, Зг, ..., Зр -г) возведения в степень (k— количество одновременно анализируемых 55 разрядов показателя степени), коммутаторы 4>, 4г...„4i, блоки 51, 5г, ..., 5i-1 возведе(1ос)г2 m ) ния в степень (! =, где m—

К показатель степени), выход 6 устройства, блок 7 умножения, содержащий L — 1 умножителей 8.

Вход 1 основания степени соединен с входами блоков 31, Зг. „„Зр -z) и с вторыми входами коммутаторов 4, 4г, ..., 4, первые входы которых соединены с потенциалом 50 логической "1". Выход i-ro блока ЗЛ соедиФ нен с (!+2)-м входом коммутаторов 41, ..., 4i

i=1, 2...„2k — 2), k младших разрядов входа 2 показателя степени соединены с управляющими входами коммутатора 41, k следующих по величине разрядов входа 2 соединены с управляющими входами коммутатора 4г и т.д. Старшие k разрядов входа 2 соединены с управляющими входами коммутатора 4i, выход (j+1)-го коммутатора 4j+1 (j=1, 2, ..., 1=1) соединен с входом j-го блока 5), выходы коммутатора 41 и выходы блоков 5>, 5г, ..., 5i-1 соединены с входами блока 7 умножения, Входы блока 7 соединены с входами умножителей 81, 8 г, ..., 8 i/R, выходы ко1 1 1 торых соединены с входами умножителей 8 1, 8 гг...,, 8 /4 выходы г умножителей 8 1, 8 г, ..., 8 б/4 соединены с входами умножителей 8 1, 8 г, ..., 3

8 i/8 и т.д. Выход умножителя 8 1 соединен (0)21 при 1.-2

R= (Сog,L)+t прп L>2 с выходом 6 устройства.

В предлагаемом устройстве используется алгоритм возведения числа А в m-ю степень, при котором выполняются следующие операции: показатель степени разбивается справа налево íà L групп по k (!оаа т) разрядов в каждой (1 = для

К каждой j-й группы (j-1, 2, „„L) определяется частный результат возведения в степень, равный возведению в 2k0-1) степень j-го корректирующего множителя, который является результатом возведения числа А в степень, равную числу, записанному в j-й группе; вычисления произведения частных результатов возведения в степень.

Устройство работает следующим образом, Основание степени с входа 1 поступает на входы блоков 31, ..., Зг -г, где в каждом (i-2)-м (i=1, 2, ..., 2k) блоке Зьz оно возводится в (i-1)-ю степень. Результаты возведения числа А в 0,1,...,2 — 1 степени поступают на

k входы коммутаторов 4>...Д 4г. На управляющие входы j-го коммутатора 4j поступают k разрядов j-ой группы показателя степени, которые управляют переключением коммутатора 4> так, что при нуле на управляющем входе на выход поступает информация с первого входа, при единице — информация с второго входа и т.д. На выходах j-го коммутатора получают j-й корректирующий множитель, который поступает на (j-1)-й блок 5>-1 возведения в степень, B каждом (j — 1)-м блоке 5)-ц-й корректирующий мно1718217 ((ДО 2. L м 3 ф

50

٠— 1) житель возводится в 2 " ) степень, т.е. на выходе блока 5>-1 получают j-1 частный результат возведения в степень, Частные результаты возведения в степень поступают на блок 7 умножения, который представляет собой древовидную матрицу умножителей

8. На выходе блока 7 получают произведение, которое является результатом возведения числа А в m-ю степень.

Быстродействие данного устройства определяется временем прохождения информации с входа 2 основания степени на выход 6 устройства, т.е. временем

T2=2t0+tzoM+R Лумн. где ском — время задержки информации на коммутаторе.

По сравнению с прототипом в предложенном устройстве быстродействие повышено в

Т1 L (тр2 + 55 + гумн ) раз)

Тр 2 тд + тком + R гумн

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

Устройство для возведения в степень, содержащее L — 1 умножителей, где m —; k — количество одновременно анализируемых разрядов в группе), 2 -2 блоков частичных

k результатов возведения в степень и L коммутаторов, причем вход основания степени устройства соединен с входами блоков частичных результатов возведения в степень и с первым информационным входом первого коммутатора, вторые информационные входы всех коммутаторов соединены с входом логической "1" устройства, k младших разрядов входа показателя степени устройства соединены с управляющим входом первого коммутатора, (i+2)-й вход которого (i=1, 2, ..., 5 2 — 2) соединен с выходом i-ro блока частичk ных результатов возведения в степень, о тл и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены L — 1 блоков возведения в степень корректирую10 щих множителей, à L— - 1 умножителей объединены в древовидную матрицу, состоящую из R ступеней умножителей

R=

К при L=2

R (1,оц211+1 при L> 2 вхо ы L/2 множителей пе во причем д у р и ступени являются входами матрицы, а выходы соединены с входами L/4 умножителей вто20 рой ступени матрицы, выход умножителя Rй ступени соединен с выходом матрицы, вход основания степени устройства соединен с первыми информационными входами

i-го коммутатора (i=2, 3, ..., L), управляющие

25 входы которых соединены соответственно с одноименными группами разрядов входа показателя степени устройства, выход i-го блока частичных результатов возведения в степень (i=1, 2, ..., 2 ) соединен с (i+2)-и

30 информационными входами j-го ()=1, 2, „., L) коммутатора, выход (j+1)-го коммутатора (j=1 2, ..., 1.— 1) соединен с входом j-го блока возвращения в степень корректирующего множителя, выход которого соединен с (j+1)35 м входом матрицы, первый вход которой соединен с выходом первого коммутатора, выход матрицы является выходом устройства.

1718217

Щг2

45

Составитель А.Мельник .Техред М.Моргентал

Корректор М.Пожо

Редактор Т.Юрчикова

Заказ 882 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", r, Ужгород, ул,Гагарина, 101