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

 

Изобретение относится к области вычислительной техники и предназначено для слайсовой сортировки потоков . дискретной информации. Целью изобретения является расширение области пpи eнeния за счет возможности определения чисел в пределах заданных граничных значений. Устройство содержит элементы ИЛИ и НЕ и п каналов анализа по количеству сравниваемых чийел, каждый из которых включает триггеры, элементы И, мультиплексор, элементы ИЛИ-НЕ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы НЕ. Устройство осуществляет сравнение чисел, поступающих старшими разрядами вперед, с определением максимального или минимального чисел в зависимости от заданного режима при соблюдении граничных условий и выдает числа, меньшие или равные нижней границе диапазона, попадакицие в интервал между заданными границами диапазона, числа, большие или равные верхней границе, и числа, ближайшие к нижней границе снизу и к верхней сверху. 1 ил. (Л

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

СОЦ)4АЛИСТИЧЕСНИХ

РЕСПУБЛИН

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

° llO ДЕЛАМ ИЗОБРЕТЕНИЙ И 0THPbfAO

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

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

"т- r (21) 3769902/24-24 (22) 05.07.84 (46) 23.04.86. Бюл. Ф 15 (72) И.А. Карасев, И.Л. Корнеев, В.И. -Кухников, В.А. Минькович, В.А. Пучков, А.Н. Собакин, В.Л. Таубкин и А.Х. Усманов (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

У 840884, кл. G 06 F 7/02, 1979.

И.К. Юэн. Устройство для последовательной побитовой максимизации и сортировки. — ТИИЭР, т. 68, В 2, февраль 1980. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ЭКСТРЕМАЛЪНОГО ЧИСЛА (57) Изобретение относится к области вычислительной техники и предназначено для слайсовой сортировкипотоков . дискретной информации. Целью иэобре„,SUÄÄ 122 441 A . 1бц 4 С 06 F 7/02 тения является расширение области применения за счет воэможности определения чисел в пределах заданных граничных значений. Устройство содержит элементы ИЛИИ НЕи h каналов анализа по количеству сравниваемых чисел, каждый из которых включает триггеры, элементы И, мультиплексор, элементы ИЛИ-НЕ, элемент ИСКЛЮЧАЮЩЕЕ

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

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

12? 6441

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

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

Устройство содержит канал 1 анализа, триггер 2, вход "Пуск" 3, элемент И 4, элемент НЕ 5, элемент И 6, (ъ-входовый элемент ИЛИ 7, вход 8 синхронизации, триггер 9, элемент

И 10, вход 11 нижней границы диапазона, элемент НЕ 12, вход 13 сравнивающего числа, триггер 14, элемент

И 15, элемент НЕ 16, триггер 17, элемент И 18, элемент НЕ 19, вход 20 верхней границы диапазона, триггер 21 элемент И 22, элемент И-НЕ 23, элемент И-НЕ 24, элемент И-HE 25, элемент И-НЕ 26, мультиплексор 27, вход

28 считывания результата, элементы

ИЛИ-НЕ 29 и 30, вход 31 блокировки, элемент ИЛИ-НЕ 32, выход 33, элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ 34, вход 35 задания типа экстремума.

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

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

Затем сравниваемые числа А,=(в;Д и значения нижней P1=(P.j и aepx>ieto

Р2= 1Р „- границ диапазонов, где ,; = 1, 2,..., т, — номер числа, =1., 2,, rri — номер разряда, представленные в позиционном двоичном коде, поступают поразрядно, старшими разрядами вперед, соответственно по входу 13 и входам задания некией 11 и верхней 20 границ диапазонов на соответствующие входы каждого канала

1 предложенного устройства, причем число с номером поступает на вход

j --ro канала, а значения нижней Р1 и верхней Р2 границ диапазонов являются общими для всех каналов 1.

В каждом канале 1 сравниваемое число поступает на вход элемента ИСКЛ10ЧАИЩЕЕ ИЛИ 34, а также на входы элементов И 15 и 18 и элемент HE 12, на входы элементов И 10 и 22., Значение границы Р1=-(P; } поступает на вход элемента И 10 и через элемент

НЕ 16 на вход элемента И 15, а значение верхней границы Р2=1Р посту1 пает на вход элемента И 22 и через

5 элемент НЕ 19 на вход элемента И 18.

Элементы И на каждом такте реализуют соответственна функции

F1=a, . P., IJ (2) F2=a, Р, ij (3) УЗ=а.. P

2j (4) F4 а.. Р

2j где à, P

Ь 1 9

Р. и а

9J !J Р

20 Р Р

ZJ соответственно прямые и инверсные значения соответствующих разрядов сравниваемых чисел и границ диапа25 занан, а элемент ИСК %ЧАЮЩЕЕ ИЛИ 34 выполняет раль управляемого иннертора, который н зависимости от потенциала на входе 35, общем для всех каналов 1, иннертирует или не инвертирует инфармацию с входа t3, что позволяет использовать предлагаемое устройство как для поиска 1 аксимального, так и минимальнога из чисел. В режимах устройства, связанных с поиском максимального из и чисел, на входе

35 необходимо задать низкий потенциал, соответствующий уровню логического "0"., а в режимах, связанных с

4б поиском минимальнага из чисел — высокий потенциал, соответствующий уровню логической "!

Так как вначале нсе триггеры каждого канала 1 устройства находятся в единичном состоянии, то нсе г1 элементов И 6 открыты и наибольшие значащие разряды (НЗР) всех чисел А. (!

1, 2..., и проходят на входы h -входового элемента ИЛИ 7, общего для g всех каналов, на входе которого сос,тояние логической "1" будет н там случае, когда не все разряды н данном сечении — нули. При появлении импульса на вход 8 синхронизации и состоянии логической "l" на выходе -нходонаго элемента ИЛИ 7, триггер 2 каждого канала 1, в котором находится число с нулевым разрядом при поиске

1226441

А (Р1

А =Р1

Р сА <Р2

\ (9) (10) f5

А. )Р2

ext 2

А Р1 ех42

А. > Р2 (12) (13) 20 (14), А,. (. Р2 (8) F4=1 максимума (или единичным при поиске минимума), устанавливается в нулевое состояние, указывая тем самым, что данное число в дальнейшем сравнении не участвует, поскольку при этом соответствующий элемент И 6 будет заперт и не пропустит на вход и -входового элемента ИЛИ 7 следующие разряды данного числа. В конце л циклов, где п — разрядность сравниваемых чисел, триггер 2, сохранивший единичное состояние, будет соответствовать экстремальной величине, Одновременно с поиском экстремума происходит поразрядное сравнениекаждого из ь чисел значениями нижней Р„ и верхней Р границ, так как из соотношении (1) (4) и того, что сравнение происходит начиная с НЗР, следует, что появление логической "1" на входе соответствующего элемента И эквивалентно выполнению следующего условия:

F1=1 A. ; Р1 (5) I F2=1 — А, ) Р1 (6) 1

F3=1 — — А. ) Р2 (7) При появлении импульса на входе

8 синхронизации и наличии логической

"1" на выходе элемента И происходит сброс соответствующего триггера в нулевое состояние. Таким образом, результаты (S) — (8) сохраняются до конца сравнения соответственно в трйггерах 9, 14, 17 и 21 каждого канала 1. Наличие связи между выходом триггера 14 и третьим входом элемента И 10, запрещающей сброс триггера 9 в том случае, если предьдущими разрядами был сброшен триггер 14, атакже между выходом триггера 21 и третьим входом элемента И 18, запрещающий сброс триггера 17 в том случае, если предьдущими разрядами был сброшен триггер 21, обеспечивает сохранение правильного результата сравнения для случая, когда младшие разряды меньшего из чисел в паре (A, Р1) или (А, Р2) окажутся

I I больше соответствующих разрядов большего из чисел в соответствующей опаре. Прямые выходы триггеров 9 и 10, триггеров 9 и 17, инверсный выход триггера 9и прямой выход триггера 2, а также инверсный выход триггера 17 и прямой выход триггера 2 попарно объединяются с -помощью элементов

И-НЕ 23-26 соответственно. Таким образом, после циклов, где гт — разрядность сравниваемых чисел, на информационных входах мультиплексора

27, с которым соединяются выходы элементов И-НЕ 23-26 и прямой выход триггера 9, присутствуют результаты

10 следующих функций: где i=1 2,...,и — номер числа а

ext 2

У

А. — экстремальное число, причем

ext2 " с

А, =А; — максимальное из и чисел если по входу 35 при сравнении поддерживается потенциал логичесн н аxt g мин кого 0, и А. =A. — миниI ( мальное из и ччииссеелл, если на входе 35 поддерживается потенциал логической "1".

С помощью задания соответствующего кода на входах 28 результат любой

35 из функций (9) — (14) может передаваться на выход мультиплексора 27.

Выход первого элемента ИЛИ-НЕ 29 соединяется с выходной шиной 33 данных.

Схема, состоящая из элементов

40 ИЛИ-НЕ 29, 30 и 32, позволяет (если это требуется) задать приоритет каналу 1 с младшим номером в том случае, если несколько чисел одновременно удовлетворяют выбранной функции.

45 Приоритет может быть установлен или не установлен путем задания соответствующего потенциала на вход 31 блокировки. Если на входе 31 поддерживается потенциал логической "1", то выход элемента ИЛИ-НЕ 30 находится в состоянии логического "0" и сигнал на выходе элемента ИЛИ-НЕ 29, соединенном с выходом 33, полностью определяется состоянием выхода мульти55 плексора 27 ° Если же на входе 31 поддерживается состояние логического

"01, то сигнал на его выходе зависит от состояния выхода элемента ИЛИ-НЕ

5 1

32 предыдущего канала 1. Если на выходе элемента ИЛИ-НЕ 32 предыдущего канала 1 состояние логического

"0", то первый элемент ИЛИ-НЕ 29 данного канала 1 блокируется логической "1" с выхода элемента ИЛИ-НК

30, т.е. состояние его выхода не зависит от выхода мультиплексора 27., а выход элемента ИЛИ-НЕ 32 данного канала 1 повторяет состояние выхода элемента ИЛИ-НЕ 32 предыдущего канала 1 и блокирует все последующие каналы 1. Если же на входе элемента

ИЛИ-НЕ 32 предыдущего канала 1 логическая " 1", то сигнал на выходе элемента ИЛИ-НЕ 29 данного канала 1 определяется состоянием выхода мультиплексора 27, В этом случае возникновение сигнала логическои "l" на выходе элемента ИЛИ-НЕ 29., соединенном с выходом 33, в канале с номером влечет появление сигнала логического "0" на выходе элемента ИЛИ-НЕ

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

Р2 границами, больших границ Р2, ближайших к границе Р1 снизу, бли-жайших к границе Р2 сверху„ поиск экстремальных чисел при собл ".денни граничных условий.

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

Устройство для определения экс-тремального числа, содержащееt- -входовый элемент ИЛИ, где — количест;. во сравниваемых чисел, и г, каналов анализа, каждый из которых содержит первый и второй элементы И, элемент НЕ и триггер, вход установки в которого подключен к входу

"Пуск устройства, а вход установки в "0" — к выходу первого элемента И, первый вход которого через элемент

НЕ соединен с первым входом второго элемента И, а второй вход подключен к прямому выходу триггера, выходы вторых элементов И всех каналов анализа подключены к выходам ts †входового элемента ИЛИ, выход которого подключен к второму входу первого элемента И каждого канала анализа,, о т л и ч а ю щ е е с я тем, что, с

22бАА1 Ь целью расшире ния области приме не ния

= à счет возможности определения чисел в пределах заданных граничных значений, в него введены два элемента IIE, а в каждый канал анализа— три элемента ИЛИ-НЕ, элемент ИСКЛЮЧА10ЩЕЕ ИЛИ, мультиплексор, четыре элемента И-НЕ, второй элемент НЕ, элементы И, с третьего по шестой элементы, и с второго по пятый триггеры, причем в каждом канале анализа входы установки в "1 всех триггеров подключены к входу "Пуск" устройства, входы синхронизации всех триггеров соединены с входом синхронизации устройства, вход задания типа экстремума соединен с первым входом элемента ИСКШОЧА10ЩЕЕ ИЛИ i -го канала анализа, где =1,2,..., в, -и канале анализа выход элемента

ИСКГ10ЧЛОЩЕЕ ИЛИ подключен к первому входу второго элемента И, а второй вход соединен с входом i-го сравниваеп. .ого числа устройства, с первыми входами третьего и четвертого элементов И и через второй элемент

НŠ— с первыми входами пятого и шестого элементов И, вторые входы которых подключены к входам соответственно верхней и нижней границ диапазона, выходы третьего, четвертого, пятого и шестого элементов И подключены к входам установки в 0" оответствепно второго, третьего, :-четвертого и пятого триггеров, прямые выходы второго и пятого триггеров соединены с третьими входами соответственно пятого и четвертого элементов И, выход первого триггера соединен с первыми входами первого и второго элементов И-НЕ, вторые входы которых подключены к инверсным выходам соответственно четвертого и третьего триггеров, прямой выход четвертого триггера подключен к первому информационному входу мультиплексора и первым входам третьего и четвертого элементов И-НЕ, вторые вхоцы которых соединены с прямыми выходами соответственно третьего и второго триггеров, выходы третьего и четвертого элементов И-НЕ подключены соответственно к третьему и второму информационным входам мультиплексора, четвертый информационный вход которого подключен к прямому выходу третьего триггера, выходы первого и второ— го элементов И-НЕ соединены соответст1226441

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

Редактор Т. Кугрышева Техред В.Кадар Корректор С.Шекмар

Заказ 2134/48

Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 венно с пятым и шестым информационными входами мультиплексора, управляющие входы которого соединены с входами считывания результата устройства, а выход подключен к первому входу первого элемента ИЛИ-НЕ, выход которого является 1 -м выходом устройства и соединен с первым входом второго элемента ИЛИ-HE второй вход которого подключен к второму входу 10 первого элемента ИЛИ-HE и выходу третьего элемента ИЛИ-HE первый вход которого соединен с входом блокировки устройства, второй вход третьего элемента ИЛИ-HE j -ro канала анализа где j =-.2,3,..., и, соединен с выходом второго элемента ИЛИ-НЕ (a -1)-ro канала анализа, второй вход третьего элемента ИЛИ-HE первого канала анализа подключен к входу логической "1" устройства.