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

 

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

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

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

РЕСПУБЛИК

09) <111

А2 (58 4 G 06 Р 7 02

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

К А ВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ hg" с.я ." / (61) 1195346 (21) 3917622/24-24 (22) 26.06.85 (46) 07.01.87. Бюл; У 1 (71) Одесский политехнический институт (72) Б.Г. Горинштейн и В.И. Свиридов (53) 681.325.5 (088.8) (36) Авторское свидетельство СССР

В 1195346, кл. С 06 Р 7/02, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ МАКСИМАЛЬНОГО ЧИСЛА (57) Изобретение относится к области автоматики и вычислительной техники, может быть использовано в цифровых системах автоматического управления и регулирования специализированных устройств обработки данных и является усовершенствованием устройства по авт.св. У 1195346. Целью изобретения. является расширение функциональных возможностей за счет возможности выделения минимального числа. Устройство содержит узлы анализа, каждый из которых содержит группу элементов ИЛИ, и-входовый элемент ИЛИ, элемент НЕ, i-й узел анализа, где i = 2,...,m (m — разрядность чисел), две группы элементов И.Кроме того, устройство содержит элементы задержки, ИЛИ, триггеры, элемент -HE и две группы элементов И. Процедура поиска минимального числа из и чисел состоит в последовательно повторяющихся циклах поиска сначала максимального (одного или одновременно нескольких) из и исходных чисел с последующим его (их) исключением из рассмотрения до выявления последнего (последних) чисел, 1 ил.

4 2

Устройство в режиме поиска максимального числа работает следующим образом. Поиск максимального числа производится последовательным поразрядным сравнением значений двоичных разрядов всех и сравниваемых чисел, начиная со старшего (в нашем случае первого) разряда.

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

При первом несовпадении значений од15

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

Допустим, что на все информационные входы 6; (j=1-n) старших разрядов чисел узла 1 анализа поступают коды либо нулей, либо единиц.

Тогда они проходят на выходы соответствующих элементов И 2 и посJ тупают на входы и-входового элемента ИЛИ 4 и на первые входы соответствующих элементов ИЛИ 3 . На выходе и-входового элемента ИЛИ 4 появляет. ся при этом соответственно код нуля или единицы а на выходах 8 элеэ 3

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

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

45 (вйс) - нули, то код единицы формируется на информационном выходе 7, данного узла анализа, определяя значение старшего (первого) разряда максимального числа, и на выходах эле50 ментов ИЛИ 3„. На выходах остальных элементов ИЛИ 3 узла 1 анализа имеют место потенциалы нулевого уровня .

Управляющие сигналы с выходов элементов ИЛИ 3 узла 1 анализа пос55 тупают в соседний узел 1 анализа на вторые входы элементов И 2 и вто3 рые входы элементов И 9, соединенных первыми входами через элемент

НЕ 5 с выходом и-входового элемен1 - 128211

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

М 1195346.

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

Устройство содержит узлы 1 анализа, в каждом узле анализа группу элементов И 2, группу элементов ИЛИ 3, и-входовый элемент ИЛИ 4, элемент

НЕ 5, информационные входы 6.,информационные выходы 7, адресные выходы 8, в i-м узле анализа группу элементов И 9. Кроме того, устройство содержит группу элементов И 10, элементы 11 задержки, группу элементов

И 12, триггеры 13, элементы ИЛИ 14, элемент И-НЕ 15, вход 16 задания режима и вход 17 сброса. ,Устройство работает следующим об- разом.

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

16 установки режима нулевого потеяциала (уровня логического,"0"), благодаря чему элементы И 121 (i ) ) оказываются эапрещенныии.

При подаче на вход 16 уровня логической "1" устройство переходит в pew ; поиска минимального числа.

При этом на соответствующие входы элементов И 12 . подается разрешакнций потенциал. Двоичные числа поступают на информационные входы 6," (i 1, j1-и где ш — число двоичных разрядов, а n — - число сравниваемых чисел).

Одновременно с подачей каждого набора двоичных чисел на входы 6;. узлов 1; анализа на вход 17 "Сброс" подается импульс признака двоичных чисел, поступающий на нулевые входы триггеров 13 и устанавливакш1ий последние в нулевое состояние. При.этом с инверсных выходов триггеров 13 на вторые входы элементов И 2„ всех узлов анализа и элементов И 10 пос.J тупают разрешающие потенциалы логической "1".

Поскольку в режиме поиска максимального числа элементы И 12 (3=

1-n) запрещены нулевым потенциалом на входе 16 установки режима работы, то возникновение единичного сигнала на соответствующем адресном выходе Sp устройства не вызывает срабатывания по единичному входу триггера 13Р, соединенного с выходом

Sp через соединенные последовательно элемент 11р задержки и элемент

И 12р, а следовательно, не приводит к .изменению управляющих потенциалов на вторых входах элементов И 2J (j=

1282 та ИЛИ 4, открывая только те из них, на которые поступают управляющие сигналы единичного уровня.

Сигналы с выходов элементов И 2J (j=1-п) поступают на входы п-входово-.5

ro элемента ИЛИ 4 и на вторые входы элементов ИЛИ 3„, на первые входы которых подаются сигналы с выходов элементов И 9„ .

При этом, если на все открытые элементы И 2 с информационных входов 6 узла 1 анализа поступают одинаковые (единичные или нулевые) сигналы, то соответственно единичный или нулевой уровень напряжения фор- 15 мируется на информационном выходе

7 данного узла анализа, единичные управляющие сигналы — на выходах элементов ИЛИ 3„ и нулевые — на выходах остальных элементов ИЛИ Зэ. 20

Если же на некоторые разрешенные элементы И 2 поступают с информационных входов 6J (gfk) единичные сигналы, а на остальные разрешенные элементы И 2 (VEk, V4g) нулевые сиг- 25 налы, то на выходе 7 и выходах элементов ИЛИ 3 имеют место единичные уровни напряжения, а на выходах всех остальных элементов ИЛИ 3 (Зад)

J нулевые уровни. 30

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

За узлов 1;, анализа.

В результате поразрядного сравне- 35 ния и двоичных чисел на информационных выходах 71 -7 устройства формируется двоичный код максимального иэ сравниваемых чисел, а порядковые номера выходов 8 > элементов ИЛИ Зр 40 (реп) узла 1щ анализа, на которых формируются единичные потенциалы,характеризуют адреса (порядковые номера) найденных максимальных чисел.

114 4

=1-n), соединенных выходами с ин„формационными входами узла 1 анализа, и на третьих входах элементов И 2„

i-x(i=2-т) узлов анализа.

Состояние выходов 7 и 8 устрой) 3 ства остается при этом неизменным до тех пор, пока не изменятся коды подаваемых на информационные входы

6; чисел.

Устройства в режиме поиска минимального числа работают следующим образом.

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

В режиме поиска минимального числа на вход 16 подается уровень логической "1". При подаче входных чисел триггеры 13„ устанавливаются в нулевое состояние, давая разрешение на элементы И 2 (j=i-n).

В случае, если поданные на входы

6 числа все нули, или все единицы, !

3 на выходах 8„ узла 1> анализа, как следует из рассмотрения работы устройства в режиме поиска максимального числа, возникают единичные потенциалы, которые достигают третьих входов элементов И 12> лишь через время задержки в элементах 11 задержки. Однако к этому моменту времени элементы И 12 запрещены нуле.1 вым потенциалом на выходе элемента

И-НЕ 15. На информационных выходах

7 -7 формируется, как и грежде,двоичный код поданных на информационные входы устройства одинаковых чисел.

В случае, если поданные на входы устройства числа не все одинаковые, то возникают единичные потенциалы лишь на адресных выходах устройства

8, соответствующих порядковым номерам максимальных чисел.

На остальных адресных выходах 8> устройства имеют место нулевые потенциалы. В этом случае с выхода элемента И-НЕ 15 на вторые входы элементов И 121 подается разрешающий потенциал, и единичный сигнал с ад82114 6 ты И 12 и, следовательно, не вызывает опрокидывания триггеров 13>.

10

5 12 ресных выходов 8 „, пройдя элементы

11» задержки и элементы И 12„, опрокидывает по единичным входам триггеры 13» в единичное состояние.

Остальные триггеры 13 по-преж5 нему остаются в нулевом состоянии.

После опрокидывания триггеров 13» на их инверсных выходах возникают нулевые потенциалы, которые закрывают элементы И 2 и 10„ во всех узлах анализа. Потенциалы на выходах элементов И 2 „ и 10„ становятся равными нулю, что эквивалентно замене максимальных чисел нулевыми. В результате этого происходит перераспределение потенциалов на адресных выходах 8> устройства: потенциалы на выходах 8» становятся равными нулю, а возникают единичные потенциалы на некоторых других адресных выходах

8 (МФЕ), и, следовательно, опрокидываются в единичное состояние триггеры 13, вызывая замену вновь найденных во втором цикле работы устройства максимальных чисел нулевыми числами. Этот процесс автоматически продолжается до тех пор, пока в некотором цикле работы не будут найдены последние максимальные (одно или несколько) чисел (они же являются минимальными среди множества и исходных чисел). Допустим, что при этом возникают единичные потенциалы одновременно на некоторых адресных выходах 8 устройства, на остальных адресных выходах при этом устанавливаются нулевые потенциалы. Благодаря тому, что элементы ИЛИ 14 объединяют по входам адресные выходы 8 и единичные выходы триггеров 13„, в момент возникновения единичных потенциалов на адресных выходах 8 р устройства появляются единичные потенциалы на всех входах элемента И-НЕ 15, в результате чего на выходе последнего возникает нулевой потенциал, закрывающий все элементы И 12 .

При выборе времени задержки в элементах 11 задержки, превышающем суммарное время задержки элементов

ИЛИ 141 и И-НЕ 15, единичный скачок напряжения на адресных выходах 8 »

; устройства не проходит через элеменНа этом циклы переходных процессов в устройстве при поиске минимального числа прекращаются. На информационных выходах 7, -?ù устройства формируется двоичный код минимального числа из множества и сравниваемых чисел, а на адресных выходах 8 устройства индицируются порядковые номера (адреса) найденных минимальных чисел.

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

Устройство для выделения максимального числа по авт.св. ¹ 1195346, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности выделения минимального числа, в него введены п элементов задержки, две группы из и элементов И, п элементов ИЛИ, и триггеров и элемент И-НЕ, выход которого соединен с первыми входами элементов И первой группы, вторые входы которых подключены к входу задания режима устройства, третий вход k-ro элемента И первой группы, где k = 1,...,n, через k-й элемент задержки соединен с выходом k-ro элемента ИЛИ группы

m-го узла анализа и первым входом

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

k-х элементов И первых групп i-x узлов анализа (i=2-m) и к первому входу k-ro элемента И второй группы, второй вход которого соединен с входом первого разряда k-го числа устройства, а выход подключен к k-му входу п-входового элемента ИЛИ первого узла анализа, вход сброса устройства подключен к входам установки в нулевое состояние всех триггеров.

1282114

Редактор О. Головач

Заказ 7267/47

Производственно-полиграфическое предприятие, r. Ултород, ул. Проектная,4

А

6rz

6in zr

47

Аи

Йч

4ю

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

Техред П..Сердюкова Корректор С. Шекмар

Тирах 670 Подписное

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

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

А

Ð1