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

входа показателя степени устройства, выход i-ro блока частичных результатов возведения в степень (, 22-2) соединен с

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

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

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

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

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

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

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

3i, За3(2k-2) возведения в степень (k количество одновременно анализируемых разрядов показателя степени), коммутаторы 4i, 42,..., 4ь блоки 5i, 52,..., SL-I возведе,, Iog22m ния в степень ( L , где m показатель степени), выход 6 устройства, блок 7 умножения, содержащий L-1 умножителей 8.

Вход 1 основания степени соединен с

входами блоков 3i, 323(2к-2) и с вторыми

входами коммутаторов 4i, 42, .... 4i, первые входы которых соединены с потенциалом логической 1. Выход i-ro блока 3.i соеди0

нен с (+2)-м входом коммутаторов 4i4i

, 22k-2), k младших разрядов входа 2

показателя степени соединены с управляющими входами коммутатора 4i, k следующих по величине разрядов входа 2 соединены с управляющими входами коммутатора 42 и т.д. Старшие k разрядов входа 2 соединены с управляющими входами коммутатора 4ц

выход 0+1Н° коммутатора 4j+1 , 2

L-1) соединен с входом j-ro блока 5j, выходы

коммутатора 4i и выходы блоков 5i, 62

5ы соединены с входами блока 7 умножения. Входы блока 7 соединены с входами умножителей 8i1, 81281i /R, выходы которых соединены с входами умножителей

5

821,

8

,- -2- умножителей 8 1,828 L/4 соедине8У4

выходы

эЗ

ны с входами умножителей 8 1, 82, ..., 83i/8 и т.д. Выход умножителя 8R1 сое

динен

R

Log2L. при log2L +l при

5

0

5

0

с выходом 6 устройства.

В предлагаемом устройстве используется алгоритм возведения числа А в т-ю степень, при котором выполняются следующие операции: показатель степени разбивается справа налево на L групп по k

- IOQ22 m разрядов в каждой (L для

каждой j-й группы , 2L) определяется

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

Устройство работает следующим образом.

Основание степени с входа 1 поступает на входы блоков 3i, ..., 32k-2, где в каждом

(i-2)-M (, 22k) блоке 3i-2 оно возводится

в (И)-ю степень. Результаты возведения

5 числа А в 0,12k-1 степени поступают на

входы коммутаторов 4i4t. На управляющие входы j-ro коммутатора 4j поступают k разрядов j-ой группы показателя степени, которые управляют переключением коммутатора 4j так, что при нуле на управляющем входе на выход поступает информация с первого входа, при единице - информация с второго входа и т.д. На выходах j-ro коммутатора получают j-й корректирующий множитель, который поступает на (j-1)-v блок 5j-i возведения в степень. В каждом )-м блоке Sj-ij-й корректирующий мно0

житель возводится в 2k 1 степень, т.е. на выходе блока 5j-i получают j-1 частный результат возведения в степень. Частные результаты возведения в степень поступают на блок7умножения, который представляет собой древовидную матрицу умножителей 8. На выходе блока 7 получают произведение, которое является результатом возведения числа А в m-ю степень.

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

T2 2t6+tKOM+R.tyMH.

где Ткем - время задержки информации на коммутаторе.

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

Ti L ( tp2 + + tyMH )

Т, 2 t(5 + tKOM + R tyMH

{раз)

Формула изобрете.ния Устройство для возведения в степень, содержащее L-1 умножителей,

/ I CfyiiMl ) К,

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

0

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

Log2L при

log2L +l при причем входы L/2 умножителей первой ступени являются входами матрицы, а выходы соединены с входами L/4 умножителей второй ступени матрицы, выход умножителя R- й ступени соединен с выходом матрицы, вход основания степени устройства соединен с первыми информационными входами 1-го коммутатора (, 3, .... L), управляющие

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

информационными входами j-го (,2L)

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

I

I

u

40 45

50

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

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