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

(51)4 0 06 Р 7/552 ОПИСАНИЕ ИЗОБРЕТЕНИЯ И А 10 СКОМУ ТВИД."ПЛСТВ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ,(.56) Авторское свидетельство СССРУ 1043644, кл. О 06 Р 7/552, 1982.Авторское свидетельство СССР(54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ ВСТЕПЕНЬ(57) Изобретение относится к вычислительной технике и момет быть использовано в специализированных вычислительных машинах н устройствах, Цельизобретения - сокращение оборудования, Устройство содержит генераторы1,2, формирователь импульсов 3, триггеры 4-6, группы 7-9 элементов И, регистры 10-15, распределитель 16 импульсов, умномители 17 и 18, логические элементы 19-22, 1 ил.Изобретение относится к вычиолительной технике и может быть использовано н специализированных вычислительнь 1 х машинах и устройствах. 5Цепь изобретения - сокращениеоборудонанияеНа чертеже представлена структурная схема устройства.Устройство содержит генераторы 1 1 Ои 2 тактовых импульсов, формирователь 3 импульсов, триггеры 4 - 6,группы 7 - 9 элементов И, регистр10 основания степени, регистр 11 показателя степени, регистр 2 1 езультата, буферный регистр 1 3, дополнительные регистры 14 и 15, распределитель 16 импульсов, умножители 17 и18, элемент 19 задержки, элементыИЛИ 20 и 21 и НЕ 22,входы 23-25 и выходы 26 и 27 устройства,В основу работы устройства положен следующий алгоритм.йПусть выполняется операция У = Хгде и - целое, положительное число.В двоичной системе счисленияЮи= 2 а+2 а, 2 ао= П Х 2;а; (2) 35Для вычисления Х " при любом значе нии и необходимо получить те значения членов правой части формулы (2), коэффициенты которой в двоичном предс тавлении числа и по Формуле (1) равны единице, и умножить их друг на друга.Из выражения (2) видно, что каждый предыдущий член может быть получен из последующего путем возведения н квадратПоэтому в предлагаемом устройстве реализуется алгоритм, по которому вычисляются нсе члены выражения (2) последовательно путем возведения в квадрат каждого предыдущего члена и параллельно Формируются частичные произведения лишь из тех членов, а 1, в которых для данного и равно единице.П р и м е р, Пусть и, = 1 О. Т.ог. да двоичная запись и будет п 1 О 1 О, Х = Х Х ХХ Последовательность получения Х" следующая .Справа налево выполняются действия, поступает Х в первой степени, затем происходит проверка наличия едийицы в нулевом разряде - она отсутствует, пронеряется наличие единицы в первом разряде - единица есть. Тогда число Х возводится в квадрат и посылается на устройство формирования промежуточных произведений, Затем проверяется наличие единицы во втором разряде - ее нет, число Х возводится в квадрат и происходит проверка наличия единицы в третьем разряде - единица есть, умножается Х " и квадрат и поступает на устройство формирования промежуточных произведений, где умножается на поступившее ранее Х . Таким обра 2зом, на устройстве формирования промежуточных произведений имеемХ Х = Х Устройство работает следующим образом.В основном состоянии триггеры4 - 6, регистры 11, 14, 15, О и 13устанавливаются в нулевое состояние,распределитель 16 подготавливаетсяк циклическому режиму, а н регистр12 записывается "1",На входы 23 и 25 поступают соответственно числа Х и и, необходимыеПдля вычисления выражения Х . По приходу сигнала запуска устройства повходу 24 триггеры 4 и 5 устанавливаются,в единичное состояние, Причемтриггер 24 отключает через элементыИ 8 вход 25 от входа регистра 1, вкотором оказывается занесенным числои, а триггер 5 подключает через элементы И 7 и элемент ИЛИ 20 число Хрегистра 10. Триггер 4 выводит генератор 1 в автоколебательный режим,Причем в первую половину периода работы генератора 1 (например, по переднему Фронту импульса) осуществляется у.станов триггера 6 н единичноесостояние, а но вторую половину пе"риода (по заднему Фронту импульса)сдвиг числа н регистре 11 на одинразряд н сторону младших р.азрядон.В первую половину работы генератора 1 после взведения триггера 6 осуществляется запуск генератора 2,который обеспечивает серию импульсов дляраспределителя 16, на выходах кото 1434428рого появляются последовательно во времени импульсы, По появлению.им,пульса на четвертом выходе распределителя 16 триггер б переходит в нулевое состояние, генератор 2 останав 5 ливается, а распределитель 16 готовится к формированию новой последовательности импульсов. По сигналу с первоговыхода распределителя 1 б им" пульсов в регистры 14 и 15 заносится число с выхода регистра 10, по второму в умножителе 8 Формируется квадрат числа, находящегося в регистре 10, по третьему результат заносит ся в регистр 10 а по четвертому триггер 5 устанавливается в нулевое состояние, запрещая через элементы И 7 прохождение числа Х в регистр 10, Причем особенностью первого цикла является то, что на втором такте на выходе умножителя 8 Формируется нулевой код, так как в ретистры 14 и 15 были занесены нули, в регистр 10 на третьем такте заносится число Х 25 с входа 23, а триггер 5 линь в первом цикле находится в единичном состоянии потому, что по четвертому такту первого цикла он сбрасывается в "О" и на всех последующих циклах по четвертому такту подтверждается это состояние.Во вторую половину работы генератора 1 число п в регистре 11 сдвигается на один разряд и если в (К+1)-мФ35 разряде оказывается единица, то сигнал, проходя через Формирователь 3, Формирующий краткий сигнал подключения через элементы И 9 второго сомножителя на вход умножителя 17, и элемент 19 задержки (имеющий время задержки больше длительности импульса с формирователя 3), обеспечивает занесение результата вычисления первого цикла в регистр 12. Если в регистре 11 после очередного сдвига числа в сторону мпадших разрядов оказывается нулевая комбинация, то на выходе элемента ИЛИ 21 Формируется сигнал, переводящий триггер 4 в нулевое состояние. На выходе 27 Формируется сиг 50 нал окончания процесса вычисления, генератор 1 останавливается, а в регистре 12 устанавливается окончательньй результат вычислений.Если в (К+1)-м разряде оказыва 551 И ется после очередного сдвига 0 то результат, полученный в регистре 10, не поступает на умножение с пре" дьщущим промежуточным произведением в регистре 12 и используется для Фор" мирования квадрата очередного члена промежуточных произведений.Таким образом, процесс вычисления Х продолжается столько циклов, каково значение разряда числа и, в котором записана единица.Устройство работает и для случая Х = 1, когда триггер 4 после поступления сигнала "Пуск" все-таки запускает генераторы 1 и 2, но промежуточный результат, полученный в регистре 10, не переписывается в регистр 12, а сам триггер 4 на первом же цикле устанавливается в нулевое состояние, индицируя окончание процесса вычисления, В регистре 12 остается ранее занесенная в него единица. Для случая 0"О устройство работает, как описано вышее, и в регистре 12 имеется нулевая комбинация.В случае неопределенности вида о0 в устройстве по общепринятому в машинах вычислениях правилу выдается 1.Формула изобретенияУстройство для возведения в степень, содержащее первый генератор тактовых импульсов, группы элементов И, регистр основания степени,инФормационньтй вход которого подключен к выходу первого элемента ИЛИ, первый вход которого соединен с выходами элементов И первой группы, первые входы которых подключены к входу основания степени устройства, регистр результата, выход которого подключен к входу первого операнда первого умножителя и является выходом результата устройства, регистр показателя степени, информационный вход которого соединен с выходами элементов И второй группы, первые входы элементов И которой подключены к входу по" каэателя степени устройства, о т л ич а ю щ е е с я тем, что, с целью сокращения оборудования, оно содержит второй генератор тактовых импульсов, первый и второй дополнительные регистры, распределитель импульсов, буферный регистр, три триггера, формирователь импульсов, второй элемент ИЛИ, второй умножитель, элемент НЕ и элемент задержки, а регистр показателя степени выполнен сдвиговым,Составитель 11.БородянскийТехред Л.Сердюкова. Корректор А,Обручар Редактор Л.Пчолинская Заказ 5555/50 Тираж 704ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий3035, Москва, Ж, Раушская наб., д. 4/5 Подписно ег Производственно-полиграфическое предприятие, г. ужгород, ул, Проектная, 4 5 ,14 причем вход запуска устройства соединен с входами установки в "1" первого и второго триггеров, прямой выход последнего из которых подключен.к вторым входам элементов И первой группы, выход регистра основания степени подключен к информационным входам первого и второго дополнительных регистров и первым входам элементов И третьей группы, выходы.элементов И которой соединены с входом второго операнда первого умножителя, выход которого через буферный регистр подключен к информационному входу регистра результата, вход разрешения записи которого соединен с выходом элемента задержки, вход которого и вторые входы элементов И третьей группы подключены к выходу Формирователя импульсов, вход которого подключен к (КФ 1)-му входу регистра показателя степени (где К- , число разрядов), выходы которого сое, динены с входами второго элемента ИЛИ инверсный выход которого подклю чен к входу установки в "0" первого ; триггера, прямой выход которого соеди" , ненс входом запуска первого генера 34428 бтора тактовых импульсов, выход кото"рого подключен к входу элемента НЕи входу установки в "1" третьеготриггера, прямой выход которого подключен к входу запуска второго генератора тактовых импульсов, выход которого соединен с входом распределителя импульсов, первый выход которор го соединен с входами разрешения записи первого и второго дополнительных регистров, второй - с входом разрешения записи второго умножителя,третий - с входом разрешения записи 1 регистра основания степени, четвертый - с входами установки в "0" второго и третьего триггеров, выходыпервого и второго дополнительных регистров подключены к входам первого 2 О и второго операндов второго умножи-теля, выход которого соединен с вторым входом первого элемента ИЛИ, выход элемента НЕ подключен к входусдвига регистра, показателя степени, 25 инверсный выход первого триггера соединен с вторыми входами элементов Ивторой группы и выходом окончания вычисления.,устройства.