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

СНИХСНИХ ВОЗ СОВЕТ ООИАЛИСРЕСПУБЛИ 0 4 С 06 Г 15/38. 13 Ф(57) Изобрет лительной те повышение быс Устройство со четыре группь пы элементов регистра, два тор и блок уп для объединен мент множеств ко один раз. каждого множе тированы по В.3) СССР979.СР 4.УСТРВ Я СУДАРСТБЕИНЫЙ КОМИТЕТ СССРДЕЛАМ ИЭОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗ К АВТОРСКОМУ СВИДЕТ 3892173/24-2429,04.8523.12,86, Бил. Иф 47Б.С.Бугумирский, В.Я,ЯцуА.Палагушин681.325(0888)Авторское свидетельство6545, кл. С 06 Р 15/38, 1вторское свидетельство СС19373, кл, 6 Об Р 15/38,ОЙСТВО ДЛЯ ОБЪЕДИНЕН ЕТЕНИЯ ние относится к вычиснике. Цель изобретения - тродействия устройства. держит два счетчика, 1 элементов И, две груп- ИЛИ, блок памяти, два дешифратора, компараравления. В устройстве ия множеств каждый эле- А и В выбирается тольПри этом коды элемеитов ства должны быть отсорвозрастанюо. 3 ил.Изобретение относится к вычислительной технике и может быть использовано в системах управления банкамиданных.Целью изобретения является повышение быстродействия устройства за счеттого, что кажцое множество просматривается только один раз.На Фиг.1 приведена схема устройства; на Фиг.2 - схема блока управления; на фиг.З - схема микропрограммы работы устройства,Устройство (1 иг.1) содержит счетчики 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 соедцценс входом сстансва генератора 1 цпульсов вход запуска которого соединен 35с входом 33., выход элемента 42 задеркки соедгшеп с управляющим входом. группы 38, выход элемента 43 задержки соединен с устаповсч 1 ипм входом40счетчика 35, счетный вход которогосоединен с выходом элемента 44 задер;кки, выход генератора 39 соединенс управляющим входом регистра 62, остальные связи ясны из чертежа. В ка 7 кдом блоке хемы микропрограммы работы устройства (Фиг.З) изображены выполняемые микрссперацни. Узлы устройства представлены позициями ца Фиг.1 и 2. Справа от черты50 ь прямоугольном блоке отмечается выход блока 18, под действием импульса на котором выполняется соответствующая микрсоперация. Позиции,. заключенные в скобки, определяют содеркимсе соответствующих узлов устройства либо состояние выходов соответствующих узлов устройства. Стрелка внутри блока схемы обозначает пересылку информации.Пусть А и В - ыюжества. Тогдаобьединение двух ьпюжеств А и В -это множество С = АОВ, составленноеиз элементов, каждый из которых принадлежит, по крайней мере, одномуиз множеств А или В, Каждое множество хранится в блоке 1 О памяти, при"чем элементы множества представленыкодами чисел, отсортированы по возрастанию и находятся в смежных ячейках. За последним элементом множества следует уникальный код (например,нулевой), расшифрсвываемый дешифраторами 13 и 14. Этот код называетсякодом конца множества.Устройство работает следующим об"разом,При включении питания устройствоустанавливается в исходное состояниеимпульсом с входа 32, по которому(через элемент ИЛИ 40) генератор 39импульсов переводится в запертое состояние, и с задержкой, необходимойдля окончания переходных процессовв блоке 18, в счетчике 35 формируется адрес первой микрокоманды микропрограммы работы устройства, записанной в узле Зб памяти команд, Приэтом из него выбирается первая микрокоманда, состоящая из кода микрооперации, который подается на входы дешифратора 37, и кода адреса следующей микрсксманды, сн появляется навторой группе выходов узла 36, сое"диненной с вхсдамя регистра 62, Кодпервой мцкрооперации расшифровывается дешифратором 37 и появляется сигнал на его первом выходе (слева посхеме). По группам 29 и 30 входов всчетчики 1 и 2 записываются адресапервых элементов множеств А и В,Устройство готово к работе.Запуск устройства в работу производится импульсом с входа 33. Поэтому импульсу запускается генератор39, который начинает выдавать импульсы тактовой частоты. Первый импульсс выхода генератора 39 проходит через открытый элемент И 45 на выход19 блока 18, При этом содержимоесчетчика 1 через группы 3 элементовИ и 7 элементов ИЛИ подается в блок10 памяти, из которого выбираетсяпервый элемент множества А. Кроме того, адрес следующей микрокомандыпринимается в регистр 62. После это 1278890го появляется импульс на выходе элемента 42 задержки, который открывает группу 38 элементов И, разрешая запись в счетчик 35 адреса следующей микрокоманды, который из регистра 62 переписывается в счетчик 35. В даль. нейп 1 ем ньбарка мцкрокоманд из узла 36 памяти команд и их распирозка произВадЯтсЯ аналагичеза, 1(ад Второй микраоперацци приводит к появлению импульса на выхаце 20 блока 18, в результате чего первый эзеемент множества А принимается в регистр 11, а содержимое счетчикаувеличе 5 зается на едРПццу (ззорлязруется адрес следующего этСлапта ЕпОжества А). Ирвыполнении сзеедуюпей микрокоманды появляется и пузьс на вьха,е 2С.:ока 18 и адрес первого элемента мна - жества Б через группы 4 элелРентав И и 7 элеецтав И 1 И поступает В бза 10 пам 51 ц, в разултате чеа а сО выходах появляется первый эл зле 1 т множества Б, Па следующей мцкрака - маиде возникает импульс на выходе 22 блока 18 ц первый элемент множества Б приимается в регистр 12, а содержимое счетпЕка 2 увеличиваетсн на единицу (фарлРруетс 51 адрес следующего элемента мна;кества Б).Если ца регистр 11 и/цззц 1 егис;р 12 принят код конца множества, та девиоратор 13 и/изп 14 выдает снгна. Схема 15 сразея сравнивает содержимое регистра 11 и 12. Если содержимое регг тра 1меньше садер:1:.11 лОго регистра 12 (т,е, кад первого элСмсцта множества Л и"ньше коета первого элемента множества В), то появляется сигнал ца выходе 16, если же анн равееы, то паявляетс сигнал на зьходе 17. Па следующей микрокоманде 105551- ется импульс на выходе элемента И 5. ,Если в регистрах 11 и 1 находятся коды конца множества, та этот импульс .проходит через элемент Н 57, эзСмен ,ИЛИ 41 ц с задержкаР 1, необходимой для принятия и счетчик 35 адреса следующей мцкрокаманды, подается на счетньп вход счетчика 35, увеличивая его содержимое ца единицу. Б пратцьном случае адрес следующей микракоманды це изменяется, Таким образом, осуществляется разветвление в лпкрапраграмме в загисцмости ат вьпОле ения каких-либо условий. Если в регистрах 11 и 12 находятся коды конца шажества, то по следуощей микрокоманде появляется импульс на выходе элемента И 56, который проходит на сигнальный выход 34,сезпдетельствуя об окончании выполнения операции объединения множеств Ли В. Этим же импульсам устройствопереводится в исходное состояние, ОВ противном случае выбираетсчлЕЕЕкр окалазда па катар ОЙ 105 Вхл етсяимпульс на Входе элемента И 52. Поэтому импульсу осуществляется разветвление в ляекропрограмме в завцси лзостн ат сцгал на выходе де 1 ПФра.Ор;1 13, Ес:ц в регеЕсзе 11 находится кад конца множества, та цеабхаццО 11 ре,1 Зть и 3 ходы усГзастзавсе оставшиеся элементы множества Б.20 Поэтому по следующей микрокомандеОввз 5 етс 5 ПлПульс на выходе 24 блока 18, ца которому очередной элементлПожестз Б из регистра 12 через от"крьтую группу 6 элементов И ц групп, 8 элементов ИЛИ проходит ца группу 31 выходов в качестве очередногоэлемепга мнажестзза С, Затеи выбирается третья мцкракомацда. Если в регистре 11 це находится код конца мно жесВата па следующей Яхкракал 5 андепаяеляется импульс на выходе элемена И 53, по которому анализируетсясгнал на выходе дешцФратора 14. 35 Еслв регистре 12 цс код конца111 Оекеста, то ца выходе дешц 11 ратара14 цулегай сигнал. В этом случае следующей выбирается микракоманда, пакотороц появляется имгульс ца зыходе 40 эле. ента И 54. При этом осуществляется раэвствлеПЕС в лПкрапрагралРле взавпснмастц ат сигнала на выходе 16схемы 15 сравнения. Если ца этом выходе едишчцый сигнал (т. е, очеред ной элемент множества Л меньше очереднага элемента множества Б), танеобходима передать очередной элемент множества А ца выход устройства.Дз 5 этага вьзбирается микрокоманда, 50 па каторац появляется импульс на выходе 23 блока 18. По этому импульсуоткрывается группа 5 элементов И иочередной элемент множества А цз регистра 11 проходит на группу 31 вы хада в каестве очередного элементалРОжества СЭГа жс мцкра";Оманд;1 Выпалняетея в случае, когда в регистра1 находится кад конца лПажестеза.ПО ДЗУМ СЛЕЦУЮГтЦМ МИКРОКОМаЦДам в регистр 11 цз блока 10 памяти принимается кад следуощега элемента множества Л а содержимое счетчика 1 узеличизаетсл на единицу. После этого зназь осу 5,)" стзтяетсл анализ сггнагаз ца зьхадах дешифратороз 14 и 13,Если ца выходе 16 схеа)1 15 сравпеция 1 улезай сигнал, то ныбирается микрокоманда. по которой появляется импульс ца выходе элемсцта И 55. Этим импульсом анализируется сигнал ца выходе 17 схемы 15 сравнения, Если ца этом ныходе присутствует едицпца (очередные элементы т 0)жестз Л и Е разит 1)то ца группу 31 Быхадаз Выдается ачерецнай элемент мпажестзэ. Л а затем осуществляется тере- ХОД К ЧТЕНИЮ СЛЕтУОШЦХ ЭЛЕМЕНТОВ множеств Л и В, Б противном случае ОСУЦЕСТЗГП 5 Е 7 СЛ ВЫЦата ОЧЕРСДЦОГа ЭЛЕМЕТГта 1 па)1(Е)С 1 З; Г.Формуа изабрстения Ус"грайстза для абъетттпеци 51 множеств сацержащее первый второй С 1) 1 11 А Пе 1)БытВ годанА11 ц четвертый блоки элементов И, первый и второй блоки элементов ИЛИ блок памттк гтет)вщ и Второй ре 111 с 1 ры первый ц Вторац тешиФраторт схему сравнения и блок упразлсцня, прцчем ВхОд эд 1)оса элемептаз церз 01 О м 10 жестза устрацстза саедицсц с иц 1)ор- МаттИОЦЦЫМ ВХОДОМ ПЕРВОГО С)1 ЕТ)иха, выходы первого и второго счетчиков соединены соответственна с первыми г)хОДлмц пе 1)БОГО и зта)ОГО блахОВ элементов И, выходы которых саедццегьы саатветствегна с первым и вторым входамц первого блаха элетенто) ИЛИ выход каторага сосдштец с адресным входом блока ттамлтц, вьгхад которого саецгп 1 ен с 1 П 11)0 мациагц 1 ым ВхоДОМ герзога регистра, выход которого саеццнеп с перзьгм входом схемы сравнения и первым входам третьего блока элементов И БыхОДы Т 1)стьеГО и четвертого блоков элементов И соединены СООТБ 1 СТ 13 СН 1 та С ПЕР 1)ЬП и ЗТ 01 ЫМ ВХО- даьгт второго бока элементов ИЛ 1 вы" ХОД КОТОРОГО ЛБЛЛЕТС 51 ИнфСРМаЦТИОННЫМ выходам устройства., установочный вход и вход запуска устройства соединены соответственна с гтерзым и вторым входами блока управления, первый ьыхОд катарОГО соединен с Выходам сигнала окончания работы устройства,второй, третий, четвертый пятый,шестой выходы блока управления соединены соответственна с вторым вхо дом первого блока элементов И, вторым входом Второго блока элементовИ, со счетным входам второго счетчика, с вторым Входам третьего блокаэлементов И и с вторым Входом четвертого блока элементов И, выходпервого дешифратора соединен с третьим входом блока управления, седьмой выход которого соединен со счет 1 гьм входом первого счетчика и входоматгиси первого регистра, о т л и -ч а ю щ е е с л тем, чта, с цельюповышения быстродействия, информациань 1 ый зхОд второго счетчика саедицен с Входом адреса элементов второго множества устройства, Выход первого регистра соединен с входом первого Деши 1)ратара выход блока памятисоединен с иц 4 ормациаццьгт входом зторого регистра, гыхад хаторога соединен с вторым входам схемы сравнения,с пергым входом четвертого блока эле"ментов И и входам второго дешнфратора, выход которого соединен с четвертым зхоцом блока управления, пятыйц шестой входы которого соединеныс ВыхОдОм Разно и зь 1 хацом Меньше(хемы сравнения соответственно, четвертый выход блока управления соеди"цец с входом записи второго регистра, З 5 причем блок управления содержит счетчик каманц, узел памяти команд, регистр, дешифратор команд, первуюгруппу из двенадцати элементов И,вторую и третью группы элементов И,первый, второй, третий элеиегты задержки, генератор импульсоз, терзыйвторой и третий элементы ИП 1 первыйВход первого элемента ИЛИ саедицен спервым входом блока управления, Вы 5 ход первого элемента ИЛИ соединен свходам останова генератора импульсов,второй вход блока управления соединен с входам запуска генератора, выход которого соединен с перзьми зхо- ) дами первой группы элементов И блокауправления, вторые входы первой группы элементов И блока управления соединены с выходами дешиФратора команд,причем выходы первого, второго, тре-Т" тьего, четвертого, пятого, шестогоэлементов И первой:.руппы блоха управления соединены :оотзетственно сзторьи седьмым третьим, четвертым,пятым и шестым выходамее блока управления, вьехады с седьмого.по одцннадцатыйл элементов И первой группы блока управления соединены с первымивходами элементов И второй группыблока управления, выход двенадцатогоэлемента И первой группы блока управления соединен с первым выходам блока управленияи вторым входом первого элемента ИЛИ, вторые входы первого и второго элементов И второй группы блока управления соединены с третьим входом блока управления, вторыевходы третьего, четвертого, пятогоэлементов И второй группы блока управления соединены саатяетствепца счетвертым, пятым и шестым входамиблока управлеееея, четвертый входблока управления соедиееен с третьимвходом первого элемента И второйгруппы бпака управления, выходы элементов И второй группы блока управлене;я соединенея с входами второгоэлемента ИЛИ, выход которого соединен с входом первого элемента задержки, вьехад которого соединен са счетным входом счетчика команд, установочный вход которого соединен с выходом зторога лемента задержки,вход которого соединен с выходомпервого элемента ИЛИ, вход третьегоэлемента задержки соединен с установочным входам регистра и выходом генератора импульсов, входы дешифрата ра команд соединены с группой вьтходод паля мцкракомацды узла памятикоманд, группа вьеходав поля местногоуправления которого присоединена иипФармациоееным входам регистра, вые 5 .ход которого соединен с первымп входами элементов И третьей группы блока управления, вторые входы элемен тов И которой соединены с выходомтретьего элемента задержки, выходы 20 элементов И третьей группы блока управления соединены с инормаццоееееымее входами счетчикакоманд , выход которого соединен с адресееым входом узлапамятп коееаеед.,Иванова Техред Л,Кранчук, Корректор С. Шекмар ак аказ 6841/ Тираж 671 ВНИИПИ Государственногопо делам изобретений и 113035,. Москва, Ж, РаушПодписное митета СССР открытий ская наб., д. 4/5