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

1 а шеи

(Л

00

:&

to

00

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

I|gnij изобретения - сокращение оборудования,

На чертеже представлена структурная схема устройства.

Устройство содержит генераторы 1 и 2 тактовых импульсов, формирователь 3 импульсов, триггеры 4-6, группы 7-9 элементов И, регистр 10 основания степени, регистр II показателя степени, регистр 2 Iieзyль- тата , буферный регистр 13, дополнительные регистры 14 и 15, распределитель 16 импульсов, умножители 17 и 18, элемент 19 задержки, элементы гаШ 20 и 21 и НЕ 22,входы 23-25 и вы ходы 26 и 27 устройства,

В основу работы устройства положен следующий алгоритм.

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

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

п , + . а., +,.,+.%о.

где коэффициенты a-(i 0,1,. j,,,К) равны нулю или единице.

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

Х Х2 а Х2 а., .,.Х2°ао

П Х2,.а;

о

(2) 35

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

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

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

Пример, Пусть.п,5 Ю, Тогда двоичная запись п будет п 1010, Х X .

Последовательность получения X следующая,

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

X

с

0

5

0

5

«

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

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

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

В первую половину работы генератора 1 после взведения триггера 6 осуществляется запуск генератора 2-,который обеспечивает серию импульсов для распределителя 16, на выходах котоого появляются последовательно во ремени импульсы. По появленито- им- ульса на четвертом выходе распредеителя 16 триггер 6 переходит в иу- евое состояние, генератор 2 останавивается, а распределитель 16 готовится к формированию новой последовательности импульсов. По сигналу с первого выхода распределителя 16 импульсов в регистры 14 и 15 заносится число с выхода регистра 10, по второму в умножителе 18 формируется квадрат числа, находящегося в регистре 10, по третьему результат заносится в регистр 0, а по четвертому триггер 5 Устанавливается в нулевое состояние, запрещая через элементы И 7 прохождение числа X в регистр 10, Причем особенностью первого цикла является то, что на втором такте на выходе умножителя 18 формируется нулевой код, так как в регистры 14 и 15 бьши занесены нули, в регистр 10 на третьем такте заносится число X с входа 23, а триггер 5 лишь в первом цикле находится в единичном состоянии потому, что по четвертому такту первого цикла он сбрасьгаается в О и на всех последующих циклах по четвертому такту подтверждается это состояние.

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

Если в (К+1)-м разряде оказывается после очередного сдвига О, то результат, полученный в регистре 10, не поступает на умножение с пре0

5

0

5

0

5

0

5

0

5

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

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

Устройство работает и для случая X 1, когда триггер 4 после поступления сигнала Пуск все-таки запускает генераторы 1 и 2, но про- межуточньй результат, полученный в регистре 10, не переписывается в регистр 12, а сам триггер 4 на первом же цикле устанавливается в нулевое состояние, индицируя окончание процесса вычисления, В регистре 12 остается ранее занесенная в него единица. Дпя случая о О устройство работает, как описано выше, и в регистре 12 имеется нулевая комбинация.

В случае неопределенности вида О в устройстве по общепринятому в мащинах вычислениях правилу вьщает- ся 1 .

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

Устройство для возведения в степень, содержащее первый генератор тактовых импульсов, группы элементов И, регистр основания степени,информационный вход которого подключен к выходу первого элемента ИЛИ, первый вход которого соединен с вьrxoдa ш элементов J первой группы, перчые входы которых подключены к входу основания степени устройства, регистр результата, выход которого подключен к входу первого операнда первого умножителя и является выходом результата устройства, регистр показателя степени, информационный вход которого соединен с выходами элементов И второй группы, первые входы элементов И которой подключены к входу показателя степени устройства, о т л н- ч ающееся тем, что, с целью сокращения оборудования, оно содержит второй генератор тактовых импульсов, первый и второй дополнительные регистры распределитель импульсов, буферный регистр, три триггера, формирователь импульсов, второй элемент ИЛИ, второй умножитель, элемент НЕ и элемент задержки, а регистр показателя степени выполнен сдвиговьм.

причем вход запуска устройства соединен с входами установки в 1 первого и второго триггеров, прямой выход последнего из которых подключе - к вторым входам элементов И первой группы, выход регистра основания степени подключен к информационным входам первого и второго дополнительных регистров и первым входам элементов И третьей группы, выходы, элементов И которой соединены с входом второго операнда первого згмножи- теля, выход которого через буферный регистр подключен к информационному входу регистра результата, вход разрешения записи которого соединен с выходом элемента задержки, вход ко- торого и вторые входь элементов И третьей группы подключены к выходу формирователя импульсов, вход которого подключен к (К-М )-му входу регистра показателя степени (где К - число разрядов), выходы которого соединены с входами второго элемента ИЛИ, инверсный выход которого подключен К входу установки в О первого ;триггера, прямой выход Которого соединен С входом запуска первого генератора тактовых импульсов, выход которого подключен к входу элемента НЕ и входу установки в I третьего триггера, прямой выход которого подключен к входу запуска второго генератора тактовых импульсов, выход ко- торого соединен с входом распределителя импульсов, первый выход которого соединен с входами разрешения записи первого и второго дополнительных регистров, второй - с входом разрешения записи второго умножителя, третий - с .входом разрешения записи регистра основания степени, четвертый - с входами установки в О второго и третьего триггеров, выходы первого и второго дополнительных регистров подключены к входам первого и второго операндов второго умножителя, выход которого соединен с вторым входом первого элемента ИЛИ, выход элемента НЕ подключен к входу -с: сдвига регистра, показателя степени, инверсный выход первого триггера соединен с вторыми входами элементов И второй группы и выходом окончания вычисления., устройства.

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