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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1718217 А 05 6 06 Р 7/552 САНИЕ ИЗОБРЕТЕ при 1. =2 ОСУДАРСТВЕ ННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССР М 1246092, кл. 6 06 Е 7/552, 1986,Авторское свидетельство СССР М 1383343, кл, 6 06 Р 7/552, 1986.(54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В СТЕПЕНЬ(57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных устройствах обработки цифровой информации для вычисления функции А. Цель изобретения - повышение быстродействия. Цель достигается благодаря тому, что в устройство, содержащее блоки 313-2 возведения в степень (к - количество одновременно анализируемых разрядов показателя степени),комм таторов 4, .-1 умножителей,1 2 а)Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных устройствах обработки цифровой информации функции АБИзвестно устройство для возведения в степень, содержащее регистр аргумента, а шифраторов произведений разрядов аргументов (а - разрядность аргумента), в коммутаторов, шифратор показателя степени, сумматор и шифратор,Недостатком известного устройства является большие затраты оборудования.Наиболее близким к заявляемому является устройство для возведения в степень, содержащее 2" - 2 блоков возведения в степень (М - количество анализируемых разрядов показателя степени в одном вычислительном блоке, коммутатор,вы- числительных блоков (1:К где гп - показатель степени), каждый из которых содержит 2 +1 регистров, коммутатор, блок возведения в 2 степень и умножитель, причем вход основания степени устройства соединен с входами блоков возведения в степень, с вторым входом коммутатора и с входом первого регистра корректирующего множителя первого вычислительного блока, вход регистра результата которого соединен с выходом коммутатора, первый выход которого соединен с входом логической "1", Е старших разрядов входа показателя степени устройства соединены с управляющим входом коммутатора устройства, выход ( - 2)-го (1=1, 2, , 2 ) блока возведения в степень соединен с -м информационным входом коммутатора и входом ( - 1)-го регистра корректирующего множителя первого вычислительного блока, оцггп+1 - 1 младших разрядов входа показателя степени устройства соединены с входом регистра показателя степени первого вычислительного блока, в каждом)-м =1, 2, , 1 ) вычислительном блоке Е старших разрядов регистра показателя степени соединены с управляющим входом коммутатора блока, первый информационный вход которого соединен с входом логической "1" устройства, выход ( - 1)-го регистра корректирующего множителя соединен с 1-м информационным входом коммутатора блока и входом ( - 1)-го регистра корректирующего множителя )+1)-го вычислительного блока, выход коммутатора блока соединен с первым входом умножителя, выход регистра результата соединен с входом блока возведения в 2 -ю степень, выход которого1( подключен к второму входу умножителя, вы множителей 10причем входы/2 умножителей первой ступени являются входами матрицы, а выходы соединены с входами/4 умножителей второй ступени матрицы, выход умножителя й"5 й ступени соединен с выходом матрицы,вход основания степени устройства соединен с вторыми информационными входами второго 1:го коммутаторов, управляющие входы которых соединены соответст 20 венно с одноименными группами разрядов 5 10 15 20 25 30 ход которого соединен с входом регистра результата Ц+1)-го вычислительного блока, выхода 1 оцга)+1 - Д+1)к младших разрядов регистра показателя степени соединены с входом регистра показателя степени )+1)-го вычислительного блока, синхровходы всех регистров подключены к тактовому входу устройства, выход умножителя :го вычислительного блока является выходом устройства.Быстродействие данного устройства для случая, когда операнды поступают не массивами, определяется временем прохождения информации через устройство и равно Т 1=Цср 2+1 б+сумн) где ср 2 - время записи информации в регистр; то - время задержки информации на блоке возведения в Степень; 1 у - время умножения.Целью изобретения является увеличение быстродействия.Цель достигается тем, что в устройство для возведения в степень, содержащее =1 У ( = ),гдеа -1(щ 2 в)показатель степени; 1 - количество одновременно анализируемых разрядов в группе, 2 -2 блоков частных результатов1(возведения в степень икоммутаторов, причем вход основания степени устройства соединен с входами блоков частных результатов возведения в степень и с вторым информационным входом первого коммутатора, первые информационные входы всех коммутаторов соединены с входом логической "1" устройства, 1 младших разрядов входа показателя степени устройства соединены с управляющим входом первого коммутатора, (+2)-й вход которого (1=1, 2, , 2 - 2) соединен с выходом -го блока частных результатов возведения в степень, введены =1 блоков возведения в степень корректирующих множителей, а 1 - 1 умножителей объединены в древовидную матрицу, состоящую из В ступеней умножителей5 10 15 20 35 40 45 бра 50 55 50 показатель степ блок 7 умножен жителей 8.Вход 1 осно входами блоков 3 входами коммута входы которых логической "1". вания степени сое1, 32, 3(2 К - 2) и Сторов 41, 42, , 41.оединены с потеВыход 1-го блока 3 динен с торы ми первые циалом соедивхода показателя степени устройства, выход 1-го блока частичных результатов возведения в степень (1=1, 22 - 2) соединен с (1+2)-и информационными входами 2, . :го коммутаторов,. выход 0+1)-го коммутатора =1, 2, , 1:1) соединен с входом )-го блока возведения в степень корректирующего множителя, выход которого соединен с О+1)- м входом матрицы, первый вход которой соединен с выходом первого коммутатора, выход матрицы является выходом устройства.Сущность изобретения по сравнению с прототипом заключается в увеличении быстродействия, которое достигается за счет распараллеливания процесса возведения в степень,Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием новых блоков возведения в степень корректирующих множителей и умножителей, объединенных в древовидную матрицу с их связями, Таким образом заявляемое устройство соответствует критерию "новизна",Сравнение заявляемого устройства с другими техническими решениями показывает, что блок возведения в степень, коммутаторы, умножители и регистры широко известны.Однако при введении в устройство блоков возведения в степень корректирующих множителей и умножителей, объединенных в древовидную матрицу в указанной связи, вышеуказанные элементы позволяют распараллелить процесс возведения в степень, что ведет к повышению быстродействия, Это позволяет сделать вывод о соответствии технического решения критерию "существенные отличия".На фиг. 1 представлена функциональная схема устройства для возведения в степень; на фиг. 2 - схема блока умножения.Устройство содержит вход 1 основания степени, вход 2 показателя степени, блоки 31, 32, , 3(2-2) возведения в степень (Е - количество одновременно анализируемых разрядов показателя степени), коммутаторы 41, 424 ь, блоки 51, 52, , 51.- возведе 1 ОС)22 в )ния в степень (. =, где в -Кени), выход 6 устройства, ия, содержащий 1-1 умнонен с (+2)-м входом коммутаторов 41, , 41 1=1, 22 К - 2), к младших разрядов входа 2 показателя степени соединены с управляющими входами коммутатора 4, 1 следующих по величине разрядов входа 2 соединены с управляющими входами коммутатора 42 и т.д. Старшие М разрядов входа 2 соединены с управляющими входами коммутатора 41, выход Ц+1)-го коммутатора 41+1 Ц=1, 2, , 1=1) соединен с входом)-го блока 5), выходы коммутатора 41 и выходы блоков 51, 52, , 5-1 соединены с входами блока 7 умножения, Входы блока 7 соединены с входами умножителей 81, 8 2, , 8 1/К, выходы ко 1 торых соединены с входами умножителей 8 1, 8 22 8 /4 выходыг Умножителей 8 1, 8 2, ., 8 /4 соездинены с входами умножителей 8 1, 8 2, ,3 8 1/8 и т.д, Выход умножителя 8 1 сое- динен 021. При 1.=2В ЯКоц 1.+1 г 1 Ри с 2 с выходом б устройства. В предлагаемом устройстве используется алгоритм возведения числа А в п-ю степень, при котором выполняются следующие операции: показатель степени разбивается справа налево на 1 групп по 11 ось 2 т ) разрядов в каждой ( 1 = дляК каждой)-й группы Д=1,2, 1) определяется частный результат возведения в степень, равный возведению в 2 Щ) степень )-го корректирующего множителя, который является результатом возведения числа А в степень, равную числу, записанному в )-й группе; вычисления произведения частных результатов возведения в степень.Устройство работает следующим о зом,Основание степени с входа 1 поступает на входы блоков 31, , 32-2, где в каждом (1-2)-м (1=1, 2, , 2 К) блоке Зь 2 оно возводится в (1-1)-ю степень. Результаты возведения числа А в 0,12 - 1 степени поступают на входы коммутаторов 441., На управляющие входы )-го коммутатора 4) поступают 1 разрядов )-ой группы показателя степени, которые управляют переключением коммутатора 4; так, что при нуле на управляющем входе на выход поступает информация с первого входа, при единице - информация с второго входа и т.д. На выходах )-го коммутатора получают )-й корректирующий множитель, который поступает на О)-й блок 51-1 возведения в степень, В каждом- 1)-м блоке 51-1)-й корректирующий мно,рДО 2.1 м Зфк 40 50 Щ - 1)житель возводится в 2" ) степень, т.е. на выходе блока 5;-1 получают )-1 частный результат возведения в степень, Частные результаты возведения в степень поступают на блок 7 умножения, который представляет собой древовидную матрицу умножителей 8. На выходе блока 7 получают произведение, которое является результатом возведения числа А в п-ю степень,Быстродействие данного устройства определяется временем прохождения информации с входа 2 основания степени на выход 6 устройства, т.е, временем Т 2=21 б+1 ком+В Лумн.где ском - время задержки информации на коммутаторе.По сравнению с прототипом в предложенном устройстве быстродействие повышено вТ 1 1 ( тр 2 + 1 д + гумн )раз)Т 2 тд + тком + Йгумн Формула изобретения Устройство для возведения в степень,содержащее 1 - 1 умножителей,где т - показатель степень; К - количество одновременно анализируемых разрядов в группе), 2 -2 блоков частичныхкрезультатов возведения в степень и 1 коммутаторов, причем вход основания степени устройства соединен с входами блоков частичных результатов возведения в степень и с первым информационным входом первого коммутатора, вторые информационные входы всех коммутаторов соединены с входом логической "1" устройства, К младших разрядов входа показателя степени устройства соединены с управляющим входом первого коммутатора, (1+2)-й вход которого (1=1, 2, , 5 2 - 2) соединен с выходом 1-го блока частич 1(ных результатов возведения в степень, о тл и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены 1 - 1 блоков возведения в степень корректирую щих множителей, а 1=1 умножителей объединены в древовидную матрицу, состоящую из В ступеней умножителей Я=Во 1. при 1.=2й3,0 Ц 21.+1 ПРи 1. 2вхо ы 1/2 множителей пе во причем д у р и ступени являются входами матрицы, а выходы соединены с входами 1 /4 умножителей вто рой ступени матрицы, выход умножителя йй ступени соединен с выходом матрицы, вход основания степени устройства соединен с первыми информационными входами 1-го коммутатора (1=2, 3, , 1), управляющие 25 входы которых соединены соответственно содноименными группами разрядов входа показателя степени устройства, выход 1-го блока частичных результатов возведения в степень (1=1, 2, ., 2 ) соединен с (1+2)-и 30 информационными входами)-го=1,2, ., )коммутатора, выход О+1)-го коммутатора =1, 2, ,1 - 1) соединен с входом)-го блока возвращения в степень корректирующего множителя, выход которого соединен с +1)- 35 м входом матрицы, первый вход которойсоединен с выходом первого коммутатора, выход матрицы является выходом устройства.1718217 4 ставитель А.Мельн Корректор М.Пожо Редактор Т.Юрчико оргентал ехре Производственно-издательский комбинат "Патент", г, Ужгород, ул, Гагарина Заказ 882 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5