Устройство для определения пересечения множеств

 

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ, содержащее два регистра, группы элементов И, группу элементов ИЛИ, дешифратор и блок памяти, первый информационный выход которого соединен с входом дешифратора, отличающееся тем, что, с целью повьппения производительности устройства за счет обработки двух множеств элементов, в него введены два счетчика, элемент ИЛИ, триггер, узел сравнения и блок микропрограммного управления, причем первый адресный вход устройства соединен с информационным входом первого счетчика, выходы разрядов которого соединены с информационными входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ группы, выходы которых соединены с адресным входом блока памяти, второй информационньш выход которого соединен с первым информационным входом узла сравнения и с информационными входами элементов И второй группы, выходы которых соединены с информационным входом первого регистра, выходы разрядов которого соединены с вторым информационным входом узла сравнения и с информационными входами элементов И третьей группы, выходы которых соединены с информационным выходом устройства, второй адресный вход устройства соединен с информационным входом второго регистра, выходы разрядов которого соединены с информационными входами элементов И четвертой группы, выходы которых соединены с информационным входом второго счетчика, выходы разрядов которого соединены с информационными входами элементов И пятой группы, выходы которых соединены с вторыми входами элементов. ИЛИ группы, выход узла сравнения соединен с единичным вхоДом триггераJ .единичный (0 выход которого соединен с первыми С управляющими входами элементов И третьей группы, первый выход блока микропрограммного управления соединен с управляющими входами элементов И первой группы, второй выход соединен со счетным входом первого счетчика и с управляющими входами о элементов И второй группы, третий, Од 4 Од четвертый, пятый и шестой выходы блока микропрограммного управления соединены соответственно с управляютщими входами элементов И четвертой группы, пятой группы, узла сравнения и с вторыми управляющими входами элементов И третьей группы, седьмой выход соединен со счетным входом второго счетчика и.с первым входом элемента ИЛИ, выход которого соединен с нулевым входом триггера, нулевой выход которогб соединен с первым входом блока микропрограммного управления , восьмой выход которого сое

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

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

РЕСПУБЛИК

„„Я0„„1176346 А 51) 4 G Об F 15/38

)"

1;., .„-.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ " : ) „1

К ABTOPCMOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ,21) 3711901/24-24 (22) 16.03.84 (46) 30.08.85. Бюл. 9 32 (72) Б.С. Богумирский, В.Я. Яцук и С.В. Сычев (53) 681.325 (088.8) (56) Опубликованная заявка Великобритании,Ф 1448211, кл. G 06 F 15/38, 1976.

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

Ф 666545, кл. G 06 F 15/38, 1977. (54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ, содержащее два регистра, группы элементов И, группу элементов ИЛИ, дешифратор и блок памяти, первый информационный выход которого соединен с входом дешифратора, о т л и ч а ю щ е е с я тем, что, с целью повышения производительности устройства за счет обработки двух множеств элементов, в него введены два счетчика, элемент

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

И второй группы, выходы которых соединены с информационным входом первого регистра, выходы разрядов которого соединены с вторым информационным входом узла сравнения и с информационными входами элементов И третьей группы, выходы которых соединены с информационным выходом устройства, второй адресный вход устройства соединен с информационньм входом второго регистра, выходы разрядов которого соединены с информационныии входами элементов И четвертой группы, выходы которых соединены с информационным входом второго счетчика, выходы pasрядов которого соединены с информационными входами элементов И пятой группы, выходы которых соединены с вторыми входами элементов.ИЛИ группы выход узла сравнения соединен с еди- з ничным входом триггера, .единичный выход которого соединен с первыми управляющими входами элементов И третьей группы, первый выход блока микропрограммного управления соединен с управляющими входами элементов И первой группы, второй выход соединен со счетным входои первого счетчика и с управляющими входаии элементов И второй группы, третий, четвертый, пятый и шестой выходы блока микропрограммного управлений соединены соответственно с управляющими входами элементов И четвертой группы, пятой группы, узла сравнения и с вторыми управляющими входами. элементов И третьей группы, седьмой выход соединен со счетным входои второго счетчика и с первым входом элемента ИЛИ, выход которого соединен с нулевым входом триггера, нулевой выход которог6 соединен с первым входом блока микропрограммного управления, восьмой выход которого сое1!76346 динен с сигнализирующим выходом устройства и с;;вторым входом элемента

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

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

Цель изобретения — повышение 5 производительности устройства за счет обработки двух множеств элемен" тов, На фиг. 1 приведена схема устройства; на фиг. 2 - схема блока. микропрограммного управления, на фиг. Э— схема микропрограммы работы устройства.

Схема содержит регистры 1 и 2, группы 3-7 элементов И, группу 15 элементов ИЛИ, дешифратор 9, блок

l0 памяти, счетчики 11 и 12, элемент

ИЛИ 13, триггер 14, узел 15 сравнения, блок 16 микропрограммного управления, адресные входы 17 и 18 2О устройства, установочный вход 19 устройства, вход 20 запуска устройства, информационный выход 21 устройства, сигнализирующий выход

22 устройства, выходы 23 - 29 блока

16 и входы 30 и 31 блока 16„ узел

32 памяти, счетчик 33, группы 34

35 элементов И, дешифратор 36, генератор 37 импульсов, распредеитель 38 импульсов, элементы ЗО

39 и 40 задержки, регистр 41, элементы ИЛИ 42, 43; триггер 44 и эле" менты И 45-58.

В каждом блоке схемы микропро-, граммы работы устройства (фиг. 3) . 35 изображены выполняемые микрооперации, Элементы устройства отмечены их позициями на фиг. l и 2. Справа от черты в прямоугольном блоке отмечается выход блока 16, под дейст- 4О вием импульса на котором выполняется соответствующая микрооперация.

Позиции, заключенные в скобки, определяют выходы (содержимое рого соединен с установочншм входол, устройства и с третьим входом элемента ИЛИ,. вход запуска устройства соединен с четвертым входом блока микропрограммного управления. соответствующих элементов устройства. Стрелка обозначает пересылку информации, а знак вопроса — проверку условия, Пусть А и  — множества элементов. Тогда пересечение двух множеств является множеством С элементов, принадлежащих как множеству А, так и множеству B. Каждое множество хра-. нится в блоке 10 памяти, причем элементы множества представлены кодами чисел и находятся в последовательных ячейках. Последний элемент множества отмечается в блоке 10 специфическим содержимым дополнительных разрядов, выходы которых соединены с входами дешифратора 9.

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

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

При включении питания устройство устанавливается в исходное состояние импульсов с входа 19, по которому обнуляются триггеры 14 (через элемент ИЛИ 13) и 44 (через элемент

ИЛИ 42); распределитель 38 переводится в исходное состояние (ни на одном из его вьходов сигнал не появляется), а генератор 37 — в запертое состояние. В счетчике 11 по входу

17 записывается адрес первого элемента множества А, а в регистр 1 по входу 18 — адрес первого элемента множества В. Устройство готово к работе.

Запуск устройства в работу производится импульсом с входа 20. По этому импульсу в счетчике 33 форми" руется адрес первой микрокоманды микропрограммы работы устройства, з 1 записанной в узле 32 памяти. При этом из него выбирается первая микро команда на входы дешифратора 36, и кода адреса следующей микрокоманды.

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

Они распределяются распределителем

38 по управляющим точкам блока 16.

Первый импульс появляется на первом выходе распределителя 38 и проходит через. элемент И 45 (код микроопера-. ции первой микрокоманды должен приводить к появлению сигнала на первом выходе дешифратора 36). При этом содержимое счетчика 11 подается чере группы 3 элементов И и 8 элементов

ИЛИ в блок 10 памяти, из которого выбирается первый элемент множества

А. Кроме того, адрес следующей микро команды принимается в регистр 41.

Второй импульс с выхода распределителя 38 открывает группы 35 элементов H и адрес следующей микрокоманды приниМается в счетчик 33. В даль. нейшем выборка микрокоманд из узла

32 памяти и их расшифровка производится аналогично. Код второй микрооперации приводит к появлению импульса на входе 24 блока 16, в результате чего содержимое счетчика

l1 увеличивается на единицу (формируется адрес следующего элемента множества А), а первый элемент множества А с блока 10 памяти принимает ся в регистр 2 (так как открывается группа 4 элементов И). Кроме того этот же импульс подается на элемент И 55. Дешифратор 9 настроен.на содержимое дополнительных разрядов блока 10 памяти, соответствующее последнему элементу множества, Следовательно, если из блока 10 на предыдущем такте выбран последний элемент множества А, то появляется импульс на выходе элемента И 55, который устанавливает триггер 44 в единичное состояние. При выполнении следующей микрокоманды появляется импульс на выходе 25 блока

16 и содержимое регистра 1 переписы вается в счетчик 12. Далее появляется импульс на выходе 26 блока 16, который открывает группу 7 элементов И и содержимое счетчика 12 подается в блок 10 памяти. При этом

176346 4

55

50 из него выбирается первый элемент множетсва В. По импульсу на цыходе

27 блока 16 осуществляется.сравнение в узле 15 содержимого на выходе блока 10 памяти с содержимым регистра 2. При совпадении этих кодов появляется импульс на выходе узла 15 сравнения и триггер 14 устанавливается в единичное состояние, подготавливая к отрытию группу 5 элементов И. По импульсу с выхода

28 блока 16 осуществляется выдача первого элемента множества С из регистра 2 на 21, если триггер 14 находится в единичном состоянии.

Если же он в нулевом состоянии, то выдача не производится. При выполне. нии следующей микрокоманды появляется импульс на выходе элемента И 52.

Здесь микропрограммаразветвляется в зависимости от состояния триггера 14 °

Если триггер 14 находится в нулевом состоянии, то появляется импульс на выходе элемента И 57, который проходит через элемент ИЛИ 43 и с задержкой, необходимой для принятия в счетчик 33 адреса следующей . микрокоманды, подается на счетный вход счетчика 33, увеличивая его содержимое на единицу. При этом иэ блока 32 выбирается микрокоманда. в результате выполнения которой появляется импульс на выходе 29 блока 16, вследствйе чего содержимое счетчика 1-2 увеличивается на единицу (формируется адрес следующего элемента множества В), а триггер

14 устанавливается в нулевое состояние. Затем появляется импульс на выходе элемента И 53 и происходит анализ потенциала на выходе дешифратора

9. Если он нулевой, то элемент И

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

Если на выходе дешифратора 9 присутствует сигнал, то появляется импульс на выходе элемента И 58 и в счетчике 33 формируется адрес микрокоманды, в результате выполнения которой появляется импульс на выходе элемента И 54.

Если триггер 14 находится в единичном состоянии, то содержимое сче П1176346 ка 33 не изменяется, вследствие чего из узла )2 выбирается микрокоманда безусловного перехода к микрокоманде, по которой выдается импульс на выходе элемента И 54.

По импульсу с выхода элемента И

54 производится анализ состояния триггера 44. Если он находится в нулевом состоянии, то следующей выбирается микрокоманда безусловного пе- рехода к первой микрокоманде микропрограммы. Если же триггер 44 находится в единичном состоянии, то появляется импульс на выходе 22 уст:ройства, сигнализирующий об окончании работы устройства. Этим .же импульсом устройство переводится в исходное состояние.

После записи в счетчик ll и ре10 гистр 1 адресов первых элементов двух других множеств и подачи импульса на выход 20 устройство снова запускается в работу.

1 I 76346

1176346

Составитель А. Жеренов

Редактор И. Ковальчук Техред З.Палий Корректор Л. Бескид

Заказ 5363/49 Тираж 710 Подписное

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

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

Филиал ППП "Патент", r..Óìãoðîä, ул. Проектная, 4