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

 

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

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

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

РЕСПУБЛИН

„„Я0ÄÄ 1495781 (51) 4 G 06 F 7/02

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4333692/24-24 (22) 29.10.87 (46) 23 ° 07.89. Бюл. ЕЕ- 27 (71) Одесский политехнический институ.т (72) В.П.Гонтаренко, Б.Г.Горинштейн и В.И.Свиридов (53) 681.325(088.8) (56) Авторское свидетельство СССР

N - 1282114, кл. С 06 F 7/02, 1985.

Авторское свидетельство СССР

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

ИЛИ 1, элемент НЕ 5 и блок управления 10, включающий элементы И 12 анализа, RS-триггер 13, элемент И 16, элемент ИЛИ 14 и элемент задержки Il„ введены элементы ЕТ, ИЛИ, RS-триггеры, второй элемент ИЛИ 15 и элемент

НЕ 17. 1 ил.

1495781

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

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

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

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

Рассмотрим сначала работу узлов анализа 1 . i = 1 m. На информациЭ Э

30 онные входы 7;1(i = l,m, j = 1, и+2) подаются коды i--x разрядов j-хдвоичных чисел, из которых (и+1)"е и (и+2)-е число определяют заданные верхнюю и нижнюю границы искомого интервала поиска максимального числа, а остальные и чисел образуют входной массив данных.

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

1 работу элементов И.

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

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

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

Допустим, что на все информационные входы 7 (j = 1, и+2) узла анализа 11 подайы либо коды нулей, либо коды единиц (т.е. старшие разряды всех сравниваемых чисел имеют одинаковые значения). Тогда они пройдут на выход соответствующих элемен.тов И 2 откуда поступят на многоР входовые входы элемента ИЛИ 4 и на ! первые входы элементов ИЛИ 3 . На выходе элемента ИЛИ 4, связайного с информационным выходом устройства, появится при этом соответственно код ,нуля или единиЦы, а на выходах эле ментов ИЛИ 3;, связанных вторыми входами с выходом элемента ИЛИ 4 через ,элемент HE 5, будут сформированы коды единиц, разрешающие работу соседнего узла анализа 1 .

Если сигналы на входах 7„ не все идентичны (т.е. на некоторых информационных входах (7 „), приоутст" вуют:коды единиц, а на остальных входах .(7,,8 K) — коды нулей), то код единицы будет сформирован на информационном выходе 8, данного узла ,анализа, определяя значение старшего (первого) разряда максимального числа, и на выходах элементов 3>, На выходах остальных элементов ИЛИ 3; узла анализа 11 будут иметь место коды нулей.

Выходные (управляющие) сигналы элементов ИЛИ 3 ° узла анализа l поступают в узел анализа 1 где заво.-: дятся на третьи входы элементов И 2 . и на первые входы элементов И.6.

При этом элементы И 2, и 6„, на которые поступают управляющие сигналы единичного уровня, будут по соответствующим входам разрешены. Все остальные. элементы И 2 > и 6g узла анализа 11, на которые поступают управляющие сигналы нулевого уровня, будут запрещены, а следовательно, будут иметь место нулевые управляю. щие сигналы иа выходах элементов

ИЛИ 3 данного узла анализа, 1495781

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

ИЛИ 3, связанных вторыми входами с выходами элементов И 6., на вторые

У входы которых заводится сигнал с выхода соответствующего элемента НЕ 5.

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

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

И 2 (Ч ф q) — нулевые сигналы, то на выходе элемента ИЛИ 4 и ньгхогах 30 элементов ИЛИ 3 ч будут иметь место сигналы единичного уровня, а на выходах элементов ИЛИ 3, — нулевого уровня, Аналогичным образом работают узлы анализа 1; (i + 2), на которые поступают управляющие сигналы с выходов элементов ИЛИ 3 . (i-I)-х узлов .ана3 лиза.

В результате поразрядного сравне- 40 ния двоичных чисел на информационных выходах 8;, i = 1,m устройства

В формируется код максимального из сравниваемых чисел, а порядковые номера элементов ИЛИ 3 -ro узла анали- 45

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

Эти адреса формируются на соответст" вующих адресных выходах 9 (j = l n) устройства, связанных с вь;ходами одноименных элементов ИЛИ 3 m-ro

J узла анализа, 5S

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

Допустим, что первое найденное максимальное число имеет .порядковый номер f. Тогда возникающий на выходе элемента ИЛИ 3< m-го узла анализа потенциальный уровень логической единицы, пройдя разрешенный по второму входу элемента 12 (н случае, если

f ф и+1), опрокинет в единичное состояние по S-входу триггера 13 . Возникший при этом нулевой потенциал на инверсном выходе триггера 13 g закроет элементы И 2 г всех узлов анализа, в результате чего на информационных вьгходах 8; (i = l,m) и адресном выходе 9 устройства установится код нуля, что указывает на замещение найденного максимального числа на нулевое. Этот процесс замещения является необратимьм, так как триггер 13 будет сохранять единичное состояние до очередного сброса его в нуль подачей импульса на шину "Сброс" 19, После побнуления числа с порядковым номером f автоматически начинается процесс поиска нового максимального числа среди оставшихся входных чисел и замещения его на нулевое, Рассмотрим режим работы устройства н режиме поиска максимального числа среди анализируемьгх чисел, попадающих н пределы интервала, задаваемого (n+I)-м числом (нерхняя граница) и (п+2)-м числом (нижняя граница).

Этот режим устанавливается подачей на вход 18 нулевого уровня напряжения, который, будучи проиннертированным элементом HE 17, поступит через элемент ИЛИ IS на третьи нходы элементов И 12 (j = Г,n) в виде единичного потенциала.

В результате поочередного обнуления найденных "максимальных чисел наступит момент,когда максимальным окажется число А с порядковым номером (и+1), внутри которого требуется найти ма"симальное число из массина входных данных. В этом случае опрокинется н единичное состояние триггер 13 „„, а спустя время задержки t » элемента 1I задержки произойt1 1l дет обнуление найденного максимального числа и запрет по вторым входам элементов всех элементов И 12, после чего автоматически начнется процесс гоиска очередного максимального числа.

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

5 состояние триггера 13 „,, опрокинет-. ся и триггер 13 и начнется переходный процесс обнуления числа с порядковым номером

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

Для этого величина t> должна быть выбрана из условия: и 1 где с — длительность переходного процесса замещения максимального 20 числа на нулевое.

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

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

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

Если среди входных данных не окажется числа, попадающего в заданный интервал значений, то очередным после обнуления числа А с порядковым номером (и+1) является число В с порядковым номером (n+2) которое и будет найдено. При этом опрокинется в единичное состояние триггер 13 ь» в результате чего на вторые входы элементов И 12 через элемент ИЛИ 14 поступит и в дальнейшем будет зафиксирован разрешающий уровень напряжения, формируемый на прямом выходе триггера 13 „,, После обнуления числа В процесс поиска очередных максимальных чисел и их замещение на нуль будет продолжать ся до тех пор, пока, не сработают все триггеры 13 и таким образом ока-! жутся замещенными на нуль все числа входного массива, Код нуля, формируемый при этом на информационных выходах устройства, свидетельствует о том, что.среди входных данных отсутствует числа, попадающее в пределы заданного интервала.

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

Этот режим устанавливается путем подачи на вход IS единичного уровня напряжения, которое через элемент

ИЛИ 14 поступает на вторые входы элементов И 12 . Напряжение на выходе элемента ИЛИ 15 соответствует при х этом напряжению на выходе элемента

И 16, поскольку íà втором входе элемента ИЛИ 15 присутствует нулевой потенциал.

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

И1 сйгнал опрокинет в единичное состояние триггер 13 »,, в результате чего на выходе элемента И 16 и, следовательно, на третьих входах элементов. И 12 возникнет единичный уро3 вень напряжения, произойдет "обнуление" найденного максимального числа и автоматически начнется поиск очереднаго максимального числа, Поскольку элементы И 121 после срабатывания триггера 13 „», оказываются разрешенными по управляющим входам, то будет иметь место последовательный процесспоискаи последующего "обнуления" чисел, попадающих в пределы задаваемого интервала, пока максимальным не окажется число

lc порядковым номером (и+2); определяющим нижнюю границу интервала.

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

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

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

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

Устройство для выделения макси- 25 мального числа, содержащее m узлов анализа (m — число разрядов анализируемых двоичных чисел) и блок управления, каждый узел анализа содержит и+1 элементов И первой группы (и†30 число анализируемых чисел), п+1 эле ментов ИЛИ группы, многовходовый элемент ИЛИ и-элемент НЕ, i-й узел анализа (i 2,, ° .,m) содержит дополнительно и+1 элементов И втоРой гРУп- З5 пы, блок управления содержит и элементов И анализа, n+1 RS-триггеров, элемент ИЛИ, элемент И, элемент задержки, причем s каждом узле анали- . за первый вход К-ro элемента И первой 4р группы (К = 1,2,...n) является входом

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

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

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

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

j- ãî узла анализа является входом

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

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

1495781

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

Техред А.Кравчук Корректор NËàêñèìèøèíåö

Редактор В.Бугренкова

Заказ 4267/46 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Ужгород, ул. Гагарина, 101 через элемент НЕ с вторым входом пер" ного элемента ИЛИ, прямой выход (n+2)-ro RS-триггера подключен к второму входу второго элемента ИЛИ, третий вход которого подключен к выходу элементов задержки, а выход соединен с вторыми входами всех элементов И анализа, в каждом узле анализа выход (n+2)-ro элемента И первой группы соединен с (и+2)-м входом многовходового элемента ИЛИ и первым входом (n+2)-го элемента ИЛИ группы, в первом узле анализа второй вход (n+2)-ro элемента ИЛИ группы соеди- . нен с выходом элемента НЕ, в i-H узле анализа выхоц элемента НЕ подключен дополнительно к первому входу (и+2)-ro элемента И второй группы, выход которого соединен с вторым входом (n+2)-ro элемента ИЛИ группы, выход (n+2)-ro элемента ИЛИ группы (i-1)-ro узла анализа соединен с третьим входом (n+2)-го элемента И первой группы и вторым входом (n+2)-го элемента И второй группы, i-го узла анализа, выход (n+2)-го элемента

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

15 установки в "0" которого подключен к входу сброса устройства.