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

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

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

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

Устройство содержит канал 1 анализа, триггер 2, вход Пуск 3, элемент И 4, элемент НЕ 5,- элемент И 6, К-входовый элемент ИЖ 7, вход 8 синхронизации, триггер 9, элемент И 10, вход 11 нижней границы диапазона, элемент НЕ 12, вход 13 сравнивающего числа, триггер 14, элемент И 15, элемент НЕ 16, триггер 17, элемент И 18, элемент НЕ 19, вход 20 верхней границы диапазона, триггер 2 элемент И 22, элемент И-НЕ 23, эле- мент И-НЕ,24, элемент И-НЕ 25, элемент И-НЕ 26, мультиплексор 27, вход 28 считьшания результата, элементы ШЖ-НЕ 29 и 30, вход 31 блокировки, элемент ИЛИ-НЕ 32, выход 33, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 34, вход 35 задания типа экстремума.

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

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

Затем сравниваемые числа и значения нижней . и верхне P2 {p2j} границ диапазонов, где

0 1,2 ,,. ., т , м - номер числа, J 1 „ 2, ..,,п, fri - номер разряда, представленные в позиционном двоичном коде, поступают поразрядно, старшими разрядами вперед, соответственно по входу 13 и входам задания нижней 11

и верхней 20 границ диапазонов на соответствующие входы каждого канала

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

В каждом канале 1 сравниваемое число поступает на вход элемента ИС- КЛЮЧАМЦЕЕ ИЛИ 34, а также на входы элементов И 15 и 18 и элемент НЕ 12, на входы элементов И 10 и 22,, Значение границы P1-(pjj} поступает на

вход элемента И 10 и через элемент НЕ 16 на вход элемента И 15, а значение верхней границы . | поступает на вход элемента И 22 и через элемент НЕ 19 на вход элемента И 18. Элементы И на каждом такте реализуют соответственно функции

, . Р..

и и

. Р . U и

. Р,, F , i

(1) (2) (3) (4)

0

где я;

Р.,,

Р. . наи

Р,

ij

1J г . Р,

7J

5

0

5

0

5

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

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

Так как вначале все триггеры каждого канала 1 устройства находятся в единичном состоянии, то все элементов И 6 открыты и наибольшие значащие разряды (НЗР) всех чисел А. j 1,2, .,., п проходят на входы и-в хо- дового элемента ИЛИ 7, общего для всех каналов, на входе которого сос- .тояние логической 1 будет в том случае, когда не все разряды в данном сечении - нули. При появлении импульса на вход 8 синхронизации и состоянии логической I на выходе h -входо- вого элемента ИЛИ 7, триггер 2 каждого кан;1ла 1; в котором находится число с нулевьгм разрядом при поиске

максимума (или единичным при поиске минимума), устанавливается в нулевое состояние, указывая тем самым, что данное число в дальнейшем сравнении не участвует, поскольку при этом соответствующий элемент И 6 будет заперт и не пропустит на вход и-входо- вого элемента ИЛИ 7 следующие разряды данного числа. В конце Ьп циклов, где 1-п - разрядность сравниваемых чисел, триггер 2, сохранивший единичное состояние, будет соответствовать экстремальной величине. Одновременно с поиском экстремума происходит поразрядное сравнение каждого из h чисел значениями нижней Р и верхней Р границ, так как из соотношении (1) - (4) и того, что сравнение происходит начиная с НЗР, следует, что появление логической 1 на входе соответствующего элемента И эквивалентно вьшолнению следующего условия:

A. : PI

A. PI

(5) (6)

A. P2 (7)

P2

(8)

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

и прямой выход триггера 2 попарно объединяются с помощью элементов И-НЕ 23-26 соответственно. Таким образом, после Ил циклов, где m - разрядность сравниваемых чисел, на информационных входах мультиплексора 27, с которым соединяются выходы элементов И-НЕ 23-26 и прямой выход триггера 9, присутствуют результаты следующих функций:

А. Р1

А. Р1

Р, А Р2

1 I

A. P2 I

ext 2 A: P1

ex

i2

P2

(9)

(10)

(11)

(12)

(13)

(14),

где ,2,...,n - номер числа, a A. - экстремальное число, причем

. dxt 7 «

i максимальное из и чисел если по входу 35 при сравнении поддерживается потенциал логичес- кого О, и АГ - мини- мальное из h чисел, если на входе 35 поддерживается потенциал логичесС помощью задания соответствующего кода на входах 28 результат любой из функций (9) -, (14) может рере- даваться на выход мультиплексора 27. Выход первого элемента ШШ-НЕ 29 соединяется с выходной шиной 33 данных.

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

выход элемента ИЛИ-НЕ 30 находится в состоянии логического О и сигнал на выходе элемента ИЛИ-НЕ 29, соединенном с выходом 33, полностью определяется состоянием выхода мульти- плексора 27. Если же на входе 31 поддерживается состояние логического О, то сигнал на его выходе зависит от состояния выхода элемента ИЛИ-НЕ

S

32 предыдущего канала 1. Если на выходе элемента ИЛИ-НЕ 32 предьщуще- го канала 1 состояние логического О, то первый элемент ИЛИ-НЕ 29 данного канала 1 блокируется логической 1 с выхода элемента ШШ-НЕ 30, т.е. состояние его выхода не зависит от выхода мультиплексора 27 а выход элемента ИЛИ-НЕ 32 данного канала 1 повторяет состояние выхода элемента ИЛИ-НЕ 32 предыдущего канала 1 и блокирует все последующие каналы 1. Если же на входе элемента ИЛИ-НЕ 32 предьщущего канала 1 логическая 1, то сигнал на в.ых,оде элемента ИЛИ-НЕ 29 данного канала 1 определяется состоянием выхода, мультиплексора 27, Б этом случае возникновение сигнала логической 1 на выходе элемента ИЛИ-НЕ 29, соединенном с выходом 33, в канале с номером Р влечет появление сигнала логического О на выходе элемента ИЛИ-НЕ 32 f -ro канала 1 и блокирование всех каналов 1 с номерами, большими Е

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

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

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

25

26441б

целью расширения области применения за счет возможности определения чисел в пределах заданных значен -ш, в него введены два элемен- 5 та ПЕ, а в калодый канал анализа - три элемента ИПИ-НЕ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, мультиплексор, четыре элемента И-НЕ, второй элемент НЕ, элементы И, с третьего по шестой

10 элементы, и с второго по пятый триггеры, прыгаем в каждом канале анализа входы установки в 1 всех триггеров подключены к входу Пуск устройства, входы синхронизации всех

15 триггеров соединены с входом синхронизации устройства, вход задания типа экстремума соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ i-го канала анализа, где ,2,,..,h в

20 ,; -м канале анализа выход элемента ИСКЛОЧ. аОЩЕЕ ИЛИ подключен к первому входу второго элемента И, а второй вход соединен с входом i-ro ваекого числа устройства, с первыми входами третьего и четвертого элементов И и через второй элемент НЕ - с первыми входами пятого и шестого элементов И, вторые входы которых подключены к входам соответст39 венно верхней и нижней границ диапазона, выходы третьего, четвертого, пятого и шестого элементов И подключены к входам установки в О ooт зeтcтвeннo второго, третьего,

.,,- четвертого и пятого триггеров, пря- шле выходы второго и пятого триггеров соединены с третьими входами соответственно пятого и четвертого элементов И, выход первого триггера 4Н соединен с первыми входами первого и второго элементов И-НЕ, вторые входы которых подключены к инверсным выходам соответственно четвертого и третьего триггеров, прямой 5 выход четвертого триггера подключен к первому информационному входу

мультиплексора и первым входам третьего и четвертого элементов И-НЕ, вторые входы которьгх соединены с прямыми

0 выходами соответственно третьего и второго триггеров, выходы третьего и четвертого элементов И-НЕ подключены соответственно к третьему и второму информационным входам мультиплексора,

5 четвертый информационньм вход которого подключен к прямому выходу третьего триггера, выходы первого и второго элементов И-НЕ соединены соответст

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

8

третьего элемента ИЛИ-НЕ, первый вход которого соединен с входом блокировки устройства, второй вход третьего элемента ИПИ-НЕ j-го канала

анализа где i

1де J , J,.. . , , соединен

с выходом второго элемента ИЛИ-НЕ 0-1)-го канала анализа, второй вход третьего элемента ИЛИ-НЕ первого канала анализа подключен к входу логической 1 устройства .

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

ti

а

л а

Адрес

Составитель Е. Иванова техред в.Кадар Корректор С.Шекмар.

2134/48

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

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

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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