Устройство для определения экстремального числа

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихГеспублик(22) Заявлено 15.12.80 (21) 3216441/18-24 д 11 М. Кп.з с присоединением заявки Нов 6 Об Г 7/04 Государственный комитет СССР но делам изобретений н открытий.5 (088,8) Опубликовано 3009.82. Бюллетень Ио 3 б Дата опубликования описания 30,09.82 И.П. Дробязко, В.И. Корнейчук, А.П. Марковский, В.Н. Сороко и В.П. Тарасенко. (71) Заявитель Киевский ордена Ленина политехнический институтим. 50-летия Великой Октябрьской социалистической революции(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГОЧИСЛА Изобретение относится к автоматике и вычислительной технике, в частности, к устройствам сортировки чисел и может быть использовано для электронных цифровых вычислительных систем и систем автоматики.Известно устройство для сравнения двоичных чисел, содержащее схемы запрета на каждый регистр, управляющий триггер, элемент И, а также триггер, элементы И и ИЛИ, общиЕ для всего устройства 1).Недостатками известного устройства являются их сложность, трудность реализации в интегральном исполнении, малое быстродействие; Наиболее близким техническим решением к предложенному является устройство для определения максимального числа из группы чисел, содержащее регистры чисел, группы элементов И, элементы ИЛИ, регистр результата, группы выходных элементов И, выходные элементы ИЛИ, элементы И; элементы НЕ, управляющий регистр, управляющие элементы И, управляющий элемент ИЛИ, элемент ИЛИ-НЕ, задающие элементы И, элементы задержки (2 . Недостатком данного устройства является его малое быстродействие,так как выделение максимального числа производится путем поразрядногосравнения,Цель изобретения - повьпаениебыстродействия.Пдставленная цель достигается10 тем, что в устройстве для определе"ния экстремального числа, содержащем И узлов анализа, группу выходныхэлементов ИЛИ, регистр результата,управляющий регистр, элементы задержки, элементы ИЛИ, ИЛИ-НЕ, причем 1-йинформационный выход каждого )-жузла анализа, где= 1, 2, п1, 2.я, и - число сравниваемых чисел, щ - количество разрядов всравниваемых числах, соединен с -мвходом 1-го выходного элемента ИЛИгруппы, выход каждого 1-го выходного элемента ИЛИ группы подключен к1-му входу регистра результата, управляющий выход каждого -го узлаанализа соединен с 1-м входом управляющего регистра, каждый )-й выходкоторого подключен к управляющемувходу -го узла анализа, первый ивторой выходы результата каждого-го узла анализа соединен с )-мивходами первого и второго элементов ИЛИ-РЕ соответственно, третий выход результата каждого )-го узла анализа подключен к -му входу первого элемента ИЛИ, выход которого соединен с первыми входами тре тьего, четвертого и пятого элементов ИЛИ-НЕ и второго элемента ИЛИ, выход которого подключен к входам первого и второго элементов задержки, выход первого элемента задержки 19 соединен с входами управления запи,сью узлов анализа, выход второго элемента задержки подключенк входам синхронизации узлов анализа, выход первого элемента ИЛИ соединен с первыми входами блокировки узлов анализа, выход первого, элемента ИЛИ-НЕ подключен к второму входу третьего элемента ИЛИ-НЕ, выход которого соединен с вторыми входами блокировки узлов анализа и с вторыми входами Четвертого и пятого элементов ИЛИ-НЕ и второго элемента ИЛИ, выход второго элемента ИЛИ-НЕ подключен к третьему входу четвертого элемента ИЛИНЕ, выход которого соединен с третьими входами блокировки узлов анализа и с третьими входами пятого элемента ИЛИ-НЕ и второго элемента ИЛИвыход пятого элемента ИЛИ-НЕ подключен к четвертому входу второго элемента ИЛИ и к четвертому входу блокировки узла анализа.В устройстве каждый из узлов анализа содержит регистр, три группы элементов И, элемент ИЛИ-НЕ, счет чик, причем вход управления записью узла анализа соединен с управляющим входом регистра, прямой выход каждого -го разряда которого подключен кпервому входу )-го элемента И 40 первой группы, выход каждого )-го элемента И первой группы соединен с -м информационным выходом узла, прямой выход (и - 1)-го разряда регистра подключен к первым входам перво- . го и второго элементов И второй группы, прямой выход и-го разряда регистра соединен с первым входом третьего элемента И второй группы и с вторьи. входом первого элемента И второй группы, прямые выходы (и)-го и и-го разрядов подключены к вторым входам второго и третьего элементов И соответственно второй группы, управляющий вход узла анализа соединен с третьими входами элементов И второй группы и с управляющим входом счетчика, выход которого подключен к второму входу каждого элемента И первой группы, выход первого, второго и третьего элементов И вто- ,60 рой группы соединен с первыми входами первого, второго и третьего элементов И соответственно третьей группь,выходы первого,второго и третьего элементов И третьей группы подключены 65 к первому, второму и третьему входамэлемента ИЛИ-НЕ, выход которого соединен с управляющим выходом узла, первый, второй и третий входы блокировки узла подключены к вторым входам первого, третьего и второго элементов И соответственно третьей группы, четвертый вход блокировки узла анализа соединен с четвертым входом элемента ИЛИ-НЕ.На чертеже приведена блок-схема устройства.Устройство содержит в узлов анализа 1., 11 1, каждый из рых состоит из первой группы элементов И 2, 21 2, элемента ИЛИНЕ 3, счетчика 4, второй группы элементов И 5, 51, 5, регистра 6, третьей группы элементов И 7, 7, 7, группу выходных элементов ИЛЙ 8. 81 8 л, элементы ИЛИ-НЕ 9 - 13, элементы ИЛИ 14 и 15, элементы 16 и 17 задержки, регистр 18 результата, управляющий регистр 19, вход 20 запуска устройства.Устройство работает следующим образом.С помощью элементов И 5 произво дится анализ содержимого двух старших разрядов каждого регистра 61, 2. , щ,при возникновении в них комбинаций "11", "10", "01", соответственно, формируются сигналы на выходах элементов И 5, 5, 5" . Эти сигналы поступают: с выходов всех элементов И 5( = 1 в) на вход элемента ИЛИ 15, с выходов всех элементов 51 каждого 1-го узла анализа 1, где 1 = 1,.:., а, на влды элемента ИЛИ-НЕ 11 с выходов элементов И 5 З каждого 1 -го узла анализа на входы элемента ИЛИ-НЕ 9, таким образом, на выходе элемента ИЛИ 15 формируется единичный сигнал в случае появления комбинации "11" в двух старших разрядах хотя бы одного из сравниваемых чисел, на выходах элементов ИЛИ-НЕ 11 и 9 формируется сигнал нулевого уровня в том случае, если в двух сравниваемых разрядах чисел хотя бы раз попадаются комбинации "10" или "01", соответственно, Сигнал с выхода элемента ИЛИ 15 блокирует через элемент ИЛИ-НЕ 12 нулевой сигнал с элемента ИЛИ 11 так, что единичный сигнал на выходе элемента ИЛИ-НЕ 12 формируется только в случае отсутствия в старших разрядах сравниваемых чисел комбинации "11" и наличия хотя бы одной комбинации "10". Аналогично нулевой сигнал с элемента ИЛИ-НЕ 9 блокируется через элемент ИЛИ-НВ 1 единичными сигналами с элементов ИЛИ 16 и ИЛИ-НЕ 12 так, что единичный сигнал на выходе элемента ИЛИ-НЕ 10 является лишь в случае отсутствия в двух старших разрядахсравниваемых чисел комбинаций "11","10" и наличия хотк бы одной комбинации,"01".,В случае отсутствия вдвух старших разрядах сравниваемыхчисел комбинаций "11", "10", "01"на выходах элементов ИЛИ 16, ИЛИ-НЕ12 и 10 формируются нулевые сигналы,которые, поступая на входы элемента ИЛИ-НЕ 13, формируют на его выходе единичный сигнал.При наличии комбинации "11" вдвух старших разрядах хотя бы одного из сравниваемых чисел, сигнал сэлемента ИЛИ 15 откроет первые вгруппах элементы И 7 для прохождения сигналов с элементов И 5 аналогично, если единичный сигнал сформирован на выходе элемента ИЛИ-НЕ 12,то будут сформированы сигналы на вторых в группах элементов И 51, Аналогично при отсутствии комбинаций "11",ф 10" и наличии "01" в старших разрядах сравниваемых чисел единичныйсигнал будет сформирован на выходахэлементов И 5 З. Формируемые такимобразом сигналы с выходов элементов И 7 вместе с сигналом с элемента ИЛИ-НЕ 13 поступают на входы элементов ИЛИ-НЕ 3, на выходе каждого1-го которого нулевой сигнал форми 1 руется в случае наличия в двух старших разрядах 1-го регистра кода максимальной величины по сравнению сдругими регистрами или в случае, когда в двух старших разрядах всех регистров окажется комбинация "00".На выходах остальных элементовИЛИ-НЕ 3 формируются сигналы единичного уровня, которым устанавливаютсяв нуль соответствующие разряды управгляющего регистра 19, нулевой сигналс выходов которых блокирует посредством элементов И 5 участие чисел,код двух старших разрядов которыхменьше максимального, в последующихтактах сравнения.Таким образом, в каждом тактеопределяются числа, максимальные подвум своим старшим разрядам, а ос-тальные иэ сравнейия на последующихтактах исключаются.Выдача сигнала любых из элементов ИЛИ 15, ИЛИ-НЕ 12, ИЛИ-НЕ 10,ИЛИ-НЕ 13 формирует единичный сигнална выходе элемента ИЛИ 14, который,пройдя через элемент 16 задержки,поступает на счетный вход счетчика 4и на упра:ляющие входы регистров 6,вследствие чего производится сдвигхранимых в них чисел на два разрядаи начинается следующий такт,Пбсле и/2 тактов числа в регистрах 6 установятся в исходное состояние, а все разряды управляющегорегистра 19, кроме одного (или нескольких, если есть несколько равных максимальных чисел), соответствующего максимальному числу, ус 5О15 формула изобретения за соединен с-ми входами первогои второго элементов ИЛИ-НЕ соответственно, третий выход результатакаждого-го узла анализа подключенк-му входу первого элемента ИЛИ,выход которого соединен с первымивходами третьего, четвертого и пятого элементов ИЛИ-НЕ и второгоэлемента ИЛИ, выход которого подключен к входам первого и второго элементов задержки, выход первого элемента задержки соединен с входамиуправления записью узлов анализа,выход второго элемента задержки подключен к входам синхронизации узлованализа,выход первого элемента ИЛИ 60 соединей с.первыми входами блокировки узлов анализа, выход первогоэлемента ИЛИ-НЕ подключен к второмувходу третьего элемента ИЛИ-НЕ, выход которого соединен с вторыми входами блокировки узлов анализа и с 25 30 35 40 тановлены в нулевое состояние, эакрывая через элементы И 2 выдачу на регистр 18 результата всех чисел, кроме максимального. По сигналу переполнения счетчика 4, поступающего на входы элементов И 2, элементом И 2, соответствующим номеру максимального числа, формируется сигнал считывания максимального числа, которое через группу открытых указанных сигналов элементов И 2 и элементы ИЛИ 8 записывается на регистр 18 результата..Предлагаемое устройство позволяет сократить время определения максимального числа за счет анализа сразу двух разрядов всех чисел в два раза. 1. Устройство для определения экстремального числа, содержащее М узлов анализа, группу выходных элементов ИЛИ, регистр результата, управляющий регистр, элементы задержки, элементы ИЛИ, ИЛИ-НЕ, причем.-й информационный выход каждого -го узла анализа, где= 1, 2 и, 3 = 1, 2, ;, е, и в чис сравниваемых чисел, ю " количество разрядов в сравниваемых числах, соединен с -м входом -го выходного элемента ИЛИ группы, выход каждого 1-го выходного элемента ИЛИ группы подключен к -му входу регистра результата, управляющий выход каждого 1-го узла анализа соединен с -м входом управляющего регистра, каждый -й выход которого подключен к управляющему входу-го узла анализа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в нем первый и вторбй выходы результата каждого-го узла анали962920 иал ППП "ПатентУжгород, ул.Пр тная,4 вторыми входами четвертого и пятого элементов ИЛИ-НЕ и второго элемента ИЛИ, выход второго элемента ИЛИ-НЕ подключен к третьему входу четвертого элемента ИЛИ-НЕ, выход которого соединен с третьими входами блокировки узлов анализа и с третьими входами пятого элемента ИЛИ-НЕ и второго элемента ИЛИ, выход пятого элемента ИЛИ.-НЕ подключен к четвертому входу второго элемента ИЛИ и к четвертому входу блокировки узла анализа,2. Устройство по п, 1, о т л и ч а ю щ е е с я тем, что в нем каждый из узлов аналйза содержит регистр, три групйы элементов И,. элемент ЙЛИ-НЕ, счетчик, причем вход управления записью узла анализа соединен с управляющим входом регистра, прямой выход каждого 1-го разряда которого подключен к первому входу 1"го элемента И первой группы, выход каждого 1-по элемента И первой группы соединен с. Ф-м информационным выходом узла, прямой выход (п - 1)-го разряда регистра подключен к первым входам первого и второго элементов И второй группы, прямой выход и-го разряда регистра соединен с первым входом третьего элемента И второй группы и с вторым входом первого элемента И второй группы, прямые выВНИИПИ Заказ 7513/68 Тираж 731 Подписное ходы (п - 1)-го и и-го разрядов подключены к вторым входам второго итретьего элементов И соответстненновторой группы, управляющий вход уз-ла анализа соединен с третьими входами элементов И второй группы и суправляющим входом счетчика, выходкоторого подключен к второму входукаждого элемента И первой группы,выход первого, второго и третьего10 элементов И второй группы соединенс первыми входами первого, второгои третьего элементов И соответственно третьей группы, выходы первого,второго и третьего элементов И третьей группы подключены к первому,второму и третьему входам элемента ИЛИ-НЕ, выход которого соединенс управляющим выходом узла, первый,второй и третий входы блокировки узла подключены к вторым входам первого, третьего и второго элементов Исоответственно третьей группы, четвертый вход блокировки узла анализасоединен с четвертьм входом элемента ИЛИ-НЕ.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9 328450, кл. С 06 Г 7/04, 1970.2. Авторское свидетельство СССРпо заявке Р 2886600/18-24,кл, С 06 Г 7/04, 1980 (прототип),