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

 

Изобретение относится к вычислительной технике и может быть использовано в системах управления базами данных. Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат. С этой целью в устройстве , содержащем блок 1 памяти, счетчики 2,3, элемент ИЛИ 4, элементы И 5,6, группу 7 элементов И, регистры 8,9, схемы 10,11 сравнения, генератор 12 импульсов и распределитель 13 импульсов, изменены сбяаи, в результате чего реализован сокращенный алгоритм поиска информации, 1 ил. д ю (Л

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

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

РЕСПУБЛИН (51) 4 С 06 F 15/38

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4177892/24-24 (22) 09.01.87 (46) 23.09.88.Бюл. к 35 (72) Б.С,Богумирский и В.M.Öûãàíêoâ (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 780011, кл. С 06 F 15/38, 1978.

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

У 1267436, кл. G 06 F 15/38, 1985.

„„SU„„425717 А 1 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДОПОЛНЕНИЯ МНОЖЕСТВА (57) Изобретение относится к вычислительной технике и может быть исполь1 зовано в системах управления базами данных. Цель изобретения — повышение быстродействия и сокращение аппаратурных затрат. С этой целью в устройстве, содержащем блок 1 памяти, счетчики 2,3, элемент ИЛИ 4, элементы

И 5,6, группу 7 элементов И, регистры 8,9, схемы 10,11 сравнения, генератор 12 импульсов и распределитель

13 импульсов, изменены связи, в результате чего реализован с экращенный алгоритм поиска информации. 1 ил.

C) 1425717

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

Цель изобретения — повышение быстродействия и сокращение аппаратурных затрат.

На чертеже приведена схема устройства. 10

Устройство содержит блок 1 памяти, счетчики 2 и 3, элемент ИЛИ 4, зле;менты И 5 и 6, группу 7 элементов И, регистры 8 и 9, схемы 10 и 11 сравнения, генератор 12 импульсов, распределитель 13 импульсов, группу 14 адресных входов, группу 15 информационных входов, вход 16 запуска, груп пу 17 информационных выходов и выход 18 призйака окончания.

Пусть P — универсальное множест,во, А — множество, являющееся под множеством множества P. Тогда допол. ненеием множества А являетоя множест во В = А элементов из множества Р,не .принадлежащих множеству А. Множества, являющиеся подмножествами множества Р, хранятся в блоке 1 памяти,причем их элементы представлены кодами чисел. Элементы кажпого множества ,находятся в последовательных ячейках памяти. Последний элемент каждого

;.множества отмечается единицей в последнем разряде. Все остальные элементы отмечаются нулем. Элементы универсального множества закодированы целымичислами от 1 до N где N — число элементов в универсальном множестве.

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

При включении питания распределитель 13 импульсов устанавливается в исходное состояние (при этом ни на одном из его выходов сигнал не появ;ляется), генератор 12 импульсов уста--45 навливается в запертое состояние, счетчик 3 обнуляется, а последний разряд регистра информации блок 1 памяти устанавливается в единичное состояние (не показано). Потенциалом, „прошедшим через элемент ИЛИ 4, подготавливается к срабатыванию элемент

И S. По группе 15 входов в регистр 9 записывается код числа N-1, а по группе 14 входов в регистр 8 заносит55 ся адрес первого элемента множества А. Устройство готово к работе.

Работа устройства инициализируется импульсом по входу 16, в результате чего запускается генератор 12 Распределитель 13 осуществляет рассылку импульсов с выхода генератора 12 по управляющим точкам устройства.

Импульс с первого выхода распределителя 13 проходит через элемент И 5, открывая информационные входы счетчика 2. Поэтому из регистра 8 в него заносится адрес первого элемента множества А. Кроме того, этот импульс поступает на счетный вход счетчика 3, формируя в нем код числа 1 (код первого элемента множества P).

По импульсу на втором выходе распределителя 13 иэ блока 1 памяти осуществляется считывание кода первого элемента множества А. Он сохраняется на регистре информации блока 1 и выдается на его выходе. Предположим, что множество А содержит несколько элементов. Поэтому сигнал на выходе последнего разряда блока 1 памяти отсутствует. Предположим также, что совпадение содержимого счетчика 3 и. регистра информации блока 1 не произошло. При этом выпадает сигнал на правом выходе схемы 11 сравнения и отсутствует сигнал на его левом выходе.

По импульсу с третьего выхода распределителя 13 содержимое счетчика 2 увеличивается на единицу, т.е. в нем формируется адрес второго элемента множества А.

Затем снова появляется импульс на первом выходе распределителя 13, однако никаких действий по нему не происходит. По импульсу с второго выхода распределителя 13 из блока 1 памяти считывается код второго элемента множества А, который сравнивается с кодом первого элемента множества P., Импульсом с третьего выхода распре делителя 13 в счетчике 2 формируется адрес третьего элемента множества А.

Устройство работает аналогично до тех пор, пока не возникнет одна из следующих ситуаций.

Код очередного элемента множества А, считанный из блока 1 памяти, совпадает с кодом первого элемента множества Р„ В. этом случае появляется сигнал на левом выходе схемы 11 сравнения, в результате чего подготавливается к срабатыванию элемент И 5.

При этом по импульсу на первом выходе распределителя 13 в счетчик 2 принимается адрес первого элемента

14257 множества А, а в счетчике 3 формируется код второго элемента множества P. Выдача компаратором 11 сигнала совпадения означает, что первый элемент множества P принадлежит множеству А, а поэтому нет необходимости в его дальнейшем просмотре..

Необходимо пропустить первый элемент множества P и перейти к проверке при-10 надлежности второго элемента множества P множеству А.

Из блока 1 памяти прочитаны коды всех элементов множества А, но совпадения схемой 11 сравнения не выявлены. При этом одновременно присутствуют сигналы на правом выходе схемы 11 сравнения и на выходе последнего разряда блока 1 памяти. Это означает, что первый элемент множест-20 ва P не принадлежит множеству А, а следовательно, его код необходимо выдать из устройства в качестве кода первого элемента множества В.

Поэтому подготавливаются к срабатыва-25 нию элементы И 5 и 6. По импульсу с третьего выхода распределителя 13 через элемент И б открывается группа 7 элементов И и содержимое счетчика 3 проходит на группу 17 выходов.

По импульсу на первом выходе распределителя 13 в счетчик 2 записывается адрес первого элемента множества А, а в счетчике 3 формируется код второго элемента множества P.

Проверка на принадлежность множе35 ству А второго и последующих элементов множества P и выдача на группу 17 выходов элементов множества В осуществляется аналогично описанному.

Наступает такой момент, когда по импульсу на первом выходе распределителя 13 в счетчике 3 сформирован код числа N+1. При этом появляется сигнал íà вде схемы 10 сравнения, 45 который проходит на выход 18 устройства, сигнализируя об окончании работы, и устанавливает устройство в исходное состояние, т.е. останавливает генератор импульсов, обнуляет

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

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

Устройство для определения дополнения множества, содержащее блок памя17

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