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

со

00

4

00 Сл

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

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

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

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

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

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

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

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

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

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

,

5

0

5

0

5

0

5

0

5

устройства. На входы 7рц (,т, k 1,п+1) подаются коды Р-ых разрядов К-ых дпоичных чисел, причем на входы поступает пороговое число, а на остальные информационные входы подаются п анализируемых двоичных чисел.

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

Для удобства рассмотрения работы узлов анализа будем полагать, что блок управления отсутствует, а на вторые входы упомянутых элементов И 2ц поданы единичные потенциальные уровни.

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

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

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

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

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

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

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

Если же на некоторое подмножество открытых элементов И 2j поступят с соответствующих входов 7, (q б J) единичные сигналы, а на остальные открытые элементы И 2 () - нулевые сигналы, то на выходе элемента ИЛИ 4 и на выходах элементов ИЛИ За будут сигналы единичного уровня, а

на выходах элементов ИЛИ 3 - нулевого уровня.

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

В результате поразрядного сравнения (п+О-ых двоичных чисел на информационных выходах 8; (,m) устройства формируется двоичный код максимального из сравниваемых чисел, а элементы ИЛИ За () m-ro узла анализа, на выходах которых формируется код единицы, определяют порядковые номера найденных максимальных чисел (их может быть несколько).

Рассмотрим процесс замещения найденного максимального числа на нулевое число. Этот процесс осуществляется с помощью блока управления. Для удобства рассмотрения положим, что все элементы И 14ц (,п) закрыты, например, нулевым потенциалом на входе 20 задания режима работы, а триггер 13р., находится в нулевом состоянии.

Допустим,что в некоторый момент времени максимальным оказалось число с порядковым номером f (fin). Тогда возникший на выходе элемента 11ПИ 3. т-го узла анализа уровень логической единицы, пройдя элемент 11, задержки и элемент И 12,, открытый в этот момент времени единичным уровнем на инверсном выходе триггера 13п+| , опрокинет по S-входу триггер 13| в единичное состояние. Возникший при этом нулевой потенциал на инверсном выходе триггера 13/ закроет элементы И 2 всех узлов анализа. В результате этого на информационных выходах 8; (,т) и адресном выходе 9 устройства появляется код нуля, что указы- вает на замещение найденного максимального числа на нулевое.

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

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

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

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

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

циалом на инверсном выходе триггера 13.,,.

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

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

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

Если же среди п анализируемых чи- сел имеется число (допустим, с порядковым номером f), равное заданному, то оба эти числа будут найдены одновременно. Однако спустя время t| за- ,данное число обнулится, а равное ему число с порядковым номером f будет зафиксировано на информационных и соответствующем адресном выходах устройства, поскольку элемент И 12 запретит прохождение импульса на S-вход триггера 13, и последний останется в исходном состоянии.

Перейдем к рассмотрению работы устройства в режиме поиска ближайшего

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

Допустим, что заданное число меньше максимального из п анализируемых чисел.

В рассматриваемом режиме работы

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

0

0

,

0

0

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

, (1) где t, - время задержки элементов 1 1

(,n+1), задержки; t - длительность фронта скачков напряжения на выходах триггеров 13 (временем задержки в элементах 12|, пренебрегают) .

Момент опрокидывания триггера 13„, в единичное состояние запаздыП г 1

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

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

Поскольку элементы И 14ц (,n) постоянно открыты по четвертым входам единичным потенциалом на входе 20 задания режима работы, а по третьим входам постоянно открыты единичным потенциалом на выходе элемента И-НЕ 17, что будет показано ниже, по после опрокидывания в единичное состояние триггера 13

n+i

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

7 Т ) т«и

где - минимальный период опрокидьшания триггера, определяющий его быстродействие, триггер 13. опрокинется из единичного в нулевое состояние, что обеспечит восстановление числа с порядковым номером f в качестве максимального.

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

и

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

Из (2) и (3) легко найти необходимую величину t| задержки элемента 11к (,n+1) задержки:

t) T n+Tn-tqp .

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

0

5

0

5

0

5

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

Удержание заданного числа в качестве максимального происходит в течение времени Ту, равного длительности импульса на выходе элемента ИЛИ 3j,, m-ro узла анализа. Поэтому на

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

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

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

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

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

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

жения, а триггер i--.,

13 ,,1 -. опрокинется в единичное состояние, запретив при этом прохождение импульсов через элементы И 12j; (,n).

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

И

в результате запретов элементов 11ц и И 14 триггеры будут

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

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

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

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

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

0

5

0

5

0

5

д 5

0

5

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

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

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

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