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

 

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

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

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

РЕСПУБЛИН (50 4 G 06 F 7/02

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

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

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4107842/24-24 (22) 23.06,86 (46) 15.03,88, Бюл, ¹- 10 (71) Одесский политехнический институт (72) Б,Г,Горинштейн, Б ° А,Линок и В.И.Свиридов (53) 681.325 (088,8) (56) Авторское свидетельство СССР

¹ 1195346, кл. Г 06 F 7/02, 1984.

Авторское свидетельство СССР № 1282114, кл, G 06 F 7/02, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ МАКСИМАЛЬНОГО ЧИСЛА (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых системах контроля и управления, Цель

„„SU„„1381483 А 1 изобретения — расширение функциональных возможностей эа счет нахождения ближайше го больше го или меньше го по отношению к заданному числу, Работа устройства основана на последовательной процедуре поиска максимального среди n+1 чисел, иэ которых одно заданное число, с последующим замещением найденного м".êñèìàëbíñãî числа на нулевое. Ближайшим меньшим числом по отношению к заданному числу является следующий после него максимум, а ближайшим большим — предыдущий максимум. Нахождение первого иэ указанцых максимумов или восстановление второго максимума происходит в зависимости от установленного режима работы устройства. 1 ил.

1.501483 к заданному числу.

55

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

На чертеже изображена функциональ ная схема предлагаемого устройства, Устройство содержит узлы 1 анализа, которые включают элементы И 2 первой группы, элементы ИЛИ 3 группы, многовходовый элемент ИЛИ 4, элемент

НЕ 5, элементы И б второй группы, входы 7 разрядов анализируемых чисел и заданного числа, информационные выходы 8, адресные выходы 9, блок 10 управления, элементы 11 задержки, элементы И 12 анализа, RS-триггеры

13, элементы И 14 сброса, элемент

ИЛИ 15, элемент И 16, элемент И-НЕ

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

Работа устройства основана на последовательной процедуре поиска максимального среди (и+1) двоичных

m-разрядных чисел, из которых одно— заданное число, с последующим замещением найденного максимального числа на нулевое.

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

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

Рассмотрим сначала работу узлов

1; (i=1 m) анализа, обеспечивающих нахождение максимального из (и+1) двоичных чисел, подаваемых в параллельном виде на информационные входы

35 устройства, На входы 7 „(р=1,m, k=

=1, и+1) подаются коды P-ых разрядов

К-ых двоичных чисел, причем на входы

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

К моменту подачи на информационные входы устройства кодов двоичных чисел RS"триггеры 13 „ (k=1,n+1) должны быть установлены в нулевое состояние, что достигается подачей на вход 19 импульса "Сброс". При этом на вторые входы элементов И 2 „ (k=1 и+1) всех узлов анализа с инверсных выходов триггеров 13„ поступают разрешающие потенциалы, Для удобства рассмотрения работы узлов анализа будем полагать, что блок управления отсутствует, а на вторые входы упомянутых элементов И

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

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

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

Допустим, что на все входы 7;„ (k=

=1,n+1) узла 1, анализа поданы коды либо нулей, либо единиц (т,е ° старшие разряды всех сравниваемых чисел имеют одинаковое значение), Тогда они пройдут на выходы соответствующих элементов И 2, откуда поступят на входы многовходового элемента ИЛИ 4 и на первые входы элементов ИЛИ 3„, На выходе элемента ИЛИ 4 появится при этом соответственно код нуля или единицы, а на выходах элементов ИЛИ

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

1381483

Если сигналы на входах 7,„не все идентичны, т.е. на некоторых входах 7; присутствуют коды единиц, а на остальных входах,3 г е SPj 5 коды нулей, то код единицы будет сформирован на информационном выходе

8 данного узла анализа, определяя значение старшего (первого) разряда максимального числа и на выходах эле- 1р ментов ИЛИ 3, На выходах остальных элементов ИЛИ 3 будут иметь место коды нулей.

Выходные (управляющие) сигналы элементов ИЛИ 3 (k=1,п+1) узла 1, 15 анализа поступают в узел 1 анализа на третьи входы элементов И 2„ и на первые входы элементов И б„. При этом элементы И 2 и И 6„, на которые поступают управляющие сигналы единич- 2р ного уровня, будут по соответствующим входам открыты. Все остальные элементы И 2> и И 6 узла 1 анализа, на которые поступают управляющие сигналы нулевого уровня, будут закрыты, а 25 следовательно, будут иметь место нулевые управляющие сигналы на выходах элементов ИЛИ 3 данного узла анализа.

На первые входы элементов И 2 к 3р узла 1> анализа поступают с соответствующих входов 7 значения вторых

2К разрядов сравниваемых чисел. В 1-ом (i 2,m) узле анализа, как и в первом, выходные сигналы элементов И 2 поск 35 тупают на входы соответствующего многовходового элемента ИЛИ ч и на первые входы элементов ИЛИ 3„, на вторые входы которых поступает сигнал с выхода соответствующего элемента 40

HE 5.

Если на все открытые элементы И

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

Если же на некоторое подмножество открытых элементов И 2 поступят с соответствующих входов 7 (q 6 j) единичные сигналы, а на остальные открытые элементы И 2„ (vpq) — нулевые сигналы, то на выходе элемента

KIN 4 и на выходах элементов ИЛИ 3 будут сигналы единичного уровня, а на выходах элементов ИЛИ 3 — нулевоч

ro уровня.

Аналогичным образом работают узлы

1; анализа (i > 2), на которые поступают управляющие сигналы с выходов элементов ИЛИ 3 (k=1,п+1) (i-1)-ых узлов анализа, В результате поразрядного сравнения (и+1)-ых двоичных чисел на информационных выходах 8; (i=1,m) устройства формируется двоичный код максимального из сравниваемых чисел, а элементы ИЛИ 3 (q и+1) m-го узла анализа, на выходах которых формируется код единицы, определяют порядковые номера найденных максимальных чисел (их может быть несколько).

Рассмотрим процесс замещения найденного максимального числа на нулевое число. Этот процесс осуществляется с помощью блока управления. Для удобства рассмотрения положим, что все элементы И 14, (k=1,n) закрыты, например, нулевым потенциалом на входе 20 задания режима работы, а триггер 13„+, находится в нулевом состоянии, Допустим,,что в некоторый момент времени максимальным оказалось число с порядковым номером f (Я п) ° Тогда возникший на выходе элемента ИЛИ 3

m-го узла анализа уровень логической единицы, пройдя элемент 11 задержки и элемент И 12, открытый в этот момент времени единичным уровнем на инверсном выходе триггера 13„+,, опрокинет по S-входу триггер 13 в

1 единичное состояние. Возникший при этом нулевой потенциал на инверсном выходе триггера 13у закроет элементы

И 2 всех узлов анализа. В результате этого на информационных выходах 8; (i=1 m) и адресном выходе 9 устройства появляется код нуля, что указы- . вает на замещение найденного максимального числа на нулевое.

Теперь рассмотрим работу устройства в режиме поиска ближайшего меньшего числа по отношению к заданному числу. Этот режим устанавливается подачей на вход 20 задания режима работы нулевого потенциала, закрывающего все элементы И!4 „ и элемент И 16, В процессе поиска максимального числа и его замещения на нулевое число наступит момент, когда максимальным окажется заданное число. При этом

1381483 триггера 13,рпрокинется в единичное состояние, а спустя время t задержки

II элемента 11 задержки проиэоидет обIIi I нуление заданного числа и устроиство

5 автоматически перейдет к поиску следующего максимального чиала, которое и является ближайшим меньшим числом по отношению к заданному. Однако замещение найденного максимального числа (например, с порядковым номером f) на нулевое не произойдет, поскольку единичный скачок напряжения, возникший на выходе элемента ИЛИ 3 m-го

f узла анализа, не пройдет через элемент И 12, закрытый, как и все остальные элементы И 12, нулевым потенциалом на инверсном выходе триггера

13„

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

9 — единичный потенциал (признак числа с порядковым номером f) ° По- 25 скольку элемент И 16 закрыт нулевым потенциалом на входе 20, то исключается возможность запуска триггеров по S-входам, что привело бы к "обнулению" найденного максимального

30 числа.

В случае, если заданное число меньше всех анализируемых чисел, в результате последовательного процесса поиска максимальных чисел и их последующего обнуления все (n+1) числа

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

Ha scex адресных выходах устройства в этом вырожденном случае формируется код единицы.

Если же среди и анализируемых чи- 45 сел имеется число (допустим, с порядковым номером f), равное заданному, то оба эти числа будут найдены одновременно. Однако спустя время ti заданное число обнулится, а равное ему

,50 число с порядковым номером f будет зафиксировано на информационных и соответствующем адресном выходах устройства, поскольку элемент И 12у запретит прохождение импульса на

S-вход триггера 13 и последний оста- 55

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

Допустим, что заданное число меньше максимального из и анализируемых чисел, В рассматриваемом режиме работы в результате последовательного процесса поиска максимального числа и его последующего обнуления наступает момент, когда максимальным окажется заданное число. Предыдущее перед заданным максимальное число (замещенное на нуль после его нахождения) является искомым ближайшим большим числом по отношению к заданному, В устройстве после нахождения заданного числа в качестве максимального происходит процесс восстановления предыдущего максимального числа (положим также, что оно имеет порядковый номер f). Это осуществляется следующим образом, Обнуление числа с порядковым номером f происходит в момент опрокидывания в единичное состояние триггера 13, совпадающий с передним фронтом импульса на выходе элемента 11 задержки, имеющим длительность

4 4 Ф () где t — время задержки элементов 11

< к (k=1,n+1), задержки; — длительность фронта скачков

Ф напряжения на выходах триггеров 13к (временем задержки в элементах 12„ пренебрегают).

Момент опрокицывания тригreра

13 в единичное состояние запаздыn+i вает относительно момента замещения на нуль числа с порядковым номером

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

Таким образом, импульс на выходе элемента 11 задержки, поступающий на первый вход элемента И 14, и единичный скачок на прямом выходе триггера 13 „, перекрываются на время

l =с,+с — с„. (2)

Поскольку элементы И 14 < (k=1,ï) постоянно открыты по четвертым входам единичным потенциалом на входе

20 задания режима работы, а по третьим входам постоянно открыты единичным потенциалом на выходе элемента И-НЕ

17, что будет показано ниже, по после опрокидывания в единичное состоя1381483

7 ние триггера 13„„, при котором элементы И 14 открываются, а элементы

И 12 закрываются по вторым входам, на выходе элемента И 14 появится импульс длительностью С, воздействующий на второй R-вход триггера 13 .

При соблюдении условия

Т„„„, (3) где Т .„- минимальный период опроки-10 дывания триггера, определяющий его быстродействие, триггер 13 опрокинется из единично1

ro в нулевое состояние, что обеспечит восстановление числа с порядковым номером f в качестве максимального.

С выходов элементов И 14 (S/f) на соответствующие R-входы триггера 13 импульсы не поступают, поскольку импульсы, поступающие в процессе поиска2О максимальных чисел на первые входы упомянутых элементов И заканчивается раньше, чем триггер 13„+, опрокидывается в единичное состояние.

Таким образом, после возвращения триггера 13 в нулевое состояние пе1 реходный проце сс поиска мак симальных чисел прекращается и на информационных выходах устройСтва фиксируется Зр ближайшее большее по отношению к заданному число. На адресном выходе 9 формируется признак порядкового номера этого числа, Иэ (2) и (3) легко найти необходи- 3 мую величину t, задержки элемента

11 (k 1,ï+1) задержки:

t t - dmin+ n tq>

Теперь поясним, почему на выходе 4О элемента И-НЕ постоянно присутствует единичный потенциал. Это имеет место, потому что единичные уровни напряже- ния на первом и втором входах элемента И-НЕ 17, соединенных соответствен- 45 но с прямым выходом триггера 13 „+, и выходом элемента ИЛИ 18, подключенного входами к входам элементов 11„ (k1,n) задержки, не перекрываются во времени. В случае, если заданное число оказывается больше всех и анализируемых чисел, то оно будет найдено в качестве максимального первым.

Возникший при этом на выходе элемента

ИЛИ 3>+, единичный скачок напряжения опрокидывает триггер 13„+ в единичное состояние и поступает на вход элемента И 16. На второй вход элемен та И 16 с выхода элемента ИЛИ-НЕ 18 поступает единичный потенциал, поскольку на всех входах элемента ИЛИНЕ, связанных с выходами элементов

11 к (k=1,n) задержки, к моменту срабатывания триггера 13„+, присутствует нулевой потенциал. удержание заданного числа в качестве максимального происходит в течение времени ац, равного длительности импульса на выходе элемента ИЛИ

3п,, ш-го узла анализа. Поэтому на выходе элемента И 16 формируется импульс длительностью ц, опрокидывающий ufo вторым S-входам триггеры 13 (к=1,п) в единичное состояние, что приводит к замещению на нуль всех и анализируемых чисел.

В момент опрокидывания триггеров

13 в единичное состояние элементы

И14„ закрыты нулевыми потенциалами на выходах элементов 11 задержки, что создает благоприятные условия для опрокидывания триггеров 13„ по

S-входам.

Спустя время t после опрокидывания триггера 13„+, в единичное состояние происходит обнуление заданного числа.

Таким образом, все (n+ 1) чисел оказываются замешенными на нуль. При этом на всех информационных и адресных выходах устройства имеют место нулевые потенциалы, что свидетельствует о том, что среди и анализируемых чисел нет числа, большего заданного.

На всех адресных выходах при этом присутствуют единичные уровни напряжения, что имеет место только лишь при вырожденном случае обнуления всех (и+1) чисел.

Рассмотрим теперь случай, когда число с порядковым номером f равно заданному. Тогда оба эти числа будут найдены одновременно и на выходах элементов ИЛИ 3 и ИЛИ 3 +< m-ro узла анализа в некоторый момент времени появятся единичные скачки напряжения, а триггер 13, .> опрокинется в единичное состояние, запретив при э том прохожде н ие импуль сов че ре з элементы И 12, (k=1,п).

Единичные скачки напряжения с выхода элемента ИЛИ 18 и прямого выхода триггера 13 „+, поступают одновременно на входы элемента И-НЕ 17, на выходе которого формируется нулевой потенциал, запрещающий все элементы

И 14к.

1381483

В результате запретов элементов

И 11 „и И 14 триггеры 13 ц будут оставаться в том состоянии, в каком они находились к моменту выявления заданного числа и равного ему числа с порядковым номером f, как максимальнык, Спустя время t после срабатывания триггера 13 „+, заданное число обнулится, а число с порядковым номером f останется зафиксированным, как максимальное, и будет выделено на информационных выходах устройства, а на адресном выходе 9 будет сформирован единичный потенциал.

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

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

Устройство для выделения максимального числа, содержащее m узлов анализа (m — число разрядов анализируемых двоичных чисел) и блок управления, каждый узел анализа содержит п элементов И первой группы (и — число анализируемых чисел), п элементов

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

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

j-ro разряда К-ro анализируемого числа устройства (j=1,2,.. °,m) второй вход соединен с инверсным выходом

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

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

ИЛИ группы, в i-м узле анализа выход элемента НЕ подключен к первым входам элементов И второй группы, выход К-ro

l0

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

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

RS-триггера, первый вход установки

l! !! в О которого подключен к входу сброса устройства, вторые входы элементов И анализа объединены, вход первого элемента задержки объединен с первым входом элемента ИЛИ, выход которого подключен к первому входу элемента И-НЕ, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет нахождения ближайшего большего или меньшего по отношению к заданному числу, в каждый узел анализа введены (n+1) é элемент И первой группы и (п+1)-й элемент ИЛИ группы, в i-й узел анализа дополнительно введен (и+1)-й элемент второй группы, в блок управления введены (n+1) и элемент задержки, (n+1) и RS-триггер, и элементов И сброса, элемент ИЛИ-НЕ и элемент И, причем первый вход (и+1)rn элемента И первой группы j-ro узла анализа является входом j-го разряда заданного числа устройства, а выход соединен с первым входом (и+1)— го элемента ИЛИ группы и (и+1)-ым входом многовходового элемента ИЛИ, второй вход (n+1)-го элемента ИЛИ группы в первом узле анализа соединен с выходом элемента НЕ, а в i-ом узле анализа — с выходом (n+1)-ro элемента И второй группы, первый вход которого подключен к выходу элемента НЕ, выход (и+1)-ro элемента ИЛИ группы (п-1)-го узла анализа соединен с вторыми входами (и+1)-х элементов И первой и второй групп 1-ro узла анализа, выход (п+1)-ro элемента ИЛИ группы ш-ro узла анализа соединен в блоке управления с первым входом элемента

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

1381483

12 ф

У

1

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

Техред И.Дидык Корректор Н.Король

Редактор А.Ревин

Заказ 1184/44 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 элемент задержки — к третьим входам (п+1)-х элементов И первой группы всех узлов анализа, а прямой выход соединен с первыми входами элементов

И сброса и вторым входом элемента

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

1 единичное состояние RS- тригге ров с первого на п-й, а третий вход соединен с выходом элемента ИЛИ-НЕ, К-й вход которого соединен с входом К-го элемента задержки и четвертым входом

K-го элемента И сброса, выход которого соединен с вто Жм входом устан«ки в "0" К-го RS-триггера, входы элемента ИЛИ с второго по и-й соединены с выходами соответствующих элементов

ИЛИ группы m-ro узла анализа.