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

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