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

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки информации. Цель изобретения - повышение быстродействия. Устройство содержит счетчик 1 импульсов, регистры 6, 12. триггер 9, элементы И 3. 4 и 10, элемент ИЛИ 11, генератор 2 импульсов, накапливающий сумматор 13, шины 14 показатели степени управляющую шину 15, входные шины 16, сигнальную шину 17 и выходные шины 18. Введение третьего регистра 7, элемента ИЛИ-НЕ 8 и формирователя 5 импульсов позволяет сократить время определения степени числа. 1 ил.

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

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

РЕСПУБЛИК (я)5 G 06 F 7/552

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ф

f7

f6 (21) 4769281/24 (22) 12.12.89 (46) 07.02.92, Бюл. ¹ 5 (71) Научно-исследовательский и проектноконструкторский институт автоматизированных систем управления транспортом газа (72) Е.H.Бантюков (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 1494003, кл, G 06 F 7/552, 1988.

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

¹ 1111157, кл, G 06 F 7/552, 1983. (54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ ЧИСЕЛ В N-Ю СТЕПЕНЬ

„„ЯЦ„„1711154 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки информации. Цель изобретения — повышение быстродействия.

Устройство содержит счетчик 1 импульсов, регистры 6, 12, триггер 9, элементы И 3, 4 и

10, элемент ИЛИ 11, генератор 2 импульсов, накапливающий сумматор 13, шины 14 показатели степени, управляющую шину 15. входные шины 16, сигнальную шину 17 и выходные шины 18. Введение третьего регистра 7., элемента ИЛИ вЂ” НЕ 8 и формирователя 5 импульсов позволяет сократить время определения степени числа. 1 ил.

1711154

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

Известно устройство для возведения чисел в N-ю степень, содержащее генератор импульсов, первый элемент И, к первому входу которого подключен выход генератора импульсов, первый элемент ИЛИ, первый счетчик импульсов, вход которого соединен с выходом первого элемента ИЛИ, выходные шины, к которым подключены входы первого счетчика импульсов, К управляемых делителей частоты, первый вход первого из которых соединен с первым входом первого элемента И, второй элемент ИЛИ, к. первому входу которого подключен выход первого управляемого делителя частоты, а выход подключен к первому входу второго управляемого делителя частоты, триггер, первый вход которого соединен с выходом второго управляемого делителя частоты через последовательно соединенные управляемые делители частоты с третьего до

N-ro, второй счетчик импульсов, первый вход которого подключен к вторым входам управляемых делителей частоты, третий элемент ИЛИ, входы которого соединены с третьими входами управляемых делителей частоты v. с вторыми выходами второго счетчика импульсов, второй элемент И, выход которого подключен к второму входу второго элемента ИЛИ и к второму входу триггера. выход которо;oсоедине,н с вторым входом первого элемента И, информационную шину, которая подключена к второму входу первого элемента ИЛИ и к входу второго счетчика импульсов. управляющую шину, которая соединена с вторым входом второго элемента И, к п рвому входу которого подкл1очен выход третьего элемента ИЛИ.

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

1Î

ЗО

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

ИЛИ, входные шины, которые подключены к информационным входам первого регистра и к первым входам соответствующих элементов ИЛИ блока, шины показателя степени, которые соединены с информационными входами счетчика импульсов. сигнальную шину, которая соединена с выходом четвертого элемента И и с первым входом первого триггера, выходные шины. которые соединены с выходами накапливающего сумматора и информационнь ми входами второго регистра.

Недостатком данного устройства является невысокое быстродействие.

Цель изобретения — повышение быстродействия.

Поставленная цель достигается тем. что в известное устройство для возведения чисел в N-ю степень, содержащее счетчик импульсов, первый и второй регистры. генератор импульсов, триггер, блок элементов ИЛИ, блок элементов И, первый и второй элементы И, накапливающий сумматор, причем первый вход второго элемента И соединен с выходом генератора импульсов, выход младших (k+1) разрядов накапливающего сумматора (где k — максимальная степень "2" в представлении входного числа А) подключен к первой группе информационных входов второго регистра, информационный вход счетчика импульсов соединен с входом показателя степени устройства, информационный вход первого регистра соединен с информационным входом устройства, введены третий регистр, элемент ИЛИ вЂ” НЕ и формирователь

1711154

10

20

50

55 импульсов, выход которого подключен к вы чита ю ще му входу счетч и ка импул ьсов и входу сброса накапливающего сумматора, выход суммы которого соединен с первым входом блока элементов ИЛИ, выход которого подключен к второй группе информационных входов второго регистра, выходы которого соединены с информационными входами накапливающего сумматора и являются информационным выходом устройства, вход запуска которого подключен к входам записи информации счетчика импульсов и первого регистра, информационный вход которого соединен с первым входом блока элементов И, второй вход ко"орого подключен к нулевому выходу триггера, а вь1ход подключен к второму входу блока элементов ИЛИ, выходы первого регистра подключены к информационным входам третьего регистра, тактовый вход которого объединен с тактовыми входами триггера, второго регистра, первым входом первого элемента И, и подключе1, к выходу генератора импульсов, вход за уска которого соединен с выходом счетчика импульсов, с входами сброса триггера и третьего регистра, информационным входом триггера и сигнальным выходом устройства, тактовый вход накапливающего сумматора соединен с выходом второго элемента И, второй вход которого соединен с выходом младшего разряда третьего регистра, остальные выходы которого подключены к входам элемента ИЛИ вЂ” НЕ, выход которого соединен с управляющими входами второго и третьего регистров и вторым входом первого элемента И, выход которого подключен к входу формирователя импульсов, На чертеже представлена функциональная схема устройства для возведения чисел

N-ю степень.

Устройство для возведения чисел в N-e степень содержит счетчик 1 импульсов, генератор 2 импульсов, второй 3 и первый 4 элементы И, фо1%ирователь 5 импульсов, к входу которого подключен выход элемента И 4, первый б и третий 7 регистры, информационные входы которого соединены с выходами регистра 6, элемент

ИЛИ вЂ” НЕ 8, триггер 9, блок 10 элементов И

10, к второму входу которого подключен нулевой выход триггера 9, блок 11 элементов ИЛИ, второй вход которого соединен с выходом блока 10 элементов И, второй регистр 12, тактовый вход которого соединен с тактовыми входами триггера 9 и регистра 7, с выходом генератора 2 импульсов, с первым входом элемента И 4 и с первым входом элемента И 3, к второму входу которого подключен выход младшего разряда регистра 7, остальные выходы которого соединены с входами элемента ИЛИ вЂ” HE 8, выход которого подключен к управляющим входам второго и третьего регистров и к второму входу элемента И 4, накапливающий сумматор 13, выход младших (k+1) разрядов которого соединен с первой группой информационных входов регистра 12, к второй группе информационных входов которого подключен выход блока

11 элементов ИЛИ, первый вход которого соедичен с выходом суммы накапливаю егс сумматора 13, к тактовому входу которого подключен выход элемента И 3, вход показателя степени устройства 14, который соединен с информационным входом с етчика 1 импульсов, вход запуска устройства

15, который подключен к входам записи информации регистра 6 и счетчика 1 импульсов, вычитающий вход которого соединен с входом сброса накапливающего сумматора 13 и с выходом формирователя

5 импульсов. информационный вход 16 устройства, который подключен к информационному входу регистра 6 и к первому входу блока 10 элементов И, сигнальный выход 17 устройства, который соединен с выходом счетчика 1 импульсов, с входами сброса триггера 9 и регистра 7, с информационным входом триггера 9 и с входом запуска генератора 2 импульсов, информационный выход 18 устройства, который соединен с информационными входами накапливающего сумматора 13 и с выходами регистра 12.

Регистр 7 является регистром сдвига и производит сдвиг в сторону младших разрядов. Регистр 12 является регистром сдвига и производит сдвиг в сторону старших разрядов, Устройство реализует следующий алгоритм последовательного вычисления степеней числа А.

Представляя число А в виде суммы степеней числа "2"

А = ao2 +а12 +a22 +...+э 2, о f 2 k получаем

В1= А =а 2 A+a12 A+a22 A+...+àk2 А;

В2 = А =-ао2 А +a12 А +a22 А +. +А 2 А;

Вз = А =ао2 А +а12 А +а22 А +...+а 2 А;

BN1=А =а 2 А +а12 А +

+ а22 А +...+а 2 Я

Регистр 7обеспечивает выдачу чисел ао, a1„... а,регистр 12 обеспечивает получение чисел 2 А, 2 А„.„2 А, 2 А, 2 А „., 2 А,..., 2оАИ-1 21AN 1 2kAN 1

1711154

Указанный алгоритм реализуется при совместной работе регистра 7, элемента И

3, регистра 12 и накапливающего сумматора 13, Устройство для возведения чисел в N-ю 5 степень работает следующим образом.

Работу устройства рассмотрим при возведении в степень и-разрядного числа (где и 9 k), т.е, А =- 8p2 +8)2 +а22 +...+an2

В исходном состоянии счетчик 1 им- i0 пульсов находится в нулевом положении и нулевым сигналом со своего выхода заема запрещает работу гечератора 2 импульсов и удерживает в нулевом положении ре гистр 7 и триггер 9, На выходе элемента 15

ИЛИ вЂ” НЕ 8 имеется единичный сигнал и вследствие этого подготовлен к работе элемент И 4, а регистр 12 находится в режиме параллельного занесения информации, элемент И 3 закрыт нулевым сигналом 20 с первого выхода регистра 7, элементы И блока 10 открыты единичнь:м сигналом с нулевого выхода триггера 9. В регистре 6 записан код числа, возводившегося в степень в предыдущем цикле вычислений, в 25 регистре 12 записан результат предыдущего цикла вычислений, накапливающий сумматор 13 находится в нулевом положении. На сигнальном выходе 17 находится нулевой сигнал, Установка устройства в 30 исходное положение после включения питания производится подачей импульса на вхоr, сброса счетчика 1 импульсов (эта цепь не показана).

Перец возведением числа в степень на 35 вход показателя 14 степени подается код показателя степени N, а на информационный вход устройства 16 — код числа А (А > 1), которое необходимо возвест в степень, после этого на вход 15 запуска устройства 40 подается импульс, по которому ус ройство начинает работу, Импульс с входа 15 записывает в счетчик 1 импульсов код числа N, а в регистр 6- код числа А. Кроме того, код числа А с информационного входа 16 через 45 элементы И блока 10 и через элементы

ИЛИ блока 11 (на вторых входах элементов

ИЛИ блока 11 находятся нулевые сигналы. так как накапливающий сумматор 13 находится в нулевом положении) поступает на 50 информационные входы регистра 12, При записи в счетчик 1 импульсов числа К на

его выходе заема появляется единичный сигнал. поступающий на сигнальный выход устройства 17 и запрещающий считы- 55 вание результата до скончания цикла вычислений, Кроме того, единичный сигнал с выхода заема счетчика 1 разрешает работу по тактовым входам регистра 7 и триггера 9 и работу генератора 2 импульсов. Регистр 7 переходит в режим параллельного занесения информации. По заднему фронту первого импульса генератора 2 в регистр 7 и в регистр 12 записывается код числа А, а триггер 9 устанавливается в единичное положение, закрывая нулевым сигналом со своего нулевого входа элементы И блока 10. Далее до окончания цикла вычислений через элементы ИЛИ блока 11 на информационные входы регистра 12 поступают только младшие (k+1) разрядов кода, находящегося в накапливающем сумматоре 13. Кроме того, первый импульс генератора 2 проходит через элемент И 4 и по заднему импульсу на выходе элемента И 4 формирователь 5 выдает импульс, подтверждающий нулевое положение накапливающего сумматора 13 и вычитающий "1" из содержимого счетчика 1 импульсов (в счетчике 1 после этого будет записан код числа (N-1). Так как хотя бы в одном из разрядов с второго и до (k+1)-ro, регистра 7 записана "1", то на выходе элемента ИЛИ вЂ” HE 8 появляется нулевой сигнал, закрывающий элемент И 4 и переводящий регистры 7 и 12 в режим сдвига информации, Начинается первый подцикл вычислений — вычисление А . Если на

2 первом выходе регистра 7 (в этом разряде после записи в регистр 4 числа А находится младший разряд числа А — а ) имеется единичный сигнал (ао=1), то элемент И 3 открыт и первый импульс генератора 2 во время нахождения регистров 7 и 12 в режиме сдвига поступает на тактовый вход накапливаюгцего сумматора 13 и по своему переднему фронту прибавляет к содержимому накапливающего сумматора 13 (нулевому коду) число А, находящееся в регистре 12. Если же на первом выходе регистра 7 нулевой сигнал (а =О), то элемент И 3 закрыт и первый импульс генератора 2 во время режима сдвига регистров

7 и 12 не проходит на тактовый вход накапливающего сумматора 13, содержимое которого остается равным "О".

Таким образом, по г1ереднему фронту первого импульса генератора 2 во время режима сдвига регистров 7 и 12 в накапливающий сумматор 13 записывается число

ap2оА, По заднему фронту этого импульса в регистрах 7 и 12 происходит сдвиг кодов.

На первый выход регистра 7 выдвигается второй разряд числа А - a>, в регистре 12 будет записано число 2 А. Аналогично

1, предыдущему случаю, если а1 = 1, то на первом выходе регистра 7 будет единичный сигнал, который открывает элемент И

3 и по переднему фронту второго импульса генератора 2 во время режима сдвига реги10 стров 7 и 12 к содержимому накапливающего сумматора 13 будет прибавлено число

2 А. Если a< - О, то элемент И 3 остается

1 закрытым и содержимое накапливающего сумматора 13 при появлении второго импульса генератора 2 во время режима сдвига регистров 7 и 12 остается без изменений, Таким образом, по переднему фронту второго импульса генератора 2 во время режима сдвига регистров 7 и 12 в накапливающий сумматор 13 будет записано число ао2 А + а12 А, По заднему фронту этого импульса в регистрах 7 и 12 происходит сдвиг кодов. На первый выход регистра 7 выдвигается третий разряд числа А-а2, в регистре 12 будет записано 2 А. Далее устройство работает аналогично описанному до прихода заднего фронта и-го импульса генератора 2 во время режима сдвига регистров 7 и 12, где и — старший разряд(отличный от "0") числа А (n s k). По заднему фронту п-ro импульса происходит сдвиг кодов в регистрах 7 и 12. На первый выход регистра 7 выдвигается и-й разряд числа А - а, при этом в остальных разрядах регистра 7 будут записаны нули, в регистре 12 будет записано число 2"А. Так как в разрядах с второго до (k+1)-ro регистра 7 записаны "-О", то на выходе элемента

ИЛИ-НЕ 8 появляется единичный сигнал, переводящий регистры 7 и 12 в .режим параллельного занесения информации и отк ры ва ющий элемент И 4.

По переднему фронту следующего (n+1)-го импульса к содержимому накапливающего сумматора 13 прибавляется число 2"А и в нем оказывается число аа2ОА+а121А+а222А+...+a>2"A = А(ао2О +

+а12 + а22 +„,+an2") = А А = А . Этот импульс проходит через элемент И 4. По заднему фронту этого импульса в регистр 7 заносится число А, в регистр 12 — число А, 2 оканчивается импульс на выходе элемента И 4 и формирователь 5 импульсов выдает импульс, устанавливающий накапливающий сумматор 13 в нулевое положение и вычитающий "1" из содержимого счетчика 1 импульсов, в котором после этого будет код числа й-2. Кроме того, на выходе элемента ИЛИ-НЕ 8 появляется нулевой сигнал, закрывающий элемент И 4 и переводящий регистры 7 и 12 в режим сдвига. Заканчивается первый подцикл вычислений. число А находится в регистре 12, начинается второй подцикл вычислений — вычисление А . Далее устройз ство работает аналогично описанному, только к содержимому накапливающего сумматора 13 (в начале этого подциклв вычислений оно равно "0") будут прибавляться числа ао2 А . а12 А, а22 A,..., ал2 "A, По переднему фронту (и+1)-ro импульса, по5 сле начала режима сдвига регистров 7 и 12 в данном (втором) подцикле, к содержимому накапливающего сумматора 13 будет прибавлено число а22 А и в нем окажется и 2 число а 2 А +а|2 А +...+а 2 "А = А (ао2 +

10 +а;2 +... +а 2") =А А=-А .

По заднему фронту этого импульса в регистр 7 заносится число А, в регистр 12— число А, оканчивается импульс на выходе элемента И 4 и формирователь 5 выдает

15 импульс, устанавливающий накапливающий сумматор 13 в нулевое положение. вычитающий "1" из содержимого счетчика 1, в котором после этого будет код числа ¹3.

На выходе элемента ИЛИ вЂ” НЕ 8 появляет20 ся нулевой сигнал, закрывающий элемент

И 4 и переводя.ций регистр 7 и 12 в режим сдвига. Заканчивается второй подцикл вычислений, число А находится в регистре

12, начинается следующий — третий под25 цикл вычислений — вычисление А . Далее

4 устройство аналогично отрабатывает третий и последующие подциклы вычислений.

По переднему фронту (n+1)-го импульса, после начала режима сдвига регистров 7 и

30 12 в (N-1)-м подцикле к содержимому накапливающего сумматора 13 прибавляется число а 2"A и в нем оказывается

=A (ao2 +a)2 +...+ап2") = A А = A

35 По заднему фронту этого импульса в регистр 7 заносится число А, в регистр 12— число А, оканчивается импульс на выходе и элемента И 4 и формирователь 5 выдает импульс, устанавливающий накапливаю40 щий сумматор 13 в нулевое положение и вычитающий "1" из содержимого счетчика 1 импульсов, в которомоказывается кодчисла "0". 8 момент окончания импульса с выхода формирователя 5 на выходе заема

45 счетчика 1 импульсов появляется нулевой сигнал, запрещающий работу генератора

2 импульсов и устанавливающий в нулевое положение регистр? и триггер 9. На сигнальном выходе 17 появляется нулевой сиг50 нал, разрешающий считывание результата— числа А с информационного выхода 18, Устройство возвратилось в исходное состояние.

Если число А-0 или 1, то аналогично

55 описанному при подаче импульса на вход 15 запуска в счетчик 1 импульсов записы вается код числа N, а в регистр б — код числа А. При записи в счетчик 1 импульсов числа N на его выходе заема появляется единичный сиг1711154 (k+1) разрядов накапливающего сумматора (где k — максимальная степень "2" в представлении входного числа А) подключен к первой группе информационных входов второго регистра, информационный вход счетчика импульсов соединен с входом поФормула изобретения

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

Составитель Б Гусятин

Техред М.Моргентал Корректор В. Гирняк

f çäàKToð А, Козориз

Заказ 340 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина. 101 нал, разрешающий работу регистра 7 и триггера 9 и работу генератора 2 импульсов, По заднему фронту первого импульса генератора 2 триггер 9 устанавливается в единичное положение, а в регистры 7 и 12 записывается код числа А (число "0" или "1"), но на выходе элемента ИЛИ вЂ” НЕ 8 сохраняется единичный сигнал. Кроме того, по заднему фронту первого импульса генератора 2 срабатываег формирователь

5 и импульс с его выхода подтверждает нулевое положение накапливающего сумматора 13 и вычитает "1" из содержащего счетчика 1 импульсов. По переднему фронту второго импульса генератора 2 число А переписывается в накапливающий сумматор

13. По заднему фронту второго импульса в регистр 7 заносится число А из регистр" 6, а в регистр 12 заносится число А из накапливающего сумматора 13.

Кроме того, формирователь 5 выдает импульс, устанавливающий накапливающий сумматор 13.в нулевое положение и вычитающий "1" из содержимого счетчика 1 импульсов. Устройство работает в этом случае аналогично описанному до момента обнуления счетчика 1 импульсов, После окончания импульса с выхода формирователя 5, записаBLUQrо нулевой код в счетчик

1, на выходе последнего появляется нулевой сигнал, устанавливающий устройство в исходное состояние. В регистре 12 и на выходе 18 находится код числа А (числа "О" или "1"). и

Время вычисления числа А равно

t=((1ogyA)+1)T(N-1), где (logzA) — целая часть числа logzA. По сравнению с известным устройством быстродействие увеличиваетА (о92 А) + 1

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

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

ИЛИ, выходы первого регистра подключены к информационным входам третьего регистра, тактовый вход которого объединен с тактовыми входами триггера, второго регистра, первым входом первого элемента

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