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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 154 9) ( 5 6 06 Е 7/5 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(57) Изобретение ной технике и м устройствах обр изобретения - и Устройство соде регистры 6, 12, т 10, элемент ИЛИ накапливающий казатели степен входные шины выходные шины гистра 7., элемен теля 5 импуль время определе(71) Научно-исследовательский и проектнконструкторский институт автоматизированых систем управления транспортом газа(56) Авторское свидетельство СССРМ 1494003, кл, 6 06 Р 7/552, 1988.Авторское свидетельство СССРМ 1111157, кл, 6 06 Е 7/552, 1983.(54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ ЧСЕЛ В й-Ю СТЕПЕНЬ 2относится к вычислитель- ожет быть использовано в аботки информации. Цель овышение быстродействия. ржит счетчик 1 импульсов, риггер 9, элементы И 3, 4 и 11, генератор 2 импульсов, сумматор 13, шины 14 пои, управляющую шину 15, 16, сигнальную шину 17 и 18. Введение третьего рета ИЛИ - НЕ 8 и формировасов позволяет сократить ния степени числа. 1 ил.Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки инфоомации.Известно устройство для возведения чисел в И-ю степень, содержащее генератор импульсов, первый элемент И, к первому входу которого подключен выход генератора импульсов, первый элемент ИЛИ, первый счетчик импульсов, вход которого соединен с выходом первого элемента ИЛИ, выходные шины, к которым подключены входы первого счетчика импульсов, К управляемых делителей частоты, первый вход первого из которых соединен с первым входом первого элемента И, второй элемент ИЛИ, к первому входу которого подключен выход первого управляемого делителя частоты, а выход подключен к первому входу второго управляемого делителя частоты, триггер, первый вход которого соединен с выходом второго управляемого делителя частоты через последовательно соединенные управляемые делители частоты с третьего до М-го, второй счетчик импульсов, первый вход которого подключен к вторым входам управляемых делителей частоты, третий элемент ИЛИ, входы которого соединены с третьими входами управляемых делителей частоты и с вторыми выходами второго счетчика импульсов, второй элемент И, выход которого подключен к второму входу второго элемента ИЛИ и к второму входу триггера. выход которого соединен с вторым входом первого элемента И, информационную шину, которая подключена к второму входу первого элемента ИЛИ и к входу второго счетчика импульсов. управляющую шину, которая соединена с вторым входом второго элемента И, к п" рвому входу которого подкл 1 очен выход третьего элемента ИЛИ.Наиболее близким по технической сущности является устройство для возведения чисел в К-ю степень, содержащее генератор импульсов, первый триггер., первый и второй регистры, первый элемент И, к входам которого подключены выходы генератора импульсов и первого триггера, управляемый делитель частоты, входы коэффициента деления которого соединены с выходами первого регистра, второй и третий элементы И, второй триггер, единичный выход которого подключен к второму входу второго элемента И, выход которого подключен к тактовому входу второго регистра и к второму входу второго триггера, нулевой выход которого соединен с вторым входом третьего элемента И, первый вход которого соединен с первым входом второго элемента И, с входом управляемого делителя частоты и с выходом 10 20 25 ЗО 35 40 45 50 55 первого элемента И. элемент ИЛИ, к первому входу которого подключен выход третьего элемента И, блок элементов ИЛИ, вторые входы каждого из которых соединены с соответствующими первыми выходами второго оегистра, блок элементов И, ко вторым входам каждого из которых подключены выходы соответствующих элементов ИЛИ блока и соответствующие вторые выходы второго регистра, накапливающий сумматор, к информационным входам которого подключены выходы элементов И блока, первые входы которых соединены между собой, с тактовым входом накапливающего сумматора и с выходом элемента ИЛИ, счетчик импульсов, вычитающий вход которого соединен с выходом управляемого делителя частоты и с первым входом второго триггера, четвертый элемент И, к входам которого подключены выходы счетчика импульсов, управляющую шину, которая соединена со вторым входом первого триггера, с тактовым входом первого регистра и со вторым входом элемента ИЛИ, входные шины, которые подключены к информационным входам первого регистра и к первым входам соответствующих элементов ИЛИ блока, шины показателя степени, которые соединены с информационными входами счетчика импульсов. сигнальную шину, которая соединена с выходом четвертого элемента И и с первым входом первого триггера, выходные шины. которые соединены с выходами накапливающего сумматора и информационнь ми входами второго регистра.Недостатком данного устройства является невысокое быстродействие.Цель изобретения - повышение быстродействия. Поставленная цель достигается тем. что в известное устройство для возведения чисел в М-ю степень, содержащее счетчик импульсов, первый и второй регистры, генератор импульсов, триггер, блок элементов ИЛИ, блок элементов И, первый и второй элементь 1 И, накапливающий сумматор, причем первый вход второго элемента И соединен с выходом генератора импульсов, выход младших К+1) разрядов накапливающего сумматора (где 1 - максимальная степень "2" в представлении входного числа А) подключен к первой группе информационных входов второго регистра, информационный вход счетчика импульсов соединен с входом показателя степени устройства, информационный вход первого регистра соединен с информационным входом устройства, введены третий регистр, элемент ИЛИ - НЕ и формирователь5 10 15 20 25 30 35 40 45 50 55 импульсов, выход которого подключен к вы чита ю ще му входу счетч и ка импул ьсов и входу сброса накапливающего сумматора, выход суммы которого соединен с первым входом блока элементов ИЛИ, выход которого подключен к второй группе информационных входов второго регистра, выходы которого соединены с информационными входами накапливающего сумматора и являются информационным выходом устройства, вход запуска которого подклкнен к входам записи информации счетчика импульсов и первого регистра, информационный вход которого соединен с первым входом блока элементов И, второй вход которого подключен к нулевому выходу триггера, а вь 1 хад подключен к второму входу блока элементов ИЛИ, выходы первого регистра подключены к информационным входам третьего регистра, тактовый вход которого объединен с тактовыми входами триггера, второго регистра, первым входом первого элемента И, и подключе., к выходу генератора импульсов, вход за. уска которого соединен с выходом счетчика импульсов, с входами сброса триггера и третьего регистра, информационным входом триггера и сигнальным выходом устройства, тактовый вход накапливающего сумматора соединен с выходом второго элемента И, второй вход которого соединен с выходом младшего разряда третьего регистра, остальные выходы которого подключены к входам элемента ИЛИ - НЕ, выход которого соединен с управляющими входами второго и третьего регистров и вторым входом первого элемента И, выход которого подключен к входу формирователя импульсов,На чертеже представлена функциональная схема устройства для возведения чисел М-ю степень,Устройство для возведения чисел в М-ю степень содержит счетчик 1 импульсов, генератор 2 импульсов, второй 3 и первый 4 элементы И, фо 1 Ъирователь 5 импульсов, к входу которого подключен выход элемента И 4, первый б и третий 7 регистры, информационные входы которого соединены с выходами регистра б, элемент ИЛИ - НЕ 8, триггер 9, блок 10 элементов И 10, к второму входу которого подключен нулевой выход триггера 9, блок 11 элементов ИЛИ, второй вход которого соединен с выходам блока 10 элементов И, второй регистр 12, тактовый вход которого соединен с тактовыми входами триггера 9 и регистра 7, с выходам генератора 2 импульсов, с первым входом элемента И 4 и с первым входом элемента И 3, к второму входу которого подключен выход младшего разряда регистра 7, остальные выходы которого соединены с входами элемента ИЛИ - НЕ 8, выход которого подключен к управляющим входам второго и третьего регистров и к второму входу элемента И 4, накапливающий сумматор 13, выход младших (1+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"А = ао 2 +а 12 +а 22 э 2 ,о 1 2получаем В 1= А =ао 2 А+а 12 А+а 22 Аа 2 А;В 2= А =ао 2 А+а 12 А+а 22 А+, +А 2 А;Вз = А =ао 2 А +а 12 А +а 22 А а 2 А; Вл=А =а 2 А +а 12 А + + а 22 А а 2 А Регистр 7 обеспечивает выдачу чисел ао, а 1 а,регистр 12 обеспечивает получение чисел 2 А, 2 А.2 А, 2 А 2, 2 А 2 2"А 2 2 одй 1 21 дй 1 21 АМУказанный алгоритм реализуется присовместной работе регистра 7, элемента И3, регистра 12 и накапливающего сумматора 13,Устройство для возведения чисел в Ч-ю 5степень работает следующим образом.Работу устройства рассмотрим при возведении в степень и-разрядного числа (гдеи1), т,е, А =- ао 2 +а 12 +а 2 +,+ал 2".В исходном состоянии счетчик 1 импульсов находится в нулевом положении инулевым сигналом со своего выхода заемазапрещает работу гечератора 2 импульсови удерживает в нулевом положении регистр 7 и триггер 9, На выходе элемента 15ИЛИ - НЕ 8 имеется единичный сигнал ивследствие этого подготовлен к работеэлемент И 4, а регистр 12 находится в режиме параллельного занесения информации, элемент И 3 закрыт нулевым сигналом 20с первого выхода регистра 7, элементы Иблока 10 открыты единичнь:м сигналом снулевого выхода триггера 9. В регистре 6записан код числа, возводившегося в степень в предыдущем цикле вычислений, в 25регистре 12 записан результат предыдущего цикла вычислений, накапливающийсумматор 13 находится в нулевом положении, На сигнальном выходе 17 находитсянулевой сигнал, Установка устройства в 30исходное положение после включения пигания производится подачей импульса навход сброса счетчика 1 импульсов (этацепь не показана).Перед возведением числа в степень на 35вход показателя 14 степени подается кодпоказателя степени И, а на информационный вход устройства 16 - код числа А (А1),которое необходимо возвест. в степень,после этого на вход 15 запуска устройства 40подается импульс, по которому усройствоначинает работу, Импульс с входа 15 записывает в счетчик 1 импульсов код числа К,а в регистр 6 - код числа А, Кроме того, кодчисла А с информационного входа 16 через 45элементы И блока 10 и через элементыИЛИ блока 11(на вторых входах элементовИЛИ блока 11 находятся нулевые сигналы.так как накапливающий сумматор 13 находится в нулевом положении) поступает на 50информационные входы регистра 12, Призаписи в счетчик 1 импульсов числа К наего выходе заема появляется единичныйсигнал. поступающий на сигнальный выход устройства 17 и запрещающий считывание результата до окончания циклавычислений,Кроме того, единичный сигнал с выхода заема счетчика 1 разрешает работу потактовым входам регистра 7 и триггера 9 и работу генератора 2 импульсов, Регистр 7 переходит в режим параллельного занесения информации. По заднему фронту первого импульса генератора 2 в регистр 7 и в регистр 12 записывается код числа А, а триггер 9 устанавливается в единичное положение, закрывая нулевым сигналом со своего нулевого входа элементы И блока 10, Далее до окончания цикла вычислений через элементы ИЛИ блока 11 на информационные входы регистра 12 поступают только младшие (+1) разрядов кода, находящегося в накапливающем сумматоре 13, Кроме того, первый импульс генератора 2 проходит через элемент И 4 и по заднему импульсу на выходе элемента И 4 формирователь 5 выдает импульс, подтверждающий нулевое положение накапливающего сумматора 13 и вычитающий "1" из содержимого счетчика 1 импульсов (в счетчике 1 после этого будет записан код числа (К), Так как хотя бы в одном из разрядов с второго и до (Е+1)-го, регистра 7 записана "1", то на выходе элемента ИЛИ - НЕ 8 появляется нулевой сигнал, закрывающий элемент И 4 и переводящий регистры 7 и 12 в режим сдвига информации, Начинается первый подцикл вычислений - вычисление А . Если на2первом выходе регистра 7 (в этом разряде после записи в регистр 4 числа А находится младший разряд числа А - а ) имеется единичный сигнал (ас,=1), то элемент И 3 открыт и первый импульс генератора 2 во время нахождения регистров 7 и 12 в режиме сдвига поступает на тактовый вход накапливаюгцего сумматора 13 и по своему переднему фронту прибавляет к содержимому накапливающего сумматора 13 (нулевому коду) число А, находящееся в регистре 12. Если же на первом выходе регистра 7 нулевой сигнал (а=О), то элемент И 3 закрыт и первый импульс генератора 2 во время режима сдвига регистров 7 и 12 не проходит на тактовый вход накапливающего сумматора 13, содержимое которого остается равным "О".Таким образом, по переднему фронту первого импульса генератора 2 во время режима сдвига регистров 7 и 12 в накапливающий сумматор 13 записывается число ао 2 А, По заднему фронту этого импульса в регистрах 7 и 12 происходит сдвиг кодов. На первый выход регистра 7 выдвигается второй разряд числа А - а, в регистре 12 будет записано число 2 А. Аналогично предыдущему случаю, если а 1 = 1, то на первом выходе регистра 7 будет единичный сигнал, который открывает элемент И 3 и по переднему фронту второго импульса генератора 2 во время режима сдвига реги 10стров 7 и 12 к содержимому накапливающего сумматора 13 будет прибавлено число 2 А. Если ао" О, то элемент И 3 остается закрытым и содержимое накапливающего сумматора 13 при появлении второго импульса генератора 2 во время режима сдвига регистров 7 и 12 остается без изменений,Таим образом, по переднему фронту второго импульса генератора 2 во время режима сдвига регистров 7 и 12 в накапливающий сумматор 13 будет записано число ао 2 А + а 12 А, По заднему фронту этого импульса в оегистрах 7 и 12 происходит сдвиг кодов, На первый выход регистра 7 выдвигается третий разряд чи 2 сла А-а 2, в регистре 12 будет записано 2 А. Далее устройство работает аналогично описанному до прихода заднего фронта и-го импульса генератора 2 во время режима сдвига регистров 7 и 12, где и - старший разряд(отличный от "0") числа А(пЦ. По заднему фронту п-го импульса происходит сдвиг кодов в регистрах 7 и 12, На первый выход регистра 7 выдвигается и-й разряд числа А - а, при этом в остальных разрядах регистра 7 будут записаны нули, в регистре 12 будет записано число 2"А. Так как в разрядах с второго до (1+1)-го регистра 7 записаны "О", то на выходе элемента ИЛИ-НЕ 8 появляется единичный сигнал, переводящий регистры 7 и 12 в.режим параллельного занесения информации и открывающий элемент И 4.По переднему фронту следующего (и+1)-го импульса к содержимому накапливающего сумматора 13 прибавляется число 2"А и в нем оказывается число до 2 А+а 12 А+а 22 Аал 2 "А = А(ао 2 + +а 12 + а 22 +,+ап 2") = А А = А . Этот импульс проходит через элемент И 4. По заднему фронту этого импульса в регистр 7 заносится число А, в регистр 12 - число А,2 оканчивается импульс на выходе элемента И 4 и формирователь 5 импульсов выдает импульс, устанавливающий накапливающий сумматор 13 в нулевое положение и вычитающий "1" из содержимого счетчика 1 импульсов, в котором после этого будет код числа й. Кроме того, на выходе элемента ИЛИ-НЕ 8 появляется нулевой сигнал, закрывающий элемент И 4 и переводящий регистры 7 и 12 в режим сдвига. Заканчивается первый подцикл вычислений. число А находится в регистре 12, начинается второй подцикл вычислений - вычисление А . Далее устройзство работает аналогично описанному, только к содержимому накапливающего сумматора 13 ( в начале этого подциклв вычислений оно равно "0") бУ 2 дт прибавляться числа ао 2 А 2, а 12 А, а 22 А ап 2 "А, По переднему фронту (и+1)-го импульса, по сле начала режима сдвига регистров 7 и 12в данном (втором) подцикле, к содержимому накапливающего сумматора 13 будет прибавлено число а 22 А и в нем окажетсяи 2число ао 2 А +а 2 А ап 2 "А = А (ао 2 + +а,21+ +а 2 п) А 2 А АзПо заднему фронту этого импульса врегистр 7 заносится число А, в регистр 12 - число А, оканчивается импульс на выходе элемента И 4 и формирователь 5 выдает 15 импульс, устанавливающий накапливающий сумматор 13 в нулевое положение, вычитающий "1" из содержимого счетчика 1, в котором после этого будет код числа И-З, На выходе элемента ИЛИ - НЕ 8 появляет ся нулевой сигнал, закрывающий элементИ 4 и переводя.ций регистр 7 и 12 в режим сдвига. Заканчивается второй подцикл вычислений, число А находится в регистре 12, начинается следующий - третий под цикл вычислений - вычисление А . Далее4устройство аналогично отрабатывает третий и последующие подциклы вычислений, По переднему фронту (и+1)-го импульса, после начала режима сдвига регистров 7 и ЗО 12 в (й)-м подцикле к содержимому накапливающего сумматора 13 прибавляется число а 2"Аи в нем оказывается =А (ао 2+а 12 ап 2") = А А = А, 35 По заднему фронту этого импульса врегистр 7 заносится число А, в регистр 12 - число А, оканчивается импульс на выходейэлемента И 4 и формирователь 5 выдает импульс, устанавливающий накапливаю щий сумматор 13 в нулевое положение ивычитающий "1" из содержимого счетчика 1 импульсов, в которомоказывается кодчисла "0", 8 момент окончания импульса с выхода формирователя 5 на выходе заема 45 счетчика 1 импульсов появляется нулевойсигнал, запрещающий работу генератора 2 импульсов и устанавливающий в нулевое положение регистр и триггер 9. На сигнальном выходе 17 появляется нулевой сиг нал, разрешающий считывание результата -числа А с информационного выхода 18, Устройство возвратилось в исходное состояние.Если число Аили 1, то аналогично 55 описанному при подаче импульса на вход 15запуска в счетчик 1 импульсов записы вается код числа й, а в регистр б - код числа А, При записи в счетчик 1 импульсов числа й на его выходе заема появляется единичный сиг(1+1) разрядов накапливающего сумматора (где М - максимальная степень "2" в представлении входного числа А) подключен к первой группе информационных входов второго регистра, информационный вход счетчика импульсов соединен с входом поФормула изобретения Устройство для возведения чисел в й-ю степень, содержащее счетчик импульсов, первый и второй регистры, генератор импульсов, триггер, блок элементов ИЛИ, блок элементов И, первый и второй элементы И. накапливающий сумматор, причем первый вход второо элемента И соединен с выходом генератора импульсов, выход младших Составитель Б ГусятинТехред М.Моргентал Корректор В. Гирняк Гедактор А, Козориз Заказ 340 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 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, записавшего нулевой код в счетчик 1, на выходе последнего появляется нулевой сигнал, устанавливающий устройство в исходное состояние, В регистре 12 и на выходе 18 находится код числа А числа "О" или "1").иВремя вычисления числа Аравно 1=6 о 92 А)+1)ТК), гдео 92 А) - целая часть числа 092 А. По сравнению с известным устройством быстродействие увеличиваетАо 92 А + 1 10 15 20 25 30 35 40 45 50 казателя степени устройства, информационный вход первого регистра соединен с информационным входом устройства, о тл ич а ю ще ес я тем, что, с целью повышения быстродействия, в него введены третий регистр, элемент ИЛИ-НЕ и Формирователь импульсов, выход которого подключен к вычитающему входу счетчика импульсов и входу сброса накапливающего сумматора, выход суммы которого соединен с первым входом блока элементов ИЛИ, выход которого подключен к второй группе информационных входов второго регистра, выходы которого соединены с информационными входами накапливающего сумматора и являются информационным выходом устройства, вход запуска которого подключен к входам записи информации счетчика импульсов и первого регистра, информационный вход которого соединен с первым входом блока элементов И, второй вход которого подключен к нулевому. выходу триггера, а выход подключен к второму входу блока элементов ИЛИ, выходы первого регистра подключены к информационным входам третьего регистра, тактовый вход которого объединен с тактовыми входами триггера, второго регистра, первым входом первого элемента И и подключен к выходу генератора импульсов, вход запуска которого соединен с выходом счетчика импульсов, с входами сброса триггера и третьего регистра, инФормационным входом триггера и сигнальным выходом устройства, тактовый вход накапливающего сумматора соединен с выходом второго элемента И, второй вход которого соединен с выходом младшего разряда третьего регистра,.остальные выходы которого подключены к входам элемента ИЛИ - НЕ, выход которого соединен с управляющими входами второго и третьего ре истров и вторым входом первого элемента И, выход которого подключен к входу формирователя импульсов.