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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах.Цель изобретения - сокращение оборудования . Устройство содержит генераторы 1,2, формирователь импульсов 3, триг- . геры 4-6, группы 7-9 элементов И, регистры 10-15, распределитель 16 импульсов , умножители 17 и 18, логические злементы 19-22. 1 ил.

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

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

РЕаЪБЛИК

„„SU„„1434428 А I (51)4 6 06 F 7/552

OllHCAHHE ИЗОБРЕТЕНИЯ

К АВтОеСиОМЧ СеидЬткЛьотвм

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4185273/24-24 (22) 20.01 87 (46) 30.10.88, Бшл. У 40 (71) Таганрогский радиотехнический институт им, В.Д.Калмыкова (72) В.Ф.Арсени и M.Е,Бородянский (53) 681.325 (088.8) ,(56) Авторское свидетельство СССР

У 1043644, кл. G 06 F 7/552, 1982.

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

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

СТЕПЕНЬ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах, Цель изобретения — сокращение оборудования, Устройство содержит генераторы

l,2, формирователь импульсов 3, триггеры 4-6, группы 7-9 элементов И, регистры 10-15, распределитель 16 импульсов, умномители 17 и 18, логические элементы 19-22. ) ил.

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

Цепь изобретения - сокращение

Оборудонанияе

На чертеже представлена структурная схема устройства. устройство содержит генераторы 1 !0 и 2 тактовых импульсов, формирователь 3 импульсов, триггеры 4 - 6, группы 7 — 9 элементов И, регистр

10 основания степени, регистр ll показателя степени, регистр !2 фезуль- !5 тата, буферный регистр 1 3, дополнительные регистры 14 и 15, распределитель 16 импульсов, умножители 17 и

18, элемент 19 задержки, элементы

ИЛИ 20 и Zl и НЕ 22,входы 23-25 и вы- 20 ходы 26 и 27 устройства, В основу работы устройства положен следующий алгоритм.

Пусть выполняется операция У = Х где п - целое, положительное число.

В двоичной системе счисления

1 !с-1 Ю

n= 2 а +2 а, +...+2 ао, (1) где коэффициенты а;(» =- 0,1,2,...,K) равны нулю или единице.

Формулу можно представить в виде

Х = Х2 а„Х2 -а„...,X2 а к

П Х2;а; (2) 35

Для вычисления Х" при любом значе нии п необходимо получить те значения членон правой части формулы (2), коэффициенты которой в двоичном предс- 40 тавлении числа п по формуле (1) равны единице, и умножить их друг на друга.

Из выражения (2) видно, что каждый предыдущий член может быть полу-45 чен из последующего путем вознедения н квадрат °

Поэтому в предлагаемом устройстве реализуется алгоритм, по которому вычисляются нсе члены выражения (2) последовательно путем возведения в квадрат каждого предыдущего члена и параллельно формируются частичные произведения лишь из тех членов, а в которых для данного и равно единице.

Пример, Пустьn, =10. Тогда двоичная запись и будет п

1010 Х = Х Х сХ1 Х2о

Последовательность получения Х" следующая .

Справа налево выполняются действия, поступает Х в первой степени, затем происходит проверка наличия едийицы в нулевом разряде — она отсутствует, пронеряется наличие единицы в первом разряде — единица есть. Тогда число Х возводится в квадрат и посылается на устройство формирования промежуточных произведений. Затем проверяется наличие единицы во втором разряде — ее нет, число Х возводится в квадрат и происходит проверка наличия единицы в третьем разряде — единица есть, умножается Х " в квадрат и поступает на устройство формирования промежуточных произведений, где умножается на поступившее ранее Х . Таким обра2 зом, на устройстве формирования промежуточных произведений имеем

Х2 . ХЭ Х100

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

В основном состоянии триггеры

4 — 6, регистры 11, 14, 15, 10 и 13 устанавливаются в нулевое состояние, распределитель 16 подготавливается к циклическому режиму, а н регистр

12 записывается "1", На входы 23 и 25 поступают соответственно числа Х и п необходимые

h для вычисления выражения Х . По приходу сигнала запуска устройства по входу 24 триггеры 4 и 5 устанавливаются,в единичное состояние. Причем триггер 24 отключает через элементы

И 8 вход 25 от входа регистра 11, в котором оказывается занесенным число п а триггер 5 подключает через элементы И 7 и элемент ИЛИ 20 число Х регистра 10. Триггер 4 выводит генератор 1 в автоколебательный режим, Причем в первую половину периода работы генератора 1 (например, по переднему фронту импульса) осуществляется у:станов триггера 6 н единичное состояние, а но вторую половину пе" риода (по заднему фронту импульса) сдвиг числа н регистре 11 на один разряд н сторону младших р.азрядон.

В первую половину работы генератора 1 после взведения триггера 6 осуществляется запуск генератора 2,который обеспечивает серию импульсов для распределителя 16, на выходах кото! 434428 рого появляются последовательно во времени импульсы, По появлению-им,пульса на четвертом выходе распределителя 16 триггер 6 переходит в нулевое состояние, генератор 2 останав.5 ливается, а распределитель 16 готовится к формированию новой последовательности импульсов. По сигналу с первого выхода распределителя 16 импульсов в регистры 14 и 15 заносится число с выхода регистра 10, по второму в умножителе !8 формируется квадрат числа, находящегося в регистре 10, по третьему результат заносит- 15 ся в регистр 10„ à по четвертому триггер 5 устанавливается в нулевое состояние, запрещая через элементы

И 7 прохождение числа Х в регистр 10.

Причем особенностью первого цикла является то, что на втором такте на выходе умножителя !8 формируется нулевой код, так как в ретистры 14 и

15 были занесены нули, в регистр 10 на третьем такте заносится число Х 25 с входа 23, а триггер 5 линь в первом цикле находится в единичном состоянии потому, что по четвертому такту первого цикла он сбрасывается в

"0" и на всех последующих циклах по четвертому такту подтверждается это состояние.

Во вторую половину работы генератора 1 число п в регистре 11 сдвигается на один разряд и если в (K+1)-м

Ф

35 разряде оказывается единица, то сигнал, проходя через формирователь 3, формирующий краткий сигнал подключения через элементы И 9 второго сомножителя на вход умножителя 17, и элемент 19 задержки (имеющий время задержки больше длительности импульса с формирователя 3), обеспечивает занесение результата вычисления первого цикла в регистр 12. Если в регистре 11 после очередного сдвига числа в сторону мпадших разрядов оказывается нулевая комбинация, то на выходе элемента ИЛИ 21 формируется сигнал, переводящий триггер 4 в нулевое состояние. На выходе 27 формируется сиг50 нал окончания процесса вычисления, генератор 1 останавливается, а в регистре 12 устанавливается окончательнь|й результат вычислений.

Если в (К+1)-м разряде оказыва55

II И ется после очередного сдвига 0 то результат, полученный в регистре

10, не поступает на умножение с предьщущим промежуточным произведением в регистре 12 и используется для фор" мирования квадрата очередного члена промежуточных произведений.

Таким образом, процесс вычисления Х продолжается столько циклов, П каково значение разряда числа и, в котором записана единица.

Устройство работает и для случая

Х = 1, когда -.ðèããåð 4 после посО тупления сигнала "Пуск" все-таки запускает генераторы I и 2, но промежуточный результат, полученный в регистре 10, не переписывается в регистр 12, а сам триггер 4 на первом же цикле устанавливается в нулевое состояние, индицируя окончание процесса вычисления, В регистре 12 остается ранее занесенная в него единица. Для случая 0" О устройство работает, как описано выше, и в регистре 12 имеется нулевая комбинация.

В случае неопределенности вида о

0 в устройстве по общепринятому в машинах вычислениях правилу выдается 1.

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

Устройство для возведения в степень, содержащее первый генератор тактовых импульсов, группы элементов И, регистр основания степени,информационньтй вход которого подключен к выходу первого элемента ИЛИ, первый вход которого соединен с выходами элементов И первой группы, первые входы которых подключены к входу основания степени устройства, регистр результата, выход которого подключен к входу первого операнда первого умножителя и являeòñÿ выходом результата устройства, регистр показателя степени, информационный вход которого соединен с выходами элементов И второй группы, первые входы элементов И которой подключены к входу no" каэателя степени устройства, о т л ич а ю щ е е с я тем, что, с целью сокращения оборудования, оно содержит второй генератор тактовых импульсов, первый и второй дополнительные регистры, распределитель импульсов, буферный регистр, три триггера, формирователь импульсов, второй элемент

ИЛИ, второй умножитель, элемент НЕ и элемент задержки, а регистр показателя степени выполнен сдвиговым, Составитель 11.Бородянский

Техред Л.Сердюкова. Корректор А,Обручар

Редактор Л.Пчолинская

Заказ 5555/50 Тираж 704

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий!!3035, Москва, Ж-35, Раушская наб., д, 4/5

Подписно е г

Производственно-полиграфическое предприятие, г. ужгород, ул. Проектная, 4

5,14 причем вход запуска устройства соединен с входами установки в "1" первого и второго триггеров, прямой выход последнего из которых подключенк вторым входам элементов И первой группы, выход регистра основания степени подключен к информационным входам первого и второго дополнительных регистров и первым входам элементов И третьей группы, выходы. элементов И которой соединены с входом второго операнда первого умножителя, выход которого через буферный регистр подключен к информационному входу регистра результата, вход разрешения записи которого соединен с выходом элемента задержки, вход которого и вторые входы элементов И третьей группы подключены к выходу формирователя импульсов, вход которого подключен к (К+1)-му входу регистра показателя степени (где К, число разрядов), выходы которого сое, динены с входами второго элемента

ИЛИ„ инверсный выход которого подклю чен к входу установки в "0" первого

:; триггера, прямой выход которого соеди, нен с входом запуска первого генера34428 б тора тактовых импульсов, выход которого подключен к входу элемента НЕ и входу установки в "1" третьего триггера, прямой выход которого подключен к входу запуска второго генератора тактовых импульсов, выход которого соединен с входом распределителя импульсов, первый выход которо-! р ro соединен с входами разрешения записи первого и второго дополнительных регистров, второй — с входом разрешения записи второго умножителя, третий - с входом разрешения записи

1 регистра основания степени, четвертый - с входами установки в "0" второго и третьего триггеров, выходы первого и второго дополнительных регистров подключены к входам первого

20 и второго операндов второго умножи- теля, выход которого соединен с вторым входом первого элемента ИЛИ, выход элемента НЕ подключен к входу сдвига регистра, показателя степени, 15 инверсный выход первого триггера соединен с вторыми входами элементов И второй группы и выходом окончания вычисления.,устройства.