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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 504 С 06 Е 7/О САНИЕ ИЗОБРЕТЕН ение функциональсчет нахождения или меньшего полу, Работа зобретени ых возмож растей аишего большег ению к зад ойства осно ному чис на на последова ска максимально иэ которых одно л ус но роцедуре п еди и+1 чис едующим замещеального числа заданное число, нием найденного на нулевое, Бли по отношению к ется следующий,кс айшим меньшимаданному числу вля сле нег им - пр первог кс дыдущиц макиэ указановлениед аишим а блс им ум Нахоаксимумго мак ов или восст ых ельной технике и мозовано в цифровых си управления. Цель ит в завирежима рапроисхвленног имумста вто мости и оты устроиств ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К А ВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Одесский политехнический институт(56) Авторское свидетельство СССР У 1195346, кл, Г 06 Р 7/02, 1984,Авторское свидетельство СССР У 1282114, кл, С 06 Е 7/02, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ МАКСИМАЛЬНОГО ЧИСЛА(57) Изобретение относится к автоматике и вычислитжет быть исполь иг темах контроля 8013814к заданному числу. 40 45 50 55 Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств цифровых систем контроля и управления,Цель изобретения - расширение функциональных возможностей устройства за счет нахождения ближайшего большего или меньшего по отношению На чертеже изображена функциональ-ная схема предлагаемого устройства,Устройство содержит узлы 1 анализа, которые включают элементы И 2 первой группы, элементы ИЛИ 3 группы, многовходовый элемент ИЛИ 4, элемент НЕ 5, элементы И б второй группы, входы 7 разрядов анализируемых чисел и заданного числа, информационные выходы 8, адресные выходы 9, блок 10 управления, элементы 11 задержки, элементы И 12 анализа, КЯ-триггеры 13, элементы И 14 сброса, элемент ИЛИ 15, элемент И 16, элемент И-НЕ 17, элемент ИЛИ-НЕ 18, вход 19 сброса и вход 20 задания режима.Работа устройства основана на последовательной процедуре поиска максимального среди (и+1) двоичных ш-разрядных чисел, из которых одно - заданное число, с последующим замещением найденного максимального числа на нулевое.В процессе такого поиска максимальным среди оставшихся (не замещенных на нуль) чисел окажется заданноечисло, которое также замещается нанулевое число, обеспечивая тем самымпродолжение процесса поиска очередного максимального числа,Ближайшим меньшим числом по отношению к заданному числу будет следующий после него максимум, а ближайшим большим числом является предыдущий максимум,1 Нахождение первого из указанных максимумов или восстановление второго максимума происходит в зависимости от установленного режима работы устройства,Устройство работает следующим образом.Рассмотрим сначала работу узлов 1; (=1,ш) анализа, обеспечивающих нахождение максимального из (и+1) двоичных чисел, подаваемых в параллельном виде на информационные входы 10 15 20 25 30 35 устройства, На входы 7(р=1,ш, 1 с==1,п+1) подаются коды Р-ых разрядовК-ых двоичных чисел, причем на входы7 , поступает пороговое число, ана остальные информационные входыподаются и анализируемых двоичныхчисел.К моменту подачи на информационныевходы устройства кодов двоичных чисел КБ"триггеры 13%=1,п+1) должныбыть установлены в нулевое состояние,что достигается подачей на вход 19импульса "Сброс", При этом на вторыевходы элементов И 2=1,п+1) всехузлов анализа с инверсных выходовтриггеров 13 поступают разрешающиепотенциалы,Для удобства рассмотрения работыузлов анализа будем полагать, чтоблок управления отсутствует, а навторые входы упомянутых элементов И2 поданы единичные потенциальныеуровни,Поиск максимального числа среди(и+1) чисел, заведенных на информационные входы устройства, производится последовательным поразрядным сравнением значений двоичных разрядоввсех (п+1) чисел, начиная со старшего (в данном случае первого) разрядаПри этом в случае равенства значенийодноименных высших разрядов производится сравнение значений следующегонизшего разряда во всех сравниваемыхчислах. При первом несовпадении значений одноименных двоичных разрядовисключаются из рассмотрения числа снулевым значением искомого разрядаи продолжается поиск максимального.числа среди оставшихся чисел,Поиск и выделение максимальногочисла производится за один цикл переходных процессов в устройстве.Допустим, что на все входы 7; (1 с= =1,п+1) узла 1, анализа поданы коды либо нулей, либо единиц (т,естаршие разряды всех сравниваемых чисел имеют одинаковое значение), Тогда они пройдут на выходы соответствующих элементов И 2, откуда поступят на входы многовходового элемента ИЛИ 4 и на первые входы элементов ИЛИ 3, На выходе элемента ИЛИ 4 появитсяпри этом соответственно код нуля или единицы, а на выходах элементов ИЛИ 3 через элемент НЕ 5 будут сформированы коды единиц, разрешающие работу соседнего узла 1 анализа.Если сигналы на входах 7, невсе идентичны, т.е. на некоторых входах 7; присутствуют коды единиц,а на остальных входах 7; , где 5 Ф 3, - 5коды нулей, то код единицы будетсформирован на информационном выходе8 данного узла анализа, определяязначение старшего (первого) разрядамаксимального числа и на выходах элементов ИЛИ 31, На выходах остальныхэлементов ИЛИ Зз узла 1, анализа будут иметь место коды нулей.Выходные (управляющие) сигналыэлементов ИЛИ 3 %=1,п+1) узла 1, 15анализа поступают в узел 1 анализана третьи входы элементов И 2 ина первые входы элементов И б. Приэтом элементы И 2 и И 6, на которыепоступают управляющие сигналы единичного уровня, будут по соответствующимвходам открыты. Все остальные элементы И 2 з и И бз узла 1 анализа, накоторые поступают управляющие сигналынулевого уровня, будут закрыты, а 25следовательно, будут иметь место нулевые управляющие сигналы на выходахэлементов ИЛИ Зз данного узла анализа.На первые входы элементов И 2 к 30узла 1 анализа поступают с соответствующих входов 7 значения вторыхкразрядов сравниваемых чисел, В 1-ом(12,ш) узле анализа, как и в первом,выходные сигналы элементов И 2 поск 35тупают на входы соответствующего многовходового элемента ИЛИ 4 и на первые входы элементов ИЛИ 3, на вторыевходы которых поступает сигнал свыхода соответствующего элемента 40НЕ 5,Если на все открытые элементы И2; узла 1 анализа поступят с соответствующих информационных входоводинаковые (единичные или нулевые) 45сигналы, то соответственно единичнЫйили нулевой сигнал будет сформированна выходе элемента ИЛИ 4 данного узлаанализа и единичные управляющие сигналы - на выходах элементов ИЛИ 3 Если же на некоторое подмножество открытых элементов И 2 1 поступят с соответствующих входов 7 (Ч 6,1) единичные сигналы, а на остальные открытые элементы И 2 (чс 1) - нулевые сигналы, то на выходе элемента ИЛИ 4 и на выходах элементов ИЛИ 3 будут сигналы единичного уровня, а на выходах элементов ИЛИ 3 - нулевочго уровня.Аналогичным образом работают узлы1; анализа (12), на которые поступают управляющие сигналы с выходовэлементов ИЛИ 3 (1 с=1,п+1) (1-1)-ыхузлов анализа,В результате поразрядного сравнения (и+1)-ых двоичных чисел на информационных выходах 8, (1=1,в) устройства формируется двоичный код максимального из сравниваемых чисел, аэлементы ИЛИ 3 (ц ( и+1) ш-го узлаФанализа, на выходах которых формируется код единицы, определяют порядковые номера найденных максимальныхчисел (их может быть несколько).Рассмотрим процесс замещс ния найденного максимального числа на нулевое число. Этот процесс осуществляется с помощью блока управления, Дляудобства рассмотрения положим, чтовсе элементы И 14, (1 с=1,н) закрыты,например, нулевым потенциалом на входе 20 задания режима работы, а триггер 13+, находится в нулевом состоянии,Допустимчто в некоторый моментвремени максимальным оказалось числос порядковым номером Е (Я п). Тогдавозникший на выходе элемента ИЛИ 3ш-го узла анализа уровень логическойединицы, пройдя элемент 11 задержкии элемент И 12, открытый в этот момент времени единичным уровнем наинверсном выходе триггера 13+ опрокинет по Я-входу триггер 13 вединичное состояние, Возникший приэтом нулевой потенциал на инверсномвыходе триггера 13 у закроет элементыИ 2 всех узлов анализа. В результатеэтого на информационных выходах 8;(=1,ш) и адресном выходе 9 устройства появляется код нуля, что указы-,вает на замещение найденного максимального числа на нулевое.Теперь рассмотрим работу устройства в режиме поиска ближайшего меньшего числа по отношению к заданномучислу. Этот режим устанавливаетсяподачей на вход 20 задания режима работы нулевого потенциала, закрывающего все элементы И 4и элемент И 16,В процессе поиска максимального числа и его замещения на нулевое число наступит момент, когда максимальным окажется заданное число. При этомтриггера 1 З,рпрокинется в единичноесостояние, а спустя время г., задержкич 1элемента 11, задержки проиэоидет обчнуление заданного числа и устроиство5автоматически перейдет к поиску следующего максимальногочиала, которое иявляется ближайшим меньшим числом поотношению к заданному. Однако замещение найденного максимального числа(например, с порядковым номером Г)на нулевое не произойдет, посколькуединичный скачок напряжения, возникший на выходе элемента ИЛИ 3 ш-гоузла анализа, не пройдет через элемент И 12, закрытый, как и все остальные элементы И 12, нулевым потенциалом на инверсном выходе триггера13На информационных выходах устройства формируется при этом код ближайшего меньшего числа по отношению кзаданному числу, а на адресном выходе9- единичный потенциал (признакчисла с порядковым номером Й). Поскольку элемент И 16 закрыт нулевымпотенциалом на входе 20, то исключается возможность запуска триггеровпо Б-входам, что привело бы к "обнулению" найденного максимального30числа.В случае, если заданное числоменьше всех анализируемых чисел, врезультате последовательного процессапоиска максимальных чисел и их последующего обнуления все (и+1) числа35будут замещены на нулевые, а на информационных выходах устройства формируется код нуля, что свидетельстВует о том что среди анализируемых 40чисел нет числа, меньше заданного.На всех адресных выходах устройства в этом вырожденном случае формируется код единицы.Если же среди и анализируемых чисел имеется число (допустим, с порядковым номером Г), равное заданному,то оба эти числа будут найдены одновременно. Однако спустя время С, за"данное число обнулится, а равное ему,50число с порядковым номером Г будетзафиксировано на информационных исоответствующем адресном выходахустройства, поскольку элемент И 12запретит прохождение импульса на8-вход триггера 13 и последний останется в исходном состоянии.,Перейдем к рассмотрению работыустройства в режиме поиска ближайшего большего по отношению к заданному числа, На вход 20 задания режима при этом подается единичный уровень нап-ряжения.Допустим, что заданное число меньше максимального из и анализируемых чисел,В рассматриваемом режиме работы в результате последовательного процесса поиска максимального числа и его последующего обнуления наступает момент, когда максимальным окажется заданное число. Предыдущее перед заданным максимальное число (замещенное на нуль после его нахождения) является искомым ближайшим большим числом по отношению к заданному, В устройстве после нахождения заданного числа в качестве максимального происходит процесс восстановления предыдущего максимального числа (положим также, что оно имеет порядковый номер Г). Это осуществляется следующим образом, Обнуление числа с порядковым номером Е происходит в момент опрокидывания в единичное состояние триггера 13, совпадающий с передним фронтом импульса на выходе элемента 11 задержки, имеющим длительность4 ф Ргде- время задержки элементов 11МОс=1,п+1), задержки;- длительность фронта скачковФнапряжения на выходах триггеров 13 (временем задержки в элементах 12 пренебрегают).Момент опрокидывания триггера 13 в единичное состояние запаздып+вает относительно момента замещения на нуль числа с порядковым номером Г на время с переходного процесса поиска заданного числа как очередно- М максимума.Таким образом, импульс на выходе элемента 11 задержки, поступающий на первый вход элемента И 14, и единичный скачок на прямом выходе триггера 13 , перекрываются на времяГ :,+(2)Поскольку элементы И 14 к В=1,п) постоянно открыты по четвертым входам единичным потенциалом на входе 20 задания режима работы, а по третьим входам постоянно открыты единичным потенциалом на выходе элемента И-НЕ 17, что будет показано ниже, по после опрокидывания в единичное состоя7ние триггера 13, при котором элементы И 14 к открываются, а элементы И 12 закрываются по вторым входам, на выходе элемента И 14 появится импульс длительностью С, воздействующий на второй К-вход триггера 13 .При соблюдении условияТ ;, (3)где Т- минимальный период опроки дывания триггера, определяющий его быстродействие, триггер 13 опрокинется из единичного в нулевое состояние, что обеспечит восстановление числа с порядковым номером Г в качестве максимального. С выходов элементов И 14 (ЯК) на соответствующие К-входы триггера 13 з импульсы не поступают, поскольку импульсы, поступающие в процессе поиска 20 максимальных чисел на первые входы Упомянутых элементов И заканчивается раньше, чем триггер 13 опрокидывается в единичное состояние.25Таким образом, после возвращения триггера 13 в нулевое состояние переходныйпроцесс поиска максимальных чисел прекращается и на информационных выходах устройСтва фиксируется 30 ближайшее большее по отношению к заданному число. На адресном выходе 9 формируется признак порядкового номера этого числа,Иэ (2) и (3) легко найти необходимую величину С, задержки элемента 11 (1 с 1,п+1) задержки:Т п 1 о+л г р ф Теперь пояснимр почему на выходе 40 элемента И-НЕ постоянно присутствует единичный потенциал. Это имеет место, потому что единичные уровни напряже-ния на первом и втором входах элемента И-НЕ 17, соединенных соответствен но с прямым выходом триггера 13,+, и выходом элемента ИЛИ 18, подключенного входами к входам элементов 11 Ь 1,п) задержки, не перекрываются во времени. В случае, если заданное число оказывается больше всех и анализируемых чисел, то оно будет найдено в качестве максимального первым.Возникший при этом на выходе элемента ИЛИ 3 ь единичный скачок напряжения опрокидывает триггер 13+ в единичное состояние и поступает на вход элемента И 16. На второй вход элемен та И 16 с выхода элемента ИЛИ-НЕ 18 поступает единичный потенциал, поскольку на всех входах злевита ИЛИНЕ, связанных с выходами элементов 11 к Ь=1,п) задержки, к моменту срабатывания триггера 13+, присутствует нулевой потенциал.удержание заданного числа в качестве максимального происходит в течелние времени равного длительности импульса на выходе элемента ИЛИ 3 п ш-го узла анализа. Поэтому на выходе элемента И 16 формируется импульс длительностью ц, опрокидывающий то вторым Я-входам триггеры 13 к %=1,п) в единичное состояние, что приводит к замещению на нуль всех и анализируемых чисел.В момент опрокидывания триггеров 13 в единичное состояние элементы И 14 к закрыты нулевыми потенциалами на выходах элементов 11 к задержки, что создает благоприятные условия для опрокидывания триггеров 13 по Б-входам.Спустя время й, после опрокидывания триггера 13+, в единичное состояние происходит обнуление заданного числа.Таким образом, все (и+ 1) чисел оказываются замешенными на нуль. При этом на всех информационных и адресных выходах устройства имеют место нулевые потенциалы, что свидетельствует о том, что среди и анализируемых чисел нет числа, большего заданного. Иа всех адресных выходах при этом присутствуют единичные уровни напряжения, что имеет место только лишь при вырожденном случае обнуления всех (и+1) чисел.Рассмотрим теперь случай, когда число с порядковым номером Е равно заданному. Тогда оба эти числа будут найдены одновременно и на выходах элементов ИЛИ 3 и ИЛИ 3и-го узла анализа в некоторый момент времени появятся единичные скачки напряжения, а триггер 13 . опрокинется в единичное состояние, запретив при этом прохождение импульсов через эле. менты И 12 к Ь=1,п).Единичные скачки напряжения с выхода элемента ИЛИ 18 и прямого выхода триггера 13 , поступают одновременно на входы элемента И-НЕ 17, на выходе которого формируется нулевой потенциал, запрещающий все элементы И 14 кВ результате запретов элементовИ 11 и И 14 к триг ге ры 13 к будутоставаться в том состоянии, в какомони находились к моменту выявлениязаданного числа и равного ему числас порядковым номером Г, как максимальнык,Спустя время , после срабатывания триггера 13 +, заданное числообнулится, а число с порядковым номером Г останется зафиксированным,как максимальное, и будет вьщеленона информационных выходах устройства, а на адресном выходе 9 будетсформирован единичный потенциал.Таким образом, предлагаемое устройство (в отличие от известных)обеспечивает вьщеление ближайшегобольшего или меньшего числа по отношению к заданному числу, а также выделение числа, равного заданному вслучае, если таковые имеются средимножества анализируемых чисел. формула изобретения Устройство для выделения максимального числа, содержащее ш узлов анализа (ш - число разрядов анализируемых двоичных чисел) и блок управления, каждый узел анализа содержит п элементов И первой группы (и - число анализируемых чисел), и элементов ИЛИ группы, многовходовый элемент ИЛИ и элемент НЕ, д-й узел анализа О=2 ш) содержит дополнительно и элементов И второй группы, блок управления содержит и элементов задержки, и элементов И анализа, и КБ- триггеров, элемент ИЛИ и элемент ИНЕ, причем в каждом узле анализа первый вход К-го элемента И первой группы (К=1,2. и) является входом 1-го разряда К-го анализируемого числа устройства (1=1,2ш), второй вход соединен с инверсным выходом К-го КБ-триггера блока управления, а выход подключен к первому входу К-го элемента ИЛИ группы и К-му входу многовходового элемента ИЛИ, выход которого является соответствующим информационным выходом устройства и подключен к входу элемента НЕ, в первом узле анализа выход элемента НЕ соединен с вторыми входами элементов ИЛИ группы, в д-м узле анализа выход элемента НЕ подключен к первым входам элементов И второй группы, выход К-го 5 1 О 15 20 25 30 35 40 45 50 55 элемента И второй группы соединен с вторым входом К-го элемента ИЛИ группы,выход К-го элемента ИЛИ группы (1-1)-го узла анализа подключен к третьему входу К-го элемента И первой группы и второму входу К-го элемента И второй группы х-го узла анализа, выход К-го элемента ИЛИ группы ш-го узла анализа является К-м адресным выходом устройства и через К-й элемент задержки в блоке управления соединен с первым входом К-го элемента И анализа, выход которого подключен первому входу установки в единичное состояние К-го КВ-триггера, первый вход установкиив О которого подключен к входу сброса устройства, вторые входы элементов И анализа объединены, вход первого элемента задержки объединен с первым входом элемента ИЛИ, выход которого подключен к первому входу элемента И-НЕ, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет нахождения ближайшего большего или меньшего по отношению к заданному числу, в каждый узел анализа введены (и+1)-й элемент И первой группы и (п+1)-й элемент ИЛИ группы, в 1-й узел анализа дополнительно введен (и+1)-й элемент второй группы, в блок управления введены (и+1)-й элемент задержки, (и+1)-й КБ-триггер, п элементов И сброса, элемент ИЛИ-НЕ и элемент И, причем первый вход (п+1)- го элемента И первой группы 1-го узла анализа является входом 1-го разряда заданного числа устройства, а выход соединен с первым входом (и+1) - го элемента ИЛИ группы и (и+1)-ым входом многовходового элемента ИЛИ, второй вход (и+1)-го элемента ИЛИ группы в первом узле анализа соединен с выходом элемента НЕ, а в 1-ом узле анализа - с выходом (и+1)-го элемента И второй группы, первый вход которого подключен к выходу элемента НЕ, выход (и+1)-го элемента ИЛИ группы (и)-го узла анализа соединен с вторыми входами (п+1)-х элементов И первой и второй групп 1-го узла анализа, выход (п+1)-го элемента ИЛИ группы ш-го узла анализа соединен в блоке управления с первым входом элемента И и входом установки в единичное состояние (и+ 1)-го КБ-триггера, инверсный выход которого подключен к вторым входам элементов И анализа и через1381483 12 Составитель Е.ИвановаТехред И.Дидык Корректор Н,Король Реви дакт аз 1184/44 Тираж 704 Под ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д.(п+1)-х элементов И первой группывсех узлов анализа, а прямой выходсоединен с первыми входами элементовИ сброса и вторым входом элементаИ-НЕ, выход которого подключен к вторым входам элементов И сброса, третьивходы которых соединены с входом задания режима устройства и вторым вхо Одом элемента И, выход которого подключен к вторым входам установки в1 единичное состояние КБ-триггеров спервого на п-й, а третий вход соединен с выходом элемента ИЛИ-НЕ, К-йвход которого соединен с входом К-гоэлемента задержки и четвертым входомК-го элемента И сброса, выход которого соединен с вто 1%м входом устан. кив "0" К-го ЕЯ-триггера, входы элемента ИЛИ с второго по и-й соединеныс выходами соответствующих элементовИЛИ группы щ-го узла анализа.1