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

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

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

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

Устройство содержит jn групп элемен.тов11Т,12Г...,1п1;11г,1221пг...1Л12т1nmnaмяти, m групп элементов И 2i . 2г 2n-i ,

2i2, 2222п-122im, 2m22n-im, n MHoroвходовых элементов ИЛИ 3.1-З.п, п управляющих элементов И 4.1-4.П, вход 5 начала работы, выход 6 конца работы, п элементов НЕРАВНОЗНАЧНОСТЬ 7.1-7.П, регистр 8 результата, гТ восстанавливающих элементов И 9.1-9.п.

Устройство для выделения максимального числа может выполняться в виде заказной специализированной БИС с использованием различных технологий либо в виде платы с использованием серийных ИМС малой и средней степени интеграции серий К155, К531, К555. При выполнении устройства по последнему вари - антус использованием, например, ИМС серии К155 элементы 1 памяти могут строиться на микросхемах К155ТВ9, причем вхоо о

XI

О XI

О

ды S и R могут быть использованы для записи информации в элемент 1 памяти, входи I и К объединены и образуют вход инвертирования состояния элемента 1 памяти, вход синхронизации С и вход синхронизации регистра 8 результата объединены и подсоединены к внешнему источнику тактирующих сигналов. Элементы И 2, 4, 9 можно выполнять с использованием ИМС К155ЛИ1, мно- говходовыые элементы ИЛИ 3-е использованием ИМС К155ЛЛ1, элементы НЕРАВНОЗНАЧНОСТЬ 7 - с использованием ИМС К155ЛП5. Регистр 8 результата выполняют в виде набора триггеров, реализуемых, например, микросхемами К155ТВ9, причем выводы S и R используют для установки в 1 всех разрядов регистра 8 при приведении устройства в исходное состояние, вход I подключен к источнику потенциала логического нуля, а вход К подсоединен к выходу соответствующего элемента НЕРАВНОЗНАЧНОСТЬ 7.

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

Перед началом работы все разряды регистра 8 устанавливают в единичное состояние. В элементы 1 памяти заносят m ri-разрядных чисел, образующих множество Q.

Сигнал начала операции подают на вход 5 устройства в виде положительного потенциала.

d2Xd

Пусть для произвольного X О. , di

х.

(гх П ) - позиции (начиная со старших разрядов) нулей в записи кода числа X. И пусть далее В 6 Q- искомое максимальное число на множестве О.. Так как не существует такого YЈ Q, что diY d 1B, то очевидно, i что на выходах элементов ИЛИ

3.t(t d) формируются единичные потенциалы, открывающие соответствующие уп- равляющие элементы И 4л для прохождения сигнала с входа 5. На выходе многовходового элемента ИЛИ 3.di формируется нулевой потенциал, который закрывает управляющий элемент И 4.di для прохождения сигнала с входа 5, Соответственно, на выходе элемента НЕРАВНОЗНАЧНОСТЬ 7.diB формируется единичный сигнал (так как потенциалы на втором входе и выходе элемента И 4.di не совпадают), который поступает на инвертирующие входы всех элементов

1 ,l3f1ffc$, в памяти и на вход установки в нуль diB-ro разряда регистра 8 результата. По приходе перепада тактового импульса переключаются в инверсное состояние все элементы 1d,, в

памяти и ус анавливается в нуль d 1-ый разряд регистра 8 результата. Поскольку элеI&

мент

памяти устанавливается в

10

15

20

25

30

35

40

45

единицу, появляется единичный потенциал на выходе элемента ИЛИ 3.diB, который открывает управляющий элемент И 4.diB для прохождения единичного сигнала с выхода элемента И 4 di 5-1 (или непосредственно с входа 5 п р и Q I 1). Элементы И 4.д (di )также отказываются открытыми единичными сигналами с выходов соответствующих элементов ИЛИ З.д для прохождения сигнала с входа 5. На выходе элемента

3,d2

в

оказывается нулевой потецинал, который закрывает элемент И 4.d2B и, так как потенциалы на втором входе и выходе последнего не совпадают, формируется единичный потенциал на выходе элемента НЕРАВНОЗНАЧНОСТЬ 7.d2B, которым инвертируется содержимое элементов

1di, 1а21 3v памяти и устанавливается в

R

нуль d2 -ый разряд регистра 8 результата. Соответственно открывается элемент И 4.d2B.

Аналогично происходят инвертирование соответствующих элементов памяти 1 и установка в нуль разрядов регистра 8 результата в позициях da , d4 , drBB.

Как только вследствие инвертирования

1 I2Lm

элементов , } открывается

элемент И 4 dm , потенциал с входа 5 проходит через цепочку открытых элементов И 4.1-4.П на выход 6 устройства. Так как все разряды di ,d2 .. ,di регистра 8 результата установлены в нуль (остальные находятся в единичном, исходном, состоянии), то код на регистре 8 результата является кодом максимального числа В б. О. .

Нулевые разряды регистра-8 результата соответствуют инвертированным столбцам элементов 1 памяти. Единичные сигналы с инверсных выходов упомянутых разрядов

diB,d2B,

..,dr поступают на входы элементов И 8 и по появлению сигнала на выходе элемента И 4.п (открывающего элементы И 9) проходят на выход элементов И 9.diB, 9.ci2 9.d2B9.drB и далее на входы со5Q ответствующих элементов НЕРАВНОЗНАЧНОСТЬ 7 (на другие два их входа поступают единичные сигналы), так что на выходах элементов НЕРАВНОЗНАЧНОСТЬ .7.diB, 7,d2B,...,7.dreB формируются единичные сигcg налы, которые инвертируют ранее инвертированные в процессе поиска элементы 1 памяти, восстанавливая тем самым их исходное состояние.

Работа устройства может быть иллюстрирована следующим примером. Пусть на

элементах 1 памяти хранятся числа (, ):

1 О О 1 1001

11101101

10101010

01111100

00101010 Для максимального числа В 11101 01, di 4, d2 7,. Соответственно, при подаче сигнала на вход 5 элементы И 4.1-4.3 открыты для его прохождения, а элемент И 4.4 -закрыт. Единичный сигнал формируется на выходе элемента НЕРАВНОЗНАЧНОСТЬ 7.4 и соответственно инвертируются элементы 1 памяти четвертого столбца и устанавливается в нуль четвертый разряд регистра 8. После первого такта на элементах 1 памяти хранятся коды:

10001001

11111101

10111010

01101100

00111010 После первого такта сигнал с входа 5 распространяется через открытые элементы И 4,1-4.6 до входа закрытого элемента И 4.7. На выходе элемента НЕРАВНОЗНАЧНОСТЬ 7.7 формируется единичный сигнал, которым инвертируется седьмой столбец элементов 1 памяти, та что после второго такта на них хранятся коды:

10001011

11111111

10111000

01101110

О 0 1 1 1 0 0 1

з на регистре 8 результата фиксируется код 111101101 максимального числа, нули в котором указывают на номера столбцов элементов 1 памяти, которые инзертируютсяв третьем такте для восстановления информации на элементах 1 памяти в первоначальном виде.

Формула изобретения Устройство для выделения максимального числа, содержащее m групп пол элементов памяти, где m - число сравниваемых чисел, п - разрядность сравниваемых чисел, m групп

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

0 элемента ИЛИ, выход р-го элемента И в каждой группе, где ,2, . п-2. соединен с первым входом p+1-ro элемента И той же группы, выходы J- ых элементов И всех групп, гдеЛ 1,2 (п-1), соединены с вхо5 дами j-r-1-ro многовходовсго элемент U iM, выход j+1-го элемента памяти в кзждол группе соединен с вторым входом j-ro зпе- мента И соответствующей группы, входы установки в нулевое состояние i-ых элемен0 тов памяти всех групп, где ,2,.. ,п, объединены, о т л и ч а юыееся тем. что, с целью повышения быстоодеГ ствия и расширения области применения за счет возможности восстановления исходной информации, в

5 него введены п элементов НЕРАВНОЗНАЧНОСТЬ и п восстанавливающих элементов И, причем выход j-ro управляющего элемента И подключен к первым входам JH 1-го управляющего элемента VI i j+1-го элемента

0 НЕРАВНОЗНАЧНОСТЬ, первы вход первого элемента НЕРАВНОЗНАЧНОСТЬ подключен к входу начала работы устройства, выход i-го управляющего элемент И соединен с вторым входом 1-го элемента НЕРАВ5 НОЗНАЧНОСТЬ, а второй вход - с выходом i-ro многовходового элемента ИЛИ, выход i-ro элемента НЕРАВНОЗНАЧНОСТЬ подключен к входам установки 9 .нулевое состояние i-x элементов памяти зсех гоупп и

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

5 элемента НЕРАВНОЗНАЧНОСТЬ, выход tiro управпяющего элемента 1/1 подключен к вторым входам всех восстанавливающих элементов И и является выходом конца рз- боты устройства.

0

Изобретение относится к-автоматике и вычислительной технике, в частности к устройствам сортировки данных, и предназначено, например, для электронных цифровых систем повышенного быстродействия, выполненных на узлах с большой степенью интеграции. Целью изобретения является повышение быстродействия и расширение области применения за счет возможности восстановления исходной информации. Устройство содержит m групп элементов 1 памяти, m групп элементов И 2, п многовходовых элементов ИЛИ 3, п управляющих элементов И 4, п элементов НЕРАВНОЗНАЧНОСТЬ 7, регистр 8 результата, п восстанавливающих элементов И 9. В конце работы устройства код максимального числа фиксируется на регистре 8 результата, а информация на элементах 1 памяти восстанавливается в первоначальном виде. сл с