Устройство для объединения множеств

 

Изобретение относится к вычислительной технике. Цель изобретенияповышение быстродействия устройства. Устройство содержит два счетчика, четыре группы элементов И, две группы элементов ИЛИ, блок памяти, два регистра, два дешифратора, компаратор и блок управления. В устройстве для объединения множеств каждый зпемент множеств А и В выбирается только один раз. При этом коды элемеитоп каждого множества должны быть отсортированы по возрастанию. 3 ил. ю N3 00 00 ЧаЕ

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (19) ®U(ll! (50 4 G 06 Г 15/38.

"4

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К AB mPCHOIVIV СВИДЕТЕЛЬСТВУ, 1

;,1

ГОСУДАРСТБЕИИЫЙ КОМИТЕТ СССР пО делАм изОБРетений и QTHpblTHA (21) 38921 73/24-24 (22) 29.04.85 (46) 23.12,86, Бил. 11» 47 (72) Б.C..Бугумпрский, В.Я.Яцук и B.A.Ïàëàãóøèí (53) 681.325(088 ° 8) (56) Авторское свидетельство СССР Р 666545, кл. G Об Р 15/38, 1979.

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

l1 1119373, кл, G Об Р 15/38, 1984. (54) УСТРОЙСТВО ДЛЯ ОБЪЕДИНЕНИЯ МНО" ЖЕСТВ (57) Изобретение относится к вычислительной технике. Цель изобретения— повьппепие быстродействия устройства.

Устройство содержит два счетчика, четыре группы элементов И, две группы элементов ИЛИ, блок памяти, два регистра, два дешифратора, компаратор и блок управления. B устройстве для объединения множеств каждый элемент множеств A и В выбирается только один раз. При этом коды элементов каждого множества должны быть отсорTHpOBQHbl IIO o3 T H . 3 KI

)278890

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

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

На фиг.\ приведена схема устройства; на фиг.2 — схема блока управления; на фиг.З вЂ” схема микропрограммы работы устройства.

Устройство (фиг.l) содержит счетчики 1 и 2, группы 3-6 элементов И, группы .7 и 8 элементов ИЛИ, блок 10 памяти, регистры 11 и 12, дешифраторы 13 и 14, схему 15 сравне«ия, выходы которой обозначены позициями 16 и !7, блок 18 управления, выходы которого сбозначе«ы позициями 19-24, а входы — 25-28, ". руппы 29 и 30 адресных входов, группу 31 информаци" снных выходов, устансвоч«ый вход 32, ВХОД 33 запуска и сиг«альный выхОД

34 устройства, Блок 18 упра>зления (фиг.2) выпслпе«пс кяпсропрограммнсму прш ципу.

0«содержит счетчик 35, узел 36 памя" ти кома«д, дешифратор 37, группу 38 элементов И, генера-ор 39 импульсов, ЗО элементы ИЛИ 40 и 41, элементы 42-44 задержки, элеме«ты И 45-61 и регистр

62, Выход элемента ИЛИ 40 соеди«ен с входом Остансва генератора импульсов„ вход запуска которого соединен с входом 33., выход элемента 42 задержки соед1шеп с управляющим входом . группы 38, выход элемента 43 задержки соединен с устаповсчным входом

40 счетчика 35, счетный вход которого соеди«ен с выходом элемента 44 задер;кки, выход генератора 39 соединен с управля|ощим входом регистра 6?, остальные связи яс«ы из чертежа.

В каждоьл блоке хемы микропрограммы работы устройства (фиг.3) изображены выполняемые микрссперацни.

Узлы устройства представле«ы позициями на фиг.1 и 2. Справа от черты ь прямоугольном блоке отмечается выход блока 18, ". Од действием импульса на котором выполняется соответствующая юпсрооперация. Позиции,. заключенные в скобки, определяют содержимое соответствующих узлов устройства либо состояние выходов соответствующих узлов устройства.

Стрелка внутри блока схемы обозначает пересылку информации.

Пусть А и  — множества. Тогда обьединение двух множеств А и В— это множество С = AlJB составленное из элементов, каждый из которых принадлежит, по крайней мере, одному из множеств А или В. Каждое множество хранится в блоке 10 памяти, причем элементы множества представлены кодами чисел, отсортированы по возoGcTBHHIo и находятся в смежных ячейках. За последним элементом множества следует уникальный код (например, нулевой), расшифрсвываемый дешифраторами 13 и 14. Этот код называется кодом конца множества.

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

При включении питания устройство устанавливается в исходное состояние импульсом с входа 32, по которому (через элемент ИЛИ 40) генератор 39 импульсов переводится в запертое состояние, и с задержкой, необходимой для окончания переходных процессов в блоке 18, в счетчике 35 формируется адрес первой микрокоманды микропрограммы работы устройства, записанной в узле 36 памяти команд. При этом из него выбирается первая микрокоманда, состоящая из кода микрооперации, который подается на входы дешифратора 37, и кода адреса следующей микрсксманды, сн появляется на второй группе выходов узла 36, сое" диненной с вхсдамя регистра 62. Код первой микрооперации расшифровывается дешифратором 37 и появляется сигнал на его первом выходе (слева по схеме). По группам 29 и 30 входов в счетчики 1 и 2 записываются адреса первых элементов множеств А и В.

Устройство готово к работе.

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

39, который начинает выдавать импульсы тактовой частоты. Первый импульс с выхода генератор", 39 проходит через открытый элемент И 45 на выход

19 блока 18 ° При этом содержимое счетчика 1 через группы 3 элементов

И и 7 элементов ИЛИ подается в блок

10 памяти, из которого выбирается первый элемент множества A. Кроме того, адрес следующей микрокоманды принимается в регистр 62. После это1278890 го появляется импульс на выходе элемента 42 задержки, который открывает группу 38 элементов И, разрешая запись в счетчик 35 адреса следующей микрокаманды, который из регистра 62 переписывается B счетчик 35. В даль.нейшем нь>барка микрокоманд из узла

36 памяти команд и их расп>ифро>зка праизВОдятся аналогичнО, Код нтарОЙ микраоперации приводит к появлению импульса на ныхаце 20 блока 18, в результате чего первый элемееет множества А принимается в регистр 11, а содержимое счетчика увеличивается на единицу (формируется адрес следующего зле е»та еп>ожестна A). !!р е выполнении следу>оп>ей микрокаманд>! появляется и: пульс» l I L!F,,е 21 С .Гака 18 и адрес первого элемента множества Б через группы 4 элементс1н И и 7 элементе>в III!I< пост ПЯРТ B б>.а;;

l Q памяги,;; ре..q:лп,тате Ee„ o i:; r E o выходах паянляется ПРрный е>1>сь>ент множества В, Ilu следующей мнкракo— маиде возникает имп льс на выходе 2? блока 18 и первый элемепт множества

Б принимается в регистр 12, а са1..ержимас счет писа ? унеличиваетсн на единицу (формируется адрес следующего элемента мна;кестна В) . .Если на регистр 1! и/нли т>егис:p

12 принят код конца множества, та деп1ифратор 13 и/илн 14 вьецает с1>гнал.

Схема 15 сран»е1>>>я сраннинает co .,сржимое регистра» 11 и 12. Если содержимое рег1п тра i:мень>пе садерж!!мого регистра 12 (r,е. кад первого зле !c!lта множества Л и"ньше кода пернаг0 элемента множества В), то появляется сигнал на выходе 16, если же ани равныу To пОявляетс» сиг>еал на ныхО де 17.

Иа следующей микро!;аманде иаян..еяется импульс на выходе элемента И 5! . ,Если в регистрах 11 и 12 находятся коды конца м»ожестна, та этот импульс .проходит через элемент Il 57, элеме>ге .HJIH 4i и с задержкой, необходимой для принятия н счетчик 35 адреса следующей микрокаманды, подается на счетньп> вход счетчика 35, унеличиная его содержимое на едипицу. В пратиьном случае адрес следующей микрокаманды не изменяется. Таким образом, осуществляется разнетвление н мн>;рапраграмме н загиснмости ат ньп>алнения каких-либо условий.

Если в регистрах II и 12 находятся коды конца множества, то по следу>ап>е>й микрокоманде появляется нмпу1» с на ныходе элемента II 56, кото5 р! Ле проходит FIB сеп нальный ныхОд 3-> свидетельствуя об окончании выполнения Операции объединения множеств Л и В. Этим >ке импульсам устройство перенодится н исходное состояние. !

О В противном случае ныбираетсч ь>>п<ракаманда пО которо>е иаявх>яется импульс на Гыхаде элемента И 52. По этому импульсу осуществляется разветвление н миесропрограмме в заниси-!

5 м,>стн ат сп".E>e!!.:E на выходе деп>и<Ьра. о ;! 13, Ес»:е н регистре 11 пахадится >;п! конца множества, та несбхсди:>а !!CPn,:!, . re !i;! >>! !F.O EE E Ус ГРОЙСтва нсе оставшиеся элементы множества Б.

20 Поэтому по следующей микрокоманде появляется пмly;E>,с»а выходе 24 блока 18, па которому очередной элемент мна;кестна В из регистра 12 через открытую группу 6 элементов И и групп, 8 элементов Ш1И проходит на группу 3! ныходон н качестве очередного элемента множества С. Затеи выбирается третья микракоманда. Если н регистре 11 не находится код конца мно30 жестна, то по следующей иикракаманде псяеляется импульс на выходе элемен..а И 53, по которому анализируется

c1ãE!;Fë на ныхадс деши41!затора 14.

35 Есл! и рег>стре 12»е код конца ила>постна, то па -.ыходе деши(111ратара !

4 улегай сигнал. В этом случае следующей выбирается микракоманда, па которой появляется имгульс на выходе I0 элемента И 5 ;. При этом осуществляется разнстнле>гиp D микропрограмме н завпспмастп ат C«. E>as>a lla выходе 16 схемы 15 сравнения. Если на этом выходе еди>шчный сигнал (т. е. очередной элемент множества Л меньше очереднагo элемента множества В), та необходима передать очередной элемент множества А на выход устройства.

Для зтага вь>бирается микрокоманда, 50 по которой появляется импульс на выходе 23 блока 18. По этому импульсу открь>нается группа 5 элементов И и очередной элемент множества А нз регистра 11 проходит на группу 31 вы55 ада" в качестве очередного элемента ме>c åeстна С . Эта ж0 мнкрО>";ома>>д В! > пал»яется н случае, когда н регистра ! »ахадптся кад каш.а мна;кестна1278890

По двум следующим микрокомандам в регистр 11 из блока 10 памяти принимается код следу3ощего элемента множества Л, а содержимое счетчика 1 увеличивается на единицу. После этого Вновь осу35;Йств)1яется анализ с13гна JoB на выходах дешифраторов 14 и 13.

Если на Выходе 16 czech»i 15 сраВпения нулевой сигнал, то Выбирается микрокоманда. по которой появляется импульс на в,ыходе элемспта И 55.

Этим импульсом анализируется сигнал на выходе 17 схемы 15 сравнения. ЕсЛ33 13а Эт031 53ЫХО>т,Е ПРИСУтСтВУЕт ЕДКПП3та (ОЧЕРЕД31ЫЕ ЭЛЕМЕНТЫ 1)НО>жОСТ>З Л и Е равн3.1), то а Группу 31 Выходов

Выдается очерецной элемент мпожестБэ. Л а затем осущес3 влястся переХОД К ЧТЕ31ИЮ СЛЕg)>JOJJJEIZ Э)1Е JPEITÎB л3110жеств Л и 1), Б противном случае

ОСУ3>31ЕСТВЛ51Е7 С51 ВЫДа:1Э. От)ЕРСДНОГО ЭЛЕл1ептa b«IO).-:;eeтва E >.

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

Устройство для объецтгпенкя множеств, соцержащее первый, второй счет -т 3кк >7е1)>33>В1> В Г00031> ТPBTHEI >

;eTBe1)тый блоки элементов И, первый .к Второй блоки элементов ИЛИ, блок

Пам тТИ >таI)БЫй И В7 ОРОй Pei ИСТPbl первый II В 1 Орой дешиф3)атОры> схему сравнения и блок управлсния, причем

ВхОд с>др оса элел!ептО j IIер1301 О м110 жЕСТБа УС7 Pойетва СОЕДИ11033> С Кт1фоР31ат)11ОН31>3Л1 1)ХОДОМ ПЕРВОГО СЧЕтЧККа, выходы первог0 к Бто1)о "0 счетчиков соединены соответствепно с первымк

ВХОД7" IH пе1)БОГО и Вт01)ОГO блОков элеме1ггов И, Выходы которых соедкнеE1bi соо 1 ВетственнО с пeрвым и Вт01)3>1м входами первого блока элементов ИЛИ, выход которого сосдш1еп с адресным б)тока JIBJb>53 TEE соецгпIен с 1ии1)орма33ионпым ВхоДОМ

If epE3 о I 0 р еГистр а > B! Iход i(OTOpor 0 со ецкнеп с первь3м входом схелть3 сравнения H первь)м входом третьегo блока элемснт013 И БыхОДы тт)етьего и четблоков 3iieMeEJTQB И coeJ),HEIPJIbI е00 TÁ(.. Т СТ В СНН О С IIePJJE>131 «1 B 7OPbIM ВХО далат 3)торого б 1ока э ie«eJJT0B ИЛ1, вы"

ХОд кoTOpoI 0 JIB)IJIeTc51 инфс1)мационным

Выходом устройства., установочный

ВХОД H Г>ХОД ЗаПУСКа ">> С ГР 033СТБ а СО Сдинены соответстг>етп10 с первым и Вто— рым 1)ходами блока управления, первый ьыхОд J

И, со счетным входом Второго счетчика, с вторым Входом третьего блока элементов И и с вторым Входом четвертого блока элементов И, Выход первого дешифратора соединен с третьим входом блока управления, седьмой выход которого соединен со счет133>3л1 входом первого счетчика и входом а1иси 11ервого регистра, о г л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия, информационгIый 3)хОд BTop01 0 сче7 чика соеди нсн с входом адреса элементов ВтороГо множества устройства, Выход первого регистра соединен с входом первого дешифратора, Выход блока памяти соедкнен с и31форл1аци031313>г>1 Входом вто25 рого регистра, гыход которого соедипеп с вторым Входом схемы сравнения, с пергым Входом четвертого блока элементов И и входом второго дешифратора, выход которого соединен с четвертым вхоцом блока управления, пятый к шестой входы которого соединены с ВыхОДОм PGBEIO H БВIхО,ЦОм NQEIE>333e схемы сравнения соответственно, четвертый Вых д блошка управления соединен с входом записи второго регистра, З5 причем блок управления содержит счетчик команц, узел памяти ког1апд, регистр, дешифратор команд, первую группу из двенадцати элементов И, Вторую к третью группы элементов И, первый, Второй, третий элементы задержки, reHeратор импульсов, 3тервый, второй и треткй элементы ИП1, первый

Вход первого элемента ИЛИ соединен с первым Входом блока управления, Вы5 ход первого элемента ИЛИ соединен с

Входом останова генератора импульсов, Второй Вход блока управления соединен с входом запуска генератора, выход которого соединен с первьмк вхоl О

) дами первой группы элементов И блока управления, вторые входы первой группы элементов И блока управления соединены с Выходами дешифратора команд, причем выходы первого, второго, тре>

-т" ть его, четвертого, пятого, шестого элементов И первой:.-руппы блоха управления соединены =оответственно с

Бторьм, седьмым, третьим, четвертым, I

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

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

1278890

1278890

Составитель В.Коряковцев

Редактор В,Иванова Техред A,Кранчук, Корректор С. Шекмар

Заказ 6841/49

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

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4