Устройство для определения максимального из @ -двоичных чисел Советский патент 1985 года по МПК G06F7/04 

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

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ .МАКСИМАЛЬНОГО ИЗ гт ДВОИЧНЫХ ЧИСЕЛ , содержащее гг групп элементов И по п-1 элементов И в каждой группе, где п- число разрядов сравниваемых чисел, -tn групп элементов памяти по п элементов памяти в каждой группе, п многовходовых элементов ИЛИ анализа разрядов, m элементов ИЛИ обнуления, управляющие элементы И, регистр результата, причем прямой выход каждого i-ro элемента памяти группы, где i 1,2,...,r,k 1,2,...., m соединен с k-м входом i-ro элемента ШШ анализа разряда, выход которого подключен к первому входу .i-ro управляющего элемента И, выход которого соединен со входом установки в единичное состояние i-ro разряда регистра результата, выход j-ro управляющего элемента И, где j 1,2,...,ri-1 подключен к первым входам i-x элементов И всех групп, второй вход j-ro , элемента И 1с-й группы подключен к инверсному выходу j-ro элемента памяти k-й группы, выход (n-l)-ro элемента И группы соединен с первым входом k-ro элемента ИЛИ обнуления, выход которого подключен к входу установки в нулевое состояние h-ro элемента памяти k-й группы, отличающееся тем, что, с целью повышения быстродействия, в устройство введены п-1 элементов И обнуления, п-2 элементов И анализа разрядов, многовходо- вый элемент И и генератор импульсов, вход запуска которого подключен к входу запуска устройства, а выход соединен с вторыми входами всех управляющих элементов И, управляющим входом многовходового элемента И и инверсными входами всех i элементов И обнуления, прямой вход j-ro элемента И обнуления подключен, (Л к выходу j-ro разряда регистра резул тата, а выход соединен с первыми входами установки в нулевое состояние J-X элементов памяти всех групп, вторые входы установки в нулевое состояние элементов памя- , ти со второго по (п-1)-й груп 1 пы объединены и подключены к входу со установки в нулевое состояние п-го 4: элемента памяти k-й группы, выход р-го элемента И группы, где р 1,2,...,п-2, соединен с (р-«-1)-м оо входом k-ro элемента ИЛИ обнуления, выходы многовходовых элементов ШШ анализа разрядов подключены к инверсным входам многовходового элемента И, выход которого является выходом окончания поиска устройства, выход первого многовходового элемента ШШ анализа разрядов подключен к инверсному входу второго управляющего элемента И, первый инверсный вход р-го элемента И анализа разрядов подключен к выходу (р+1)-го мно

1

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

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

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

Устройство содержит гп групп элементов И , , 1 , 1 ,....

элементов памяти 2,2....2,2,

2 9 9 TTQ .«,,, эле

ментов ИЛИ 3%3,.....,3 обнуления, п- многовходовых элементов ИЛИ анализа разрядов 4.Ag4, управляющие элементы И 5 ,5 ... .5,, (п-2) элементов И анализа разрядов 6

, ВХОД 7 запуска устройп-2

ства, генератор 8 импульсов, многовходовый элемент И 9, регистр 10 результата, (ri-1) элементов И обнуления 11, 11,11п-1(1) sbiходы 12, 122....12 элементов И 11j являются вторыми установками в нулевое.состояние j-ой группы элементов 2j памяти, 13 - выход окончания поиска устройства.

Назначение элементов устройства следующее. Элементы 2 памяти, где

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

, ессигналы разрешения, например

ли хотя бы Б ОДНОМ из чисел анализируемого разряда в элементах 2 памяти присутствует 1.

Элементы И 5 , где i 1,2,...,п и элементы И 6р, где р 1,2,..., (п-2) служат для последовательного анализа разрядов всех чисел и соответствующего стробирования тех разрядов, которые содержат хотя бы в одном из чисел 1 в соответствующем разряде.

Элемент И 9 служит для выработки сигнала окончания операции поиска максимального числа на выходе 13 устройства, причем сигнал на выходе

элемента И 9 появляется лишь при обнуленных состояниях всех элементов 2 памяти, т.е..когда отсутствуют сигналы разрешения с выходов элементов И1Ш 4- .

Элементы И 11; где j 1,2,

(п-1) служат для выработки сигнала обнуления соответствующего разряда -ой группы элементов 2 памяти по

.окончанию такта перезаписи 1 состояния в регистр 10 результата.

Регистр 10 результата служат для формирования двоичного п-разрядного кода максимального из m двоичных чисел.

Генератор 8 импульсов служит для выработки тактов синхронизации, обепечивающих последовательное формирование стробирующих импульсов при анализе разрядов чисел, начиная со старших разрядов. Запуск генератора 8 происходит по сигналу, поступающему на вход 7 запуска устройства.

3

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

Перед началом работы в элеменIf

ты 2 V памяти заносятся m двоичных чисел, причем в первую группу элементов 2 памяти заносят все старшие разряды m двоичных чисел,далее в последующие группы заносятся все разряды чисел в порядке убывания старшинства разрядов, а в группе злементов 2 памяти заносятся все младшие разряды m двоичных чисел. Регистр 10 результата обнуляется.

В устройство по входу 7 поступае сигнал начала операции, по которому осуществляется запуск генератора 8 импульсов. Генератор 8 импульсов вырабатывает серию импульсов стробирования дпя элементов И 5, элемента И 9, элементов И 1Ь , причем сигналом разрешения для элементов И 5. и элемента И 9 является сам тактовый импульс, а для злементов И 11- - отсутствие тактового импульса на их первых входах.

В случае 1, если хотя бы в одном из элементов 2 памяти 1-ой группы, где 1 1,2,, т, в старшем разряде записана 1, то сигнал через элемент ИЛИ 4 поступает на второй вход элемента И 5 , разрешая прохождение строб-импульса с генератора 8 импульсов. При этом сигнал поступает в регистр 10 результата и записывает в него 1 в этом разряде, а также этот сигнал поступает на вторые входы элементов И 1 данного разряда. Если в I.-OM числе, 1 1,2,.m этот разряд установлен в О состояние, то с инверсного выхода элемента 2 памяти снимается разрешающий потенциал, открывающий элементы И 1 и через элемент ШЖ 3 поступает сигнал установки в нулевое состояние по первым входам элементов 2 памяти, в которых и хранится tc-oe число. Данное число исключается из процесса поиска максимального из m двоичных чисел. По окончанию первого импульса, генератора 8 импульсов на первом вхде элемента И 11 появится сигнал разрешения, а поскольку по первому такту в старшем разряде регистра 10 уже записана 1, то срабатывает элемент И 11 и на его выходе 12 появляется сигнал установки в нуле734084

вое состояние всех старших разрядов элементов 2 памяти, т.е. проанализированные разряды элементов 2 . памяти обнуляются. 5 В случае 2, когда исследуемые

числа имеют нулевые значения в старшем разряде (), то с выхода элемента ИЛИ 4 на второй вход элемента И 5 поступает сигнал Запрет 10 а на третий вход элемента И 5 этот сигнал уже разрешающий (по входу он инвертируется). При этом, если хотя бы в одном из чисел в следующем разряде () имеется 1, то срабатывает элемент ИЛИ 2 разрешая тем самым прохождение первого стробимпульса с генератора 8 через второй элемент И Sj. Срабатывает элемент И 5 и сигнал с его выхода 0 . поступает в регистр 10 результата и записывает 1 в этом разряде, а также на вторые входы элементов И 1 где 1 1,2,....т. Если в числе данный разряд равен нулю, то

5 с инверсного выхода элемента 2 ПАМЯТИ данного разряда снимается разрешающий потенциал, открывающий . . элемент И 1 и через элемент ИЛИ 3 поступает сигнал установки в нулевое

0 состояние по первым входам элемен- . тов 22 памяти, в которых и хранится k-oe число. Таким образом, уже первым строб-импульсом производится перезапись единичного значения после-

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

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

В случае 3, когда и в старшем и .в последующих разрядах (, ) во всех исследуемых числах только нулевые значения, то с выхода элеJJ ментов ШШ 4 и 4 поступает запрет на вторые входы соответствующих элементов И 5 и 5 . Эти самые сигналы с выходов элементов ИЛИ 4 и 42, например нулевого потенциала,

J уже вызывают срабатывание элемента ШШ 6 за счет инверсии сигналов, поступающих на его входы. Разрешающий потенциал с выхода элемента ИЛИ 6 разрешает срабатывание по третьему входу элемента И 5 и по второму входу элемента И 6. Далее, если хотя бы в одном из чисел еледующий разряд () имеет значение 1, то срабатывает элемент ИЛИ 4 и на второй вход .элемента И 5- постпает сигнал разрешения. Первым строб-импульсом происходит перезапись 1 в соответствуюпщй разряд регистра 10 результата, а также обнуляются все элементы памяти тех чисел, которые имели в этом () разряде нулевое значение как ив предьщупшх случаях. По окончанию строб-импульса с выхода 12j элемента И 11з сигнал обнуляет, все элементы 2 памяти (). Аналогично производится анализ и стробирование последующих разрядов.

Далее производится анализ и стробирование последу1рщих j-разрядов w чисел, запись 1 в соответствующие разряды регистра 10 результата, есл хотя бы у одного анализируемого j -разряда исследуемых 1. чисел была 1. Если в -ом числе данный j-ты разряд имеет нулевое значение, то с инверсного выхода элемента 2 памяти данного разряда поступает разрешение последовательно в соответствующем такте через элемент И 5j, первьй элемент И 1 элемент ИЛИ 3 для установки в нулевое состояние по первым входам элементов 2j памяти, в которьрс хранилось число. По окончанию стробимпульса происходит обнуление элементов памяти 2 простробированного j-разряда всех m чисел.

Таким образом, осуществляется анализ значащих (ненулевых) разрядов чисел и перенос такта стробирования на первый значащий разряд,тем самым сокращается время формирования результата в регистре 10. Кроме того, в каждом такте еще выбывают из анализа все числа, имеющие в стробируем1згх разрядах нулевые значения, и обнуляются все проанализированные значащие разряды. Причем в каждом такте импульсов с генератора 8. импульсов производится опрос... состояний всех разрядов всех чисел на О. Если в хбде опроса элемента И 9 по его стробирующему входу поступит импульс в момент, когда выбыли из анализа все числа, а максимальное число имеет в оставшихся разрядах нулевое значение, то на выходе элемента И 9 формируется сигнал об окончании операции. Это позволяет досрочно определить максимальное число, при этом число N тактовых импульсов меньше количества п разрядов исследуемых чисел.В результате поиска по сигналу с выхода 13 устройства в регистре 10 сформированный двоичный код максимального из tn двоичных чисел может быть записан во внешнее устройство.

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