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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик («)962920 (61) Дополнительное н авт. свид-ву (22) Заявлено 15.12.80 (21) 3216441/18-24

Ре1М К,З с присоединением заявки ¹â€”

G 06 F 7/04

Государственный комитет

СССР но делам изобретений н открытий (23) Приоритет— ($3) УДК 681. 325. . 5 (088. 8) Опубликовано 300982. Бюллетень ¹ 36

Дата опубликования описания 30,09.82

И.П. Дробязко, В.И. Корнейчук, А.П. Марковский, В.Н. Сороко и В.П. Тарасенко (72) Авторы изобретения. (71) Заявитель

Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО

ЧИСЛА

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

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

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

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

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

Цель изобретения — повьпаение быстродействия.

Пдставленная цель достигается ð тем, что в устройстве для определения экстремального числа, содержащем и узлов анализа, группу выходных элементов ИЛИ, регистр результата, управляющий регистр, элементы задержки, элементы ИЛИ, ИЛИ-НЕ, причем l-й информационный выход каждого J-го узла анализа, где = 1, 2,..., п, j = 1, 2,..., rn, r, — число сравниваемых чисел, щ — количество разрядов в сравниваемых числах, соединен с J-м входом 1-го выходного элемента ИЛИ группы, выход каждого t--го выходного элемента ИЛИ группы подключен к

J-.ìó входу регистра результата, управляющий выход каждого 1-го узла анализа соединеí с 1-м. входом управляющего регистра, каждый J-й выход которого подключен к управляющему входу j-го узла анализа, первый и второй выходы результата каждого -го узла анализа соединен с )-ми

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

Четвертого и пятого элементов ИЛИ-HE и второго элемента ИЛИ, выход второго элемента ИЛИ-НЕ подключен к третьему входу четвертого элемента ИЛИНЕ, выход которого соединен с третьими входами блокировки узлов анализа и с третьими входами пятого элемента ИЛИ-НЕ и второго элемента ИЛИ, .выход пятого элемента ИЛИ-НЕ подключен к четвертому входу второго элемента ИЛИ и к четвертому входу блокировки узла анализа.

В устройстве каждый из узлов анализа содержит регистр, три группы элементов И, элемент ИЛИ-НЕ, счет- 35 чик, причем вход управления записью узла анализа соединен с управляющим входом регистра, прямой выход каждого i-го разряда которого подключен к первому входу i-ro элемента И 4Q первой группы, выход каждого i-го элемента И первой группы соединен с

i-м информационным выходом узла, пря-. мой выход (n — 1)-го разряда регистра подключен к первым входам перво- . го и второго элементов И второй группы, прямой выход и-ro разряда регистра соединен с первым входом третьего элемента И второй группы и с вторьм. входом первого элемента И второй группы, прямые выходы (n- 1)-ro и п-го разрядов подключены к вторым входам второго и третьего элементов И соответственно второй группы, управляющий вход узла анализа соединен с третьими входами элементов И второй группы и с управляющим входом счетчика, выход которого подключен к второму входу каждого элемента И первой группы, выход первого, второго и третьего элементов И вто-,60 рой группы соединен с первыми входами первого, второго и третьего элементов И соответственно третьей rpynma,выходы первого, второго и третьего элементов И третьей группы подключены к первому, второму и третьему входам элемента ИЛИ-НЕ, выход которого соединен с управляющим выходом узла, первый, второй и третий входы блокировки узла подключены к вторым входам первого, третьего и второго элементов И соответственно третьей группы, четвертый вход блокировки узла анализа соединен с четвертым входом элемента ИЛИ-НЕ.

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

Устройство содержит m узлов ана1 .1, 1 1,..., 1, каждый рых состоит из первой группы элементов И 2, 21,..., 2„, элемента ИЛИНЕ 3, счетчика 4, второй группы элементов И 5„, 51, 5, регистра 6, третьей группы элементов И 7, 7, 7, группу выходных элементов ИЛЙ 8.„

81,..., 8л, элементы ИЛИ-НЕ 9 — 13, элементы ИЛИ 14 и 15, элементы 16 и 17 задержки, регистр 18 результата, управляющий регистр 19, вход 20 запуска устройства.

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

С помощью элементов И 5 произво дится анализ содержимого двух старших разрядов каждого регистра 6

1, 2,..., m,ïðè возникновении в них комбинаций "11", "10", "01", соответственно, формируются сигналы на выходах элементов И 5, 5, 5" . Эти сигналы поступают: с выходов всех элементов И 5„(i = 1,..., m) на вход элемента ИЛИ 15, с выходов всех элементов 5 каждого i-го узла анализа 1, где i = 1,.:., m, на в.оды элемента ИЛИ-НЕ 11 с выходов элеменТоВ И 5З каждого i ãî узла анализа на входы элемента ИЛИ-НЕ 9, таким образом, на выходе элемента ИЛИ 15 формируется единичный сигнал в случае появления комбинации "11" в двух старших разрядах хотя бы одного из сравни".,аемых чисел, на выходах элементов ИЛИ-HE 11 и 9 формируется сигнал нулевого уровня в том случае, если в двух сравниваемых разрядах чисел хотя бы раз попадаются комбинации "10" или "01", соответственно. Сигнал с выхода элемента ИЛИ 15 блокирует через элемент

ИЛИ-НЕ 12 нулевой сигнал с элемента ИЛИ 11 так, что единичный сигнал на выходе элемента ИЛИ-НЕ 12 формируется только в случае отсутствия в старших разрядах сравниваемых чисел комбинации "11" и наличия хотя бы одной комбинации "10". Аналогично нулевой сигнал с элемента ИЛИ-НЕ 9 блокируется через элемент ИЛИ-HH 1g единичными сигналами с элементов ИЛИ 16 и ИЛИ-НЕ 12 так, что единичный сигнал на выходе элемента ИЛИ-HE 10 является лишь в случае отсутствия в двух старших разрядах

96?920 сравниваемых чисел комбинаций "11", "10" и наличия хоти бы одной комбинации ."01".,В случае отсутствия в двух старших разрядах сравниваемых чисел комбинаций "11", "10", "01" на выходах элементов ИЛИ 16, ИЛИ-HE

12 и 10 формируются нулевые сигналы, которые, поступая на входы элемента ИЛИ-НЕ 13, формируют на его выходе единичный сигнал.

При наличии комбинации "11" в двух старших разрядах хотя бы одного из сравниваемых чисел, сигнал с элемента ИЛИ 15 откроет первые в группах элементы И 7„ для прохождения сигналов с элементов И 5,, аналогично, если единичный сигнал сформирован на выходе элемента ИЛИ-НЕ 12, то будут сформированы сигналы на вторых в группах элементов И 51 . Аналогично при отсутствии комбинаций "11", "10" и наличии 01" в старших разрядах сравниваемых чисел единичный сигнал будет сформирован на выходах элементов И 5З. Формируемые таким образом сигналы с выходов элементов И .7 вместе с сигналом с элемента ИЛИ-НЕ 13 поступают на входы элементов ИЛИ-НЕ 3, на выходе каждого

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

На выходах остальных элементов

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

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

Выдача сигнала любых из элементов ИЛИ 15, ИЛИ-НЕ 12, ИЛИ-НЕ 10, ИЛИ-НЕ 13 формирует единичный сигнал на выходе элемента ИЛИ 14, который, пройдя через элемент 16 задержки, поступает на счетный вход счетчика 4 и на упра:,,ляющие входы регистров 6, вследствие чего производится сдвиг хранимых в них чисел на два разряда и начинается следующий такт.

Пбсле n/2 тактов числа в регистрах 6 установятся в исходное состояние, а все разряды управляющего регистра 19, кроме одного (или нескольких, если есть несколько равных максимальных чисел}, соответствующего максимальному числу, ус5 !

О

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

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

40 тановлены в нулевое состояние, эакрывая через элементы И 2 выдачу на регистр 18 результата всех чисел, кроме максимального. По сигналу переполнения счетчика 4, поступающего на входы элементов И 2, элементом И

2, соответствующим номеру максимального числа, формируется сигнал считывания максимального числа, которое через группу открытых указанных сигналов элементов И 2 и элементы ИЛИ 8 записывается на регистр 18 результата. .Предлагаемое устройство позволяет сократить время определения максимального числа за счет анализа сразу двух разрядов всех чисел в два раза.

1. Устройство для определения экстремального числа, содержащее М узлов анализа, группу выходных элементов ИЛИ, регистр .результата, управляющий регистр, элементы задержки, элементы ИЛИ, ИЛИ-НЕ, причем i-й информационный выход каждого j-го узла анализа, где i = 1, 2,..., n„

j = 1, 2, ;, е, n †чис сравниваемых чисел, m " количество разрядов в сравниваемых числах, соединен с

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

i-го узла анализа соединен с j ì входом управляющего регистра, каждый j-й выход которого подключен к управляющему входу j -го узла анализа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в нем первый и вторбй выходы результата каждого j--го узла аналидами блокировКи узлов анализа и с

962920 вторыми входами четвертого и пятого элементов ИЛИ-НЕ и второго элемента ИЛИ, выход второго элемента ИЛИ-HE подключен к третьему Уходу четвертого элемента ИЛИ-НЕ, выход которого соединен с третьими входами блокировки узлов анализа и с третьими входами пятого элемента ИЛИ-НЕ и второго элемента ИЛИ, выход пятого элемента ИЛИ.-НЕ подключен к четвертому входу второго элемента ИЛИ и к четвертому входу блокировки узла анализа, 2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что в нем каждый из узлов аналйза содержит регистр, три групйы элементов И,. элемент ЙЛИ-НЕ, счетчик, причем вход управления записью узла анализа соединен с управляющим входом регистра, прямой выход каждого I-го разряда которого подключен к первому входу I-го элемента И первой группы, выход каждого I-по элемента И первой группы соединен с.1 :-м информационным выходом узла, прямой выход (п - 1)-го разряда регистра подключен к первым входам первого и второго элементов- И второй группы, прямой выход и-го разряда регистра соединен с первым входом третьего элемента И второй группы и с вторым входом первого элемента И второй группы, прямые выл

ВНИИПИ Заказ 7513/68

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

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

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

Источники информации, принятые во внимание при экспертизе

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

9 328450, кл. С 06 I 7/04, 1970.

2. Авторское свидетельство СССР по заявке Р 2886600/18-24, кл. G 06 F 7/04, 1980 (прототип) .