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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых системах контроля и управления. Цель изобретения - расширение области применения путем режекции множества анализируемых чисел, попадающих в заданные границы интервала значений. Устройство содержит M узлов анализа (M-разрядность двоичных чисел) и блок управления. Каждый узел анализа включает элементы И первой группы, элементы ИЛИ группы, многовходовый элемент ИЛИ, элемент НЕ и дополнительную группу элементов И, а узлы анализа, кроме первого, дополнительно содержат элементы И второй группы. Блок управления содержит элементы И, элементы ИЛИ, элемент И, элементы ИЛИ, RS-триггеры первой группы и второй группы, а также элементы задержки. Устройство позволяет, кроме выделения максимального числа, провести режекцию анализируемых чисел, попавших в заданный интервал. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) А1 (5D4Ñ06F 702

1 !.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АBTOPCKOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

flQ ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ПКНТ СССР

1 (21) 43 759 73/24-24 (22) 05. 01.88 (46) 15. 10.89. Бюп. 9 38 (71) Одесский политехнический институт (72) В.П. Гонтаренко, Б. Г. Горинштейн и В.И. Свиридов (53) 68 1.325 (088.8) (56) Авторское свидетельство СССР

Ф 1116426, кл. G 06 F 7/06, 1984.

Авторское свидетельство СССР по заявке Р 4333692/24, кл. G 06.F 7/02, 1987. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ МАКСН- .

ИАЛЬНОГО ЧИСЛА (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых системах контроля и управления ° Цель изобретения - расширение области приИзобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых системах контроля и управления.

Цель изобретения — расширение области применения за счет режекции анализируемых чисел в заданном интервале .

Структурная электрическая схема устройства показана на чертеже.

Устройство содержит узлы 1 анализа, включающие каждый элементы И 2 и 3, многовходовой элемент ИЛИ 4, элемент НЕ 5 и элементы ИЛИ 6, а узлы анализа, кроме первого, дополнительно содержат элементы И 7, входы 8, 2 менения за счет множества анализируемых чисел, попадающих в заданные границы интервала значений. Устройство содержит m узлов анализа (ш — pasрядность двоичных чисел) и блок управления. Каждый узел анализа включает элементы И первой группы, элементы ИЛИ группы, многовходовый элемент ИЛИ, элемент НЕ и дополнительную группу элементов И, а узлы анализа, кроме первого, дополнительно содержат элементы И 7 второй группы.

Блок управления содержит элементы И, элементы ИЛИ, элемент И, элементы ИЛИ, RS-триггеры первой группы и второй группы, а также элементы задержки.

Устройство позволяет, кроме выделения максимального числа, провести режекцию анализируемых чисел, попавших в заданный интервал. 1 ил ° выходы 9 режектируемых чисел, выходы 10 максимального числа, выходы 11 адреса максимального числа, выходы

12 адреса режектируцмого числа, блок

13 управления, который содержит элементы И l4, RS-триггеры 15 и l6, элементы И 17, элементы ИЛИ 18, элемент

И 19, элемент ИЛИ 20, элементы задержки 2! и 22, вход "Сброс" 23.

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

Рассмотрим сначала работу узлов анализа 1i i 1,m, На информационные входь) 8ij (i 1,m, j = Гр+7) подаются коды i-x разрядов j-x двоичных чисел, из которых первые и чиселI

1515159 образуют входной массив данных, а (и+1)-е и (n+2)-е числа определяют задаваемую верхнюю (В) и нижнюю (А) границы интервала режекции чисел вход5 ного массива.

В исходный момент времени триггеры

15 и 16 должны находиться в нулевом состоянии. Установка триггеров в нулевое состояние производится подачей импульса на шину "Сброс" 23. При этом на втор .е и третьи входы элементов И

2j всех узлов анализа с инверсных выходов триггеров 15 и 16 поступают единичные уровни напряжения, разреша--1 ющие работу укаэанных элементов И.

Блоки анализа осуществляют поиск максимального числа среди множества (n+2) заведенных на их входы чисел путем последовательного поразрядного 20 сравнения кодов входных чисел, начиная со старшего (в нашем случае— первого i 1)) разряда. При этом в случае равенства значений одноименньм высших разрядов чисел устройство 25 автоматически переходит к сравнению следующих низших разрядов и при несовпадении значений сравниваемых одноименных разрядов исключаются из анализа числа с нулевым значением иско- 30 мого разряда и поиск максимального числа продолжается среди оставшихся сравниваемых чисел.

Допустим, что на все информационные входы 8, (j = 1,п+2) узла аНа- 35

1 лиза 1 поданы либо коды нулей, либо коды единиц (т.е. старшие разряды всех сравниваемых чисел имеют одинаковые значения). Тогда они пройдут на выход соответствующих 9JIeMPHTQB H 2, 40 откуда поступят на входы многовходового элемента ИЛИ 4 и на первые входы элементов ИЛИ 6> . На выходе элемента

ИЛИ 4, связанного с информационным выходом 10 устройства появится при 45 этом соответственно код нуля или единицы, а на выходах элементов ИЛИ 6, связанных вторыми входами с выходом элемента ИЛИ 4 через элемент НЕ 5, будут сформировань. коды единиц, разрешающие работу соседнего узла

50 анализа 12 °

Если сигналы на входах 8l) не все идентичны (т. е. на некоторых информационных входах (8,„) присутствуют коды единиц, а на остальных входах (8, 55

3 9 k) — коды нулей), то код единицы будет сфорьмрован на информационном выходе 10 данного узла анализа, onределяя значение старшего (первого) разряда максимального числа, и на выходах элементов ИЛИ 6 . На выходах остальных элементов ИЛИ 6 узла анализа 1„ имеют место коды нулей.

Выходные сигналы элементов ИЛИ 6р узла анализа 1, поступают в узел анализа 1, где заводятся на четвертые входы элементов И 2 и на первые вхо1 ды элементов И 7 . При этом элементы

И 2 „ и 7„, на которые поступают управляющие сигналы единичного уровня, по соответствующим входам разрешены.

Все остальные элементы И 2 s и 7s узла анализа 12, на которые поступают управляющие сигналы нулевого уровня, запрещены, а следовательно, имеют место нулевые управляющие сигнапы на вьлодах элементов ИЛИ 6 данного уз5 ла анализа.

На первые входы элементов И 2 узJ ла анализа 1 поступают с соответствующих информационных входов 8 .зна2J чения вторых разрядов сравниваемых чисел. В i-м (i = 2,ш) узле анализа, как и в первом, выходные сигналы элементов И 2 поступают на входы соответствующего многовходовог о элемента ИЛИ

4 и на первые входы элементов ИЛИ 6, связанных вторьпа1 входами с выходамй элементов И 7 на вторые входы котоt рых заводится сигнал с. выхода соответствующего элемента НЕ 5.

Если на все разрешенные элементы

И 2; узла анализа 1 поступят с соJ

2 ответствующих информационных входов устройства одинаковые (единичные илн нулевые) сигналы, то соответственно единичный или нулевой сигнал будет сформирован на выходе элемента ИЛИ

4 данного узла анализа и единичные управляющие сигналы - на выходах элементов ИЛИ 6„.

Если же некоторое подмножество разрешенных элементов И 2„поступят с соответствующих информационных входов 82 (q е k) единичные сигналы, а на осталь. ых разрешенные элементы

И 2„(v ф q) - нулевые сигналы, то на выходе элемснта kfJIH 4 и выходах элементов ИЛИ 6 будут иметь место сигналы единичного уровня, а на выходах элементов ИЛИ 6 — сигналы нулевого уровня.

Аналогичным образом работают узлы анализа 1; (i ) 2), на которые поступают управляющие сигналы с выходов

5 15 элементов ИЛИ 6 (i-1)-х узлов ана1 лиза.

В результате поразрядного сравнения двоичных чисел на информационных выходах 10;, i = 1,ш, устройства формируется код максимального из (n+2 сравниваемых чисел, а порядковые номе ра элементов ИЛИ 6 m-го узла анализа

Ф на выходах которых формируется код единицы, определяют порядковые номера (адреса) найденных максимальных чисел (их может быть несколько) ° Эти адреса формируются на соответствующих адресных выходах 11> (j = 1,n) устройства,связанных с выходами одноименных элементов ИЛИ 6 ш-го узла ана J лиза.

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

Допустим, что первое найденное максимальное число имеет порядковый номер f Тогда возникший на выходе элемента ИЛИ 6 ш-го узла анализа потенциальный уровень " 1" пройдя разрешенный по второму и третьему входам элемент И 14, опрокинет в единичн>е состояние по s-входу триггер 15 .

Возникший при этом нулевой потенциал на инверсном выходе триггера 15 закf роет элементы И 2 всех узлов анализа, в результате чего на информационньж выходах 10, (i = 1,m) и адресном выходе 11 устройства установится код нуля, что указывает на замещение найденного максимального числа на нулевое. Этот процесс замещения является необратимым, т.к ° триггер 15 будет сохранять единичное состояние.до очередного сброса его в нуль подачей импульса на шину "сброс" 19 °

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

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

В результате поочередного обнуления найденных максимальных чисел наступит момент, когда максимальным окажется число В с порядковым номером (и+1). Среди входных чисел может ока15159 е заться еще одно (или несколько) чисел, равных В. Допустим, их порядковый номер f Тогда на выходе элементов

ИЛИ 6 и 6 „, одновременно возникнут единичные скачки напряжения, которые, ) пройдя через элемент И 14 и элемент задержки 21, опрокинут в единичное состояние триггеры 15 f и 15„, . При этом произойдет обнуление сначала числа с порядковым номером f, а спустя время с задержки элемента эа31 держки 21 будет замещено на нулевое и число В.

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

После срабатывания триггера 15 „„ элементы И 14 будут запрещены нуле25 вым потенциалом на выходе элемента

ИЛИ 20, а элементы И 17 будут разрешены единичным потенциалом на выходе элемента И 19. После обнуления числа Б начнется процесс поиска оче 0 редного максима- ьпого числа. Пусть его порядковый номер равен t (и+1<

t и+2). Тогда единичный скачок напряжения на выходе элемента ИЛИ

6 m-rа узла анализа, пройдя элемент

И 17, опрокинет в единичное состоя35 ние "риггер 16 . При этом нулевой потенциал на инверсном выходе триггера 16 запретит по третьему входу элемент И 14, а нулевой потенциал

40 на выходе элемента ИЛИ 18 запретит элементы И 2 во всех узлах анализа, что приведет к обнулению числа с порядковым номером t и поиску с последующим обнулением очередных максималь45 ньж чисел, лежащих в пределах заданного интервала с граничными значениями А, В. В результате указанного процесса наступит момент, когда MlK симальным окажется число А с порядковым номером (п+2) и, возможно, одно (или несколько) равных ему чисел, допустим, с порядковыми номерами f.

При этом опрокинется в единичное состояние триггер 16, а спустя время задержки t элемента задержки 22

55 опрокинется в единичное состояние триггер 15„. Срабатывание указанных триггеров приведет к обнулению чисел с порядковыми ночерами f и (n+2) .

1515159

Время задержки элементов задержки 21 и 22 одинаково и должно удовлетворять условию

С)1 С>2) ь где — длительность переходного процесса замещения максимального числа на нулевое.

После срабатывания триггера 15„+, единичный потенциал на его прямом выходе, пройдя элемент ИЛИ 20, разрешит по вторым входам элементы И 14, а пройдя через элемент ИЛИ 18, восстановит разрешающие потенциалы на третьих входах тех элементов И 2, которые на предыдущих этапах работы устройства оказались по этим входам запрещенными. Среди элементы И 14 попрежнему останутся запрещенными по третьим входам те иэ них, которые к моменту срабатывания триггера t5 „ оказались запрещенными на предыдущем этапе работы устройства. Порядковые номера этих элементов И равны порядковым номерам чисел Х, удовлетворяющих условию А Х (В, Таким образом. после срабатывания триггера 15 „+ окажутся "восстановленными" указанные числа Х, что приведет к процессу поиска максимального среди них числа.

Найденное максимальное число (пусть его порядковый номер равен t) не сотрется, поскольку запрещен по третьему входу элемент 14 и, следовательно, единичный скачок на выходе элемента

ИЛИ 6 ш-ro каскада не пройдет на в-вход триггера 15 . На этом перех| дные процессы в ycTpo стве закончат я ° 40

Код последнего максимального числа выделится на информационных выходах

10,;, * 1,ш, его порядковый номер на адресном выходе 11<, а порядковые номера чисел Х, попавших в границы заданного интервала, будут зафикс|.рованы в виде единичных потенциалов на прямых выходах сработавших триггеров

16 и, следовательно, на соответствующих адресных выходах 12„ (j п) этих чисел.

Для режекции на выходах 9; (i

1,m j = 1,n) кодов чисел Х в узлах анализа используются элементы И 3, k 1,п, связанные первыми входами с первыми входами соответствующих эле55 ментов И 2„, а по вторым входам — управляемые потенциалами на прямых выходах триггеров 16„. Поэтому на раэрядных выходах 9; будут сформированы коды чисел, которым соответствуют разрешенные элементы И 3 „, т.е. попавших в границы заданного интервала.

В случае, если среди анализируемых чисел не окажется ни одного числа, попадающего в границы заданного интервала значений, после обнаружения числа А (с порядковым номером и+2) начнется автоматический процесс поиска и последующего обнуления очередных максимальных чисел, который будет продолжаться до тех пар, пока не окажутся замещенными на нуль все (n+2) входных числа. Нулевые потенциалы на всех выходных информационных и адресных выходах устройства будут свидетельствовать об этом факте.

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

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

ИЛ". и элемент задержки, причем B каждом узле, анализа первый вход k-ro элемента И первой группы (k = 1,2, ...,и) является входом j-ro разряда

k-го анализируемого числа устройства (j = 1„2,...,m) первые входы (n 1)-ro и (n+2)-ro элементов И первой группы являются входами j = x разрядов соответственно верхней и и;|жней границ устройства, второй вход

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

1515159

10 вход которого соединен с прямым вы— ходом (n+1)-ãî RS-триггера первой . группы, в каждом узле анализа выход р-го элемента И первой группы (р

1,2.. °,n+2) подключен к первому входу р-ro элемента-ИЛИ группы и р-му входу многовходового элемента ИЛИ, выход которого является соответствующим выЫодом максимального числа уст10 ройства и подключен к входу элемента

НЕ, в первом узле анализа выход элемента НЕ соединен с вторыми входами элементов ИЛИ группы, в i-м узле анализа выход элемента НЕ подключен к первым входам элементов И второй группы, выход р-го элемента И второй группы соединен с вторым входом р-го элемента ИЛИ группы, выход р-ro элемента ИЛИ группы (i-1)-ro узла анали20 за подключен к третьему входу р-го элемента И первой группы и второму входу р-ro элемента И второй группы i-го узла анализа, выход k-го элемента HJIH группы ш-го узла анализа 2д является k-м адресным выходом макси-. мального числа устройства и соединен с первым входом k-го элемента И анализа, выход которого соединен с входом установки в " 1" k-ro триггера

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

40 заданном интервале, в каждый блок анализа введена дополнительная группа из и элементов И, а в блок управления введены второй элемент задержки, и ,дополнительных элементов И, и дополнительных элементов ИЛИ и n RS-триггеров второй группы, причем выход

k-го элемента ИЛИ группы ш-го узла анализа соединен с первым входом k-ro дополнительного элемента И в блоке управления, выход которого соединен с входом установки в "1" k-го RS-триггера второй группы, инверсный выход которого соединен с третьим входом k-го элемента И анализа и первым входом

k-ro дополнительного элемента ИЛИ, выход которого соединен с третьим входом k-го элемента И первой группы первого узла анализа и четвертым входом k-го элемента И первой группы

i-го узла анализа, в каждом узле ана.лиза первый вход k-го элемента И дополнительной группы является входом

j-го разряда k-ro анализируемого числа устройства, а выход — выходом

j-ro разряда k-го режектируемого числа устройства, прямой выход k-ro RSтриггера второй группы соединен с вторыми входами k-x элементов И дополнительных групп всех узлов анализа и является выходом адреса режектируемого числа устройства, инверсный выход (и+1)-го RS-триггера первой группы соединен с вторыми входами (n+1)-õ элементов И первых групп всех узлов анализа, выходы (n+1)-го и (n+2)-го элементов ИЛИ группы m-го узла анализа через элементы задержки подключены к входам установки в "1" соответственно (n+1)-ro и (и+2)-ro

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

15151 59

Составитель Е, Иванова

Техред JI.Îëèéíûê

Корректор Т. Малец

Редактор М. Ци тки на

Подписное

Заказ 6277/46

Тираж бб8

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Пройаводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101