Устройство для выделения максимального числа Советский патент 1989 года по МПК G06F7/02 

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

Цель изобретения - расширение области применения за счет возможности выделения максимального числа в заданном интервале, либо за его пределами.

На чертеже показана схема устрой- ства.

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

рядов и при несовпадении значений сравниваемых одноименных разрядов исключаются из анализа числа с нулевым значением искомого разряда и поиск максимального числа продолжается среди оставшихся сравниваемых чисел.

Поиск и выделение максимального числа производится за один цикл пе- реходньйс процессов в устройстве.

Допустим, что на все информационные входы (j 1, n+2) узла анализа 1 поданы либо коды нулей, либо коды единиц (т.е. старшие разряды всех сравниваемых чисел имеют одинаковые значения). Тогда они пройдут на выход соответствующих элемен- ;тов и 2j, откуда поступят на много- входовые входы элемента ИЛИ 4 и на I первые входы элементов ИЛИ 3;. На вьпсоде элемента ИЛИ 4, связанного с информационным выходом устройства, появится при этом соответственно код

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

элемент И 16 и элемент НЕ 17, вход 18 - нуля или единицы, а на выходах элезадания режима, вход 19 сброса.

Устройство работает следующим образом ,

Рассмотрим сначала работу узлов анализа Г., , i 1 m. На информации онные входы 7{j(i 1,m, j 1, n+2) подаются коды Д-х разрядов j-x двоичных чисел, из которых (п+1)-е и (п+2)-е число определяют заданнь1е верхнюю и нижнюю границы искомого интервала поиска максимального числа, а остальные п чисел образуют входной массив данных.

В исходный момент времени триггеры 13; должны находиться в нулевой состоянии. Установка триггеров в нулевое состояние производится подаяей импульса на шину Сброс 19, При этом на вторые входы элементов И 2j всех узлов анализа с инверсных выходов триггеров 13 поступают единичные уровни напряжения, разрешающие работу элементов И,

Блоки анализа осзтцествляют поиск максимального числа среди.множества (п+2) заведенных на их входы чисел путем последовательного поразрядного сравнения кодов входных чисел, начиная со старшего (в нашем случае - первого (i- 1)) разряда.

При этом в случае равенства значений одноименных высших разрядов чисел устройство автоматически переходит к сра внению следующих низших раз ментов ИЛИ 3 , связанных вторыми вхо дами с выходом элемента ИЛИ 4 через /элемент НЕ 5, будут сформированы коды единиц, разрешающие работу сосед30

него узла анализа 1

г

35

Если сигналы на входах 7 не все идентичны (т.е. на некоторых информационных входам ,), присутствуют коды единиц, а на остальных вхо дах (7,j,S К) - коды нулей), то код единицы будет сформирован на информационном выходе 8, Данного узла анализа, определяя значение старшего (первого) разряда максимального числа, и на выходах элементов 3ц. На выходах остальных элементов ИЛИЗ ; узла анализа Ц будут иметь место ко ды нулей.

Выходные (управлякяцие) сигналы эле,ментов ИЛИ 3 узла анализа 1 i, поступают в узел анализа Ц, где заво.45

дятся на третьи входы элементов И 2;, и на первые входы элементов И 6,

При этом элементы И 2 и 6 ,

на

50

55

которые поступают управляющие сигналы единичного уровня, будут по соответствующим входам разрешены. Рее остальные элементы И 2, и 6j узла анализа Ц, на которые поступают равляющие сигналы нулевого уровня, будут запрещены, а, следовательно, будут иметь место нулевые управляющие сигналы на выходах элементов ИЛИ 3 данного узла анализа

ментов ИЛИ 3 , связанных вторыми входами с выходом элемента ИЛИ 4 через /элемент НЕ 5, будут сформированы коды единиц, разрешающие работу сосед

него узла анализа 1

г

Если сигналы на входах 7 не все идентичны (т.е. на некоторых информационных входам ,), присутствуют коды единиц, а на остальных входах (7,j,S К) - коды нулей), то код единицы будет сформирован на информационном выходе 8, Данного узла анализа, определяя значение старшего (первого) разряда максимального числа, и на выходах элементов 3ц. На выходах остальных элементов ИЛИЗъ узла анализа Ц будут иметь место коды нулей.

Выходные (управлякяцие) сигналы эле,ментов ИЛИ 3 узла анализа 1 i, поступают в узел анализа Ц, где заво.:

дятся на третьи входы элементов И 2;, и на первые входы элементов И 6,

При этом элементы И 2 и 6 ,

на

которые поступают управляющие сигналы единичного уровня, будут по соответствующим входам разрешены. Рее остальные элементы И 2, и 6j узла анализа Ц, на которые поступают равляющие сигналы нулевого уровня, будут запрещены, а, следовательно, будут иметь место нулевые управляющие сигналы на выходах элементов ИЛИ 3 данного узла анализа

На первые входы элементов И 2 узла анализа 1 поступают с соответствующих информационных входов У,значения вторых разрядов сравниваемых чисел, В i-M (i 2,m) узле анализа, как и в первом, выходные сигналы элементов И 2 поступают на входы со ответствунщего многовходового элемента ИЛИ 4 и на первые входы элементов ИЛИ 3 , связанных вторыми входами с выходами элементов И 6, на вторые входы которых заводится сигнал с выхода соответствующего элемента НЕ 5

Если на все разрушенные элементы И 2 узла анализа 1 поступят с соответствующих информационных входов одинаковые (единичные или нулевые) сигналы, то соответственно единичный или нулевой сигнал будет сформирован на выходе элемента ИЛИ 4 данного узла анализа и единичные управляющие сиг налы - на выходах элементов ИЛИ 3ц

Если на некоторые подмножества разрешенных элементов И 2 , поступят с соответствующих информационных входов (qjfK) единичные сигналы, а на остальные разрешенные элементы И 2у (V q) - нулевые сигналы, то на выходе элемента ИЛИ 4 и вьколах элементов ИЛИ 3 а будут иметь место сигналы единичного уровня, а на вы- ,ходах элементов ИЛИ 3 - нулевого уровня.

Аналогичным образом работают узлы анализа 1 , ( 2), на которые поступают управлякяцие сигналы с выходов элементов ИЛИ лиза.

В результате поразрядного сравнения двоичных чисел на информацион- ных выходах 8 ; , i 1 ,m, устройства формируется код максимального из сравниваемых чисел, а порядковые но3- (i-l)-x узлов .анамера элементов ИЛИ 3 узла анализа, на выходах которых формируется код единицы, определяют порядковые номера (адреса) найденных максимальных чисел (их может быть несколько). Эти адреса формируются на соответст- вующих адресных выходах 9 j (j 1jn) устройства, связанных с выходами одноименных элементов ИЛИ 3: т-го узла анализа,

Рассмотрим теперь процесс замещения найденного максимального числа нулевым. Этот процесс осуществляется с помощью блока управления.

0

5

0

Допустим, что первое найденное максимальное число имеет порядковый номер f. Тогда возникающий на выходе элемента ИЛИ 3 ц. т-го узла анализа потенциальный уровень логической единицы, пройдя разрешенный по второму входу элемента 12( (в случае, если ), опрокинет в единичное состояние по S-входу триггера 13 . Возникший при этом нулевой потенциал на инверсном выходе триггера 13 л закроет элементы И 2 г всех узлов анализа, в результате чего на информаци- онных выходах 8 , (i 1 ,m) и адресном выходе 9 устройства установи.тся код нуля, что указывает на замещение найденного максимального числа на нулевое. Этот процесс замещения является необратимым, так как триггер 13г будет сохранять единичное состояние до очередного сброса его в нуль подачей импульса на шину Сброс 19.

После обнуления числа с порядко

вым номером f автоматически начинается процесс поиска нового максимального числа среди оставшихся входных чисел и замещения его на нулевое.

Рассмотрим режим работы устройства в режиме поиска максимального числа среди анализируемых чисел, попадающих в пределы интервал а, задаваемого (п+1)-м числом (верхняя граница) и (п+2)-м числом (нижняя граница). Этот реяшм устанавливается подачей на вход 18 нулевого уровня напряжения, который, будучи проинвертирован

ным элементом НЕ 17, поступит через элемент ИЛИ I5 на третьи входы

элементов И 12 : (j ,п) в виде единичного потенциала.

В результате поочередного обнуления найденных максимальных чисел наступит момент ,когда максимальным

окажется число А с порядковым номером (п+), внутри которого требуется найти ма симальное число из массива входных данных. В этом случае опрокинется в единичное состояние триггер 13, а спустя время задержки t j элемента 11 задержки произойдет обнуление найденного максимального числа и запрет по вторым входам элементов всех элементов И 12, после

чего автоматически начнется процесс поиска очередного макс шального числа.

Если среди входных данных окажется одно (или несколько) число, равiioe верхнему граничному числу А (пусть порядковый номер этого числа равен t), то практически одновременно с опрокидыванием в единичное состояние триггера 13 „+, опрокинется и триггер 13 и начнется переходный процесс обнуления числа с порядковым номером t.

Время задержки tj элемента 11 за- держки должно быть выбрано таким, чтобы обнуление числа А с порядковым номером t произошло раньше, чём буде замещено на нуль число А с порядковым номером (п+1).

Для этого величина tj должна быть выбрана из условия:

,

где f - длительность переходного процесса замещения максимального числа на нулевое.

Таким образом, процесс поиска очередного максимального числа всегда начинается после обнуления заданного верхнего граничного числа А.

Если среди входных данньпс имеется число Х В, где В - заданное нижнее граничное число, имеющее порядковый номер (п+2), то оно будет найдено (пусть оно имеет порядковый но- мёр f), однако опрокидьюание в едй ничное состояние траггера 13 г не произойдет, поскольку к моменту появления импульса на выходе элемента 3 ( га-го узла анализа элемент И 12, как и все другие элементы И 12 у, окажется запертым нулевым потенциалом на выходе элемента ИЛИ 14. Таким образом, стирание числа X не произойдет и оно будет зафиксировано на инфор- мационных выходах 8 j устройства.

Найденное число X является максимальным среди входных данных, попадающих в пределы заданного интервала ().

Если среди входных данных не окажется числа, попадающего в заданный интервал значений, то очередным после обнуления числа А с порядковым номером (п+1) является число В с по- рядковым номером (п+2), которое и будет найдено. При этом опрокинется в единичное состояние триггер 13 ti g результате чего на вторые входы элементов И 12j через элемент ИЛИ 1 4 поступит и в дальнейшем будет зафиксирован разрешающий уровень напряжения, формируемый на прямом выходе триггера 1 3 .j.

После обнуления числа В процесс поиска очередных максимальных чисел и их замещение на нуль будет продолжать ся до тех пор, пока, не сработают все триггеры 13. и таким образом окажутся замещенными на нуль все числа входного массива.

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

Рассмотрим теперь работу устройства в режиме поиска максимального числа среди анализируемых чисел, лежащих вне искомого интервала значений. Этот режим устанавливается путем подачи на вход 1В единичного уровня напряжения, которое через элемент ИЛИ 14 поступает на вторые входы элементов И 12.. Напряжение на выходе элемента ИЛИ 15 соответствует при х этом напряжению на выходе элемента И 16, поскольку на втором входе элемента ИЛИ 15 присутствует нулевой потенциал.

В случае, если максимальное число из множества анализируемых чисел лежит в пределах задаваемого интервала значений, то в процессе работы устройства первым в качестве максимального будет найдено число с порядковым номером (п+1), определяющее верхнюю границу искомого интервала, признак которого выделится на выходе элемента ИЛИ 3, т-го узла анализа. Пройдя элемент И 12, этот сигнал опрокинет в единичное состояние триггер 13|,, в результате чего на выходе элемента И 16 и, следовательно, на третьих входах элементов, И 12.- возникнет единичный уровень напряжения, произойдет обнуление найденного максимального числа и автоматически начнется поиск очередного максимального числа.

Поскольку элементы И 12j после срабатьшания триггера оказьгоа- ются разрешенными по управляющим входам, то будет иметь место последовательный процесс поиска и последующего обнуления чисел, попадающих в пределы задаваемого интервала, ;пока максимальным не окажется число с порядковым номером (п+2), определяющим нижнюю границу интервала-. Это число также будет найдено и замещено на нуль. При этом опрокинется в единичное состояние триггер 13 , а на выходе элемента И 16 и, следовательно, на третьих входах элементов И 12, появится нулевой (запрещающий) потенциал.

Очередное найд енн6е максимальное число будет зафиксировано на информационных выходах устройства и соответствующем адресном выходе.

В случае, если максимальное среди анализируемых чисел больше верхней границы задаваемого интервала, то оно будет первым найдено и выделено на выходах устройства. Обнуление этого числа не произойдет, поскольку триггеры 13, и 13 „ находятся при этом в исходных состояниях, обеспечивающих нулевой потенциал на тре- тьих входах элементов И 12 (j I,n).

Формула изобретения

Устройство для выделения максимального числа, содержащее m узлов анализа (т - число разрядов анализируемых двоичных чисел) и блок управления, каждый узел анализа содержит п+1 элементов И первой группы (п- число анализируемых чисел), п+1 элементов ИЛИ группы, многовкодовый элемент ИЛИ и-элемент НЕ, i-й узел анализа (i 2,...,m) содержит дополнительно п+1 элементов И второй группы, блок управления содержит п элементов И анализа, п+1 RS-триггеров, элемент ИЛИ, элемент И, элемент задержки, причем в каждом узле анали-

за первый вход К-го элемента И первой 40 узел анализа введен дополни- группы (К 1,2,...п) является входом тельно (п+2)-й элемент. . И второй

группы.

J-го разряда К-го анализируемого числа устройства (j I,2,...m), пер- ,вый вход (п+1)-гс) элемента И первой группы является входом j-ro разряда кода верхней границы устройства, вто- ,рой вход К-го элемента И первой группы каждого узла анализа соеди- ,нен с инверсным выходом К-го RS-триг- ;гера блока управления, инверсный выход (п+1)-го RS-триггера через элемент задержки подключен к второму входу (п+1)-го элемента И первой группы каждого узла анализа, в каждом узле анализа выход р-го элемента И первой группы (р 1,2,..., n-fl) подключен к первому входу р-го элемента ИЛИ группы и р-му входу мно- говходового элемента ИЛИ, выход котоа в блок управления - (п+2)-й RS-триггер, втлрой элемент ИЛИ и элемент НЕ, причем первый вхо (п+2)-го элемента И первой группы j-ro узла анализа является входом j-ro разряда кода нижней границы ус ройства, вторые входы (п+2)-х элементов И первых групп всех узлов ан лиза соединены с инверсным выходом (п+2)-го RS-триггера и вторым входом элемента И, третий вход которог подключен к прямому выходу (п+)-го RS-триггера, а выход соединен с пер се вым входом первого элемента ИЛИ, вы ход которого соединен с первыми вхо дами элементов И анализа, вход зада ния режима устройства соединен с пе вым входом второго элемента ИЛИ и

50

78110

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

пы, выход р-го элемента И второй

группы соединен с вторым входом р-го элемента ИЛИ группы,выход р-го элемента ИЛИ группы (i-l)-ro узла анализа подключен к третьему входу

р-го элемента И первой группы и второму входу р-го элемента И второй группы i-ro узла анализа, выход К-го элемента ИЛИ группы т-го узла анализа является К-адресным выходом

устройства, вход сброса устройства подключен к входам установки в О всех RS-триггеров, выход К-го элемента И анализа соединен с входом установки в единичное состояние К-го

RS-триггера, вход установки в единичное состояние (п+1)-го RS-триггера подключен к выходу (п+1)-го элемента ИЛИ группы га-го узла анализа, вход задания режима устройства подключен к первому входу элемента И, первые входы элементов И анализа объединены, о т л и ч а ю-щ е е - с я тем, что, с целью расширения об35

ласти применения устройства за счет возможности выделения максимального числа в заданном интервале либо за его пределами, в каждый узел анализа введены (п+2)-й элемент И первой группы,(п+2)-и элемент ИЛИ группы.

узел анализа введен дополни- тельно (п+2)-й элемент. . И второй

группы.

а в блок управления - (п+2)-й RS-триггер, втлрой элемент ИЛИ и элемент НЕ, причем первый вход (п+2)-го элемента И первой группы j-ro узла анализа является входом j-ro разряда кода нижней границы устройства, вторые входы (п+2)-х элементов И первых групп всех узлов анализа соединены с инверсным выходом (п+2)-го RS-триггера и вторым входом элемента И, третий вход которого подключен к прямому выходу (п+)-го RS-триггера, а выход соединен с первым входом первого элемента ИЛИ, выход которого соединен с первыми входами элементов И анализа, вход задания режима устройства соединен с первым входом второго элемента ИЛИ и

IIU9578112

через элемент НЕ с вторым входом пер-ключей дополнительно к первому входу

вого элемента ИЛИ, прямой выход(п+2)-го элемента И второй группы,

(п+2)-го RS-триггера подключен к вто-выход которого соединен с вторым вхорому входу второго элемента ИЛИ, тре-дом (п+2)-го элемента ИЛИ группы,

тий вход которого подключен к выхо-выход (п+2)-го элемента ИЛИ группы

ду элементов задержки, а выход сое-(i-l)-ro узла анализа соединен с трединен с вторыми входами всех элемен-тьим входом (п+2)-го элемента И пертов И анализа, в каждом узле анали-вой группы и вторым входом (п-ь2)-го

за выход (п+2)-го элемента И первой юэлемента И второй группы, i-ro узла

группы соединен с (п+2)-м входоманализа, выход (п+2)-го элемента

многовходового элемента ИЛИ и первымШШ группы т-го узла анализа подклювходом (п-ь2)-го элемента ШШ группы,чен к входу установки в единичное сов первом узле анализа второй входстояние (п+2)-го RS-триггера, вход

(п+2)-го элемента ИЛИ группы соеди- 15установки в О которого подключен к

нен с выходом элемента НЕ, в i-Mвходу сброса устройства. узле анализа выход элемента НЕ под