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

 

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

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (л)5 G 06 F 7/04

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4763764/24 (22) 28.11.89 (46) 07.12.91. Бюл. N 45 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) О.В.Гуленко, В,И.Корнейчук, А.П,Марковский и А.Ю,Михайлюк (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

М 1314334, кл. G 06 F 7/04, 1986, Авторское свидетельство СССР

N 1043634, кл. G 06 F 7/04, 1982. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ МАКСИМАЛЬНОГО ЧИСЛА (57) Изобретение относится к автоматике и вычислительной технике, в частности к устИзобретение относится к автоматике и вычислительной технике, в частности к устройствам сортировки данных, и предназначено, например, для электронных цифровых систем повышенного быстродействия, выполненных на узлах с большой степенью интеграции.

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

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

Устройство содержит л rovnn элеменмяти, m групп элементов И 2>, 2z,...,2 -p,, 21, 22,.„, 2n->,...,21, 2m,...„2n-1, п много„,,5UÄÄ 1697076 А1 ройствам сортировки данных, и предназначено; например, для электронных цифровых систем повышенного быстродействия, выполненных на узлах с большой степенью интеграции, Целью изобретения является повышение быстродействия и расширение области применения за счет возможности восстановления исходной информации. Устройство содержит m групп элементов 1 памяти, m групп элементов И 2, п многовходовых элементов ИЛИ 3, и управляющих элементов И 4, и элементов НЕРАВНОЗНАЧНОСТЬ 7„регистр 8 результата, и восстанавливающих элементов И 9. В конце работы устройства код максимального числа фиксируется на регистре 8 результата, а информация на элементах 1 памяти восстанавливается в первоначальном виде. входовых элементов ИЛИ 3.1-3.п, п управляющих элементов И 4.1 — 4.п, вход 5 начала работы, выход 6 конца работы, п элементов

НЕРАВНОЗНАЧНОСТЬ 7.1 — 7.п, регистр 8 результата, и восстанавливающих элементов И 9.1 — 9 и.

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

БИС с использованием различных технологий либо в виде платы с использованием серийных ИМС малой и средней степени интеграции серий К155, К531, К555. При выполнении устройства по последнему вариантус использованием, например, ИМС серии К155 элементы 1 памяти могут строиться нэ микросхемах К155ТВ9; причем вхо1897076 ды S vf R могут быть использованы для "«anf си информации в элемент 1 памяти, вход: и К объединены и образуют вход инвертирования состояния элемента 1 памяти, вхсд синхронизации С и вход синхронизации р»- 5 гистра 8 результата объединены и подсоединены к внешнему источнику тактирук1щих сигналов, Элементы И 2, 4, 9 можно выполнять с использованием И1ЛС К155ЛИ1, мнаговходовыые элементы ИЛИ 3-с;,0 использованием, ИМС К155ЛЛ1, элементы

НЕРАВНОЗНАЧНОСТЬ 7 — с испonüýoâàíèем ИМС К155ЛП5. Регистр 8 результата выполняют в виде набора триггеров., реализуемых, например, микросхемами 15

К155ТВ9, причем выводы S vf R испальзуют для установки в 1 Всех разрядов оегистрэ

8 при приведении устройства в исходнгс состояние, вход I подключен к источнику потенциала логического нуля, а вход К пад- 20 соединен к выходу соответствующе-о элемента НЕРАВНОЗНАЧНОСТЬ 7.

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

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

Сигнал начала операции подают на вход 30

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

Пусть для произвольного Х -: — Р, d1 „ х, ог,...,dr„(гх и ) — позиции (начиная са х х старших разрядов) нулей в записл кода чис- 35 ла Х, И пусть далее В (= Й.— искомое макс,;мальное число на множестве Q. Так как не существует такого У О, чта d1 > d 1, .о очевидно,, что на выходах элемен-,ав ИЛИ

З.т(т < с1 ) формируются едлничные пстенциалы, открывающие соответствуюц„ие у;1равляющие элементы И 4.т для .прохождения сигнала с входа 5. На выходе многовходового элемента ИЛИ З.d1 фоо45 мируется нулевой потенциал, который;cfкрывает управляющий элемент И 4,d1 для прохождения сигнала с входа 5. Соответственно, на выходе элемента НЕРАВНОЗНАЧНОСТЬ 7.аi формируется

50 единичный сигнал (так как потенциалы на втором входе и выходе элемента Л 4,d) не

В, совпадают), который поступает нэ инвертирующие входы всех элеме TcB

1 1,1Я „„,1 Я, в памяти и на вход уст:нонки в нуль d1 -гс разряда регистра 8 рВ зультата. Па приходе перепада тактового импульса переключаются в инверсное ссстояние все элементы 1Д,1Я „„, I,II, в памяти v ус анавливается в нуль о1 -ый разБ ряд регистра 8 результата. Поскольку элемент Д памяти устанавливается в единицу появляется единичный потенциал на выходе элемента ИЛИ З.d1 который отB крывает управляющий элемент И 4.d1 для в про.<а>кден 151 единичного сигнала с выхода элемента И 4 di -1 (или непосредственно с входа 5 .при d; =1). Элементы И 4.g

Б (d1

З,d2 оказывается нулевой потецинал, кото8 рый закрывает элемент И 4.d2 v., так как

Б потенциалы на втором входе и выходе последнега не совпадают формируется единичный потенциал HB выходе элемента

НЕРАВНОЗНАЧНОСТЬ 7.сЬ, которым инвертируется содержимое элементов

"lq(,1ß,...,1 1, памяти и устанавливается в нуль d2 -ыи разряд регистра 8 результата. в

Соответственно открь;вается элемент И

4. d2

Аналогична происходят инвертирование соответствующих элементов памяти 1 и установка в нуль разрядов оегистра 8 реБ Б в зультата в позицияx сказ, dл, бгв

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

2 111 элементов (1„„,

4,1 — 4.п на выход 6 устройства, Так как все разряды di,(12,...,d регистра 8 результаБ, Б В та установл.-ны в нуль(остальные нахсдятся в единичном, исходном, состоянии), то код на регистре 8 резуль.,ата является кодом максимального числа В G. !I2, Нулевые разряды регистра-8 результата соответствуют инвертированным столбцам элементсв 1 памяти. Единичные сигналы с инверсных выходов упомянутых разрядов

d1,d2,...,df поступа1от на входы элеменВ В 8 тов И 8 v по появлению сигнала на выходе

:;ncмента И 4,8: (открывающего элементы И

9) г18ооходят на выход элементов И 9.d1

9.d2 .„„9,d2 ...„9.d(!I далее на входы соВ В ответствующих элементов НЕРАВHQ=,НАЧ110CTb 7 (на другие даа их входа поступают единичные сигналы), так Tc на выходах элементов НЕРАВНОЗНАЧНОСТЬ 7,с11, 7,d2 „...7,(багз формируются единичные сигВ в налы, которые инвертируют ранее инвертированные в процессе поиска элементы 1 памяти, восстанавливая тем самым их ис.(opI-Ioe состояние.

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

1697076 элементах 1 памяти хранятся числа (п-8, m=5):

1 0 0 ", 1 0 0 1

1 1 1 0 1 1 0 1

1 0 1 0 1 0 1 0

0 1 1 1 1 1 0 0

0 0 1 0 1 0 1 0

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

1 0 0 0 1 0 0 1

1 1 1 1 1 1 0 1 20

1 0 1 1 1 0 1 0

0 1 1 0 1 1 0 0

0 0 1 1 1 0 1 0

После первого такта сигнал с входа 5 распространяется через открытые элемен- 25 ты И 4.1 — 4.6 до входа закрытого элемента

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

1 0 0 0 1 0 1 1

1 1 1 1 1 1 1 1

1 0 1 1 1 0 0 0

0 1 1 0 1 1 1 0 35

0 0 1 1 1 0 0 1 а на регистре 8 результата фиксируется код

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

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

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

50 по и-1 элел1ентов И, и многовходовых элементов ИЛИ, регистр результата, и управляющих элементов И, причем вход н ала работь, устройств: подключен к первому входу первого управляющего элемента И, выходы первы элементов памяти всех групп соединены с первыми входами первых элементов И соответствующих групп и входами первого многовходового элемента ИЛ И, выход р-го элел1ента И в каждой группе, где р=1,2,...n-2, соединен с первым входом р+1-го элемента И той же группы, выходы J-ых элементов И всех групп, гдеj — 1,2 (n-1), соединены с входами )+1-го многовходовсго элемента И.:::И, выход j+1-го элемента памяти s xaæäo;t группе соединен с вторым входом j- o элемента И соответствующей группы, вхсды установки в нулевое состояние i-ых элементов памяти всех групп, где =1,2,...,п, обьединены, отл ич а ю щ ее ся тем, что,с целью повышения быстродействия и расширения области применения за счет возможности восстановления исходной информации, в него введены и элементов НЕРАВНОЗНАЧНОСТЬ и п восстанавливающих элементов

И, причем выход j-го управляющего элемента И подключен к первым входал j+1-ro управляющего =-лемен «а И v. j+1-го элемента

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

i-го многовходового элемента ИЛИ, выход

i-го элемента НЕРАВНОЗНАЧНОСТЬ подключен к входа:: установки в нулевое состояние i-x элементов памяти всех групп и входу установки в нулевое состояние i-ro разряда регистра результата, инверсный выход которого подключен к первому входу

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

Составитель Е.Иванова

Техред M.Ìoðãåíòàë Корректор М,Кучерявая

Редактор T.Ôåäîòîâ

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 4306 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5