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

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

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

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

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

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

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

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

15 информационный выход каждого j-ix .узла анализа, где i 1, 2,..., п, j 1, 2,..., га, г. - число сравниваемых чисел, m - количество разрядов в сравниваемых числах, соединен с J-M

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

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

30 j-ro узла анализа соединен с J-MH

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

В устройстве каждый из узлов анализа содержит регистр, три группы элементов И, элемент ИЛИ-НЕ, счетчик, причем вход управления записью узла анализа соединен с управляющим входом регистра, пряной выход каждого |-го разряда которого подключен к первому входу i-ro злемег та И первой группы, выход каждого i-ro элемента И первой группы соединен с i-M информационным выходом узла, прямой выход (п - 1)-го разряда регистf a. подключен к первым входам первого и второго элементов И второй группы, прямой выход п-го разряда регистра соединен с первым входом третьего элемента И второй группы и с втоpfcw. входом первого элемента И второй группы, прямые выходы (п- 1)-го и rt-ro разрядов подключены к вторым входам второго и третьего элемен- , тов И соответственно второй группы, управляющий вход узла анализа соединен с третьими входами элементов И второй группы и с управлякяцим входом счетчика, выход которого подключен к второму входу каждого элемента И первой группы, выход первого, второго и третьего элементов И второй группы соединен с первыми входами первого, второго и треткего элементов И соответственно третьей группы,выходы первого, вторю го и третьего элементов И третьей группы подключены

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

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

Устройство содержит m узлов анализа 1, 1 2- г 1п7 каждый из которых состоит из первой группы элементов И 2vj, 2,..,, 2f,, элемента ИЛИНЕ 3, счетчика 4, второй группы элементов И 5-,, 2, 5з, регистра б, третьей группы элементов И 7, l, 131 группу выходных элементов ИЛИ 8

БП, элементы ИЛИ-НЕ 9-13,

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

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

С помощью элементов И 5 произвол; дится анализ содержимого двух старших разрядов каждого регистра 6;j , i 1, 2,..., возникновении в них комбинаций 11, 10, 01, соответственно, формируются,, сигналы кА выходах элементов и Ъ, 5,, 5. Эти сигналы поступают: с выходов всех элементов И 5J| (i 1,..., m) на вход элемента ИЛИ 15, с выходов всех элементов каждого t -го узла анализа 1, где i 1,...., m, на вг.оды элемента ИЛИ-НЕ 11 с выходов элементов И 5j кажддго i-ro узла анализа на входы элемента ИЛИ-НЕ 9, таким образом, на выходе элемента ИЛИ 15 формируется единичный сигнал в случае появления комбинации Ц в двух старших разрядах хотя бы одного из сравниваемых чисел, на выходах элементов ИЛИ-НЕ 11 и 9 формируется сигнал нулевого уровня в том случае, если в двух сравниваемых разрядах чисел хотя бы раэ попадаются комбинации 10 или 01, соответственно. Сигнал с выхода элемента или 15 блокирует через элемент ИЛИ-НЕ 12 нулевой сигнал с элемента ИЛИ 11 так, что единичный сигнал на выходе элемента ИЛИ-НЕ 12 формируется только в случае отсутствия в старших разрядах сравниваемых чисел комбинации 11 и наличия хотя бы одной комбинации 10. Аналогично нулевой сигнал с элемента ИЛИ-НЕ 9 блокируется через элемент ИЛИ-НВ IQ единичными сигналами с элемен-. тов ИЛИ 16 и ИЛИ-НЕ 12 так, что единичный сигнал на выходе элемента ИЛИ-НЕ 10 является лишь в случае отсутствия в двух старших разрядах

сравниваемых чисел комбинаций 11, 10 и наличия ХОТЯ бы одной комбинации .01. В случае отсутствия в двух; старших разрядах сравниваемых чисел комбинаций 11, 10, 01 на выходах элементов ИЛИ 16, ИЛИ-НЕ 12 и 10 формируются нулевые сигналы, которые, поступая на входы элемента ИЛИ-НБ 13, формируют на его выходе единичный сигнал.

При наличии комбинации 11 в двух старших разрядах хотя бы одного из сравниваемых чисел, сигнал с элек8ента ИЛИ 15 откроет первые в группах элементы И 7 для прохождения сигналов с элементов И 5, аналогично, если единичный сигнал сформирован на выходе элемента ИЛИ-НЕ 12 то будут сформированы сигналы на вто рых в группах элементов И 5. Аналогично при отсутствии комбинаций ц 10 и наличии 01 в старших разрядах сравниваемых чисел единичный сигнал будет сформирован на выходах элементов И S. Формируемые таким образом сигналы с выходов элементов И 7 вместе с сигналом с элемента ИЛИ-НЕ 13 поступают на входы элементов ИЛИ-НЕ 3, на выходе каждого i-го которого нулевой сигнал форми1руется в случае наличия в двух старших раэрядах i-ro регистра кода максимальной величины по сравнению с другими регистрами или в случае/ ког да в двух старших разрядах всех регистров окажется комбинация 00. На выходах остальных элементов ИЛИ-НЕ 3 формируются сигнсшы единичного уровня, которым устанавливаются в нуль соответствующие разряды управляющего регистра 19, нулевой сигнал с выходов которых блокирует посредством элементов И 5 участие чисел, код двух старших разрядов которых меньше максимального, в последующих тактах сравнения.

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

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

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

0 записывается на регистр 18 результата.

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

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

20

1. Устройство для определения экстремального числа, содержащ(эе N узлов анализа, группу выходных элементов ИЛИ, регистр результата, управ25ляквдий perjicTp, элементы задержки, элементы ИЛИ, ИЛИ-НЕ, причем, i-й информационный выход каждого j-ro узла анализа, где. 1, 2,..., п, j 1, 2,..., ТВ, п -число сравнивае30мых чисел, m - количество разрядов в сравниваемых числах, соединен с J-M входом г-го выходного элемента ИЛИ гоуппы, выход каждого i-ro выходного элемента ИЛИ группй под35ключен к j-му входу регист ра результата, управляющий выход каждого i-ro узла анализа соединен с J-M входом управляющего регистра, каждый j-й выход которого подключен к управляющему вхоДу j-ro узла анали.40за, отличающееся тем, что, с целью повышения быстродействия, в нем первый и вторЬй выходы зультата каждого j-ro узла ангшиза соединен с j-ми входами первого .

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

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

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