Устройство для определения дополнения множества Советский патент 1988 года по МПК G06F17/27 

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

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

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

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

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

При включении питания распределитель 13 импульсов устанавливается в исходное состояние (при этом ни на одном из его выходов сигнал не появ- ;ляется), генератор 12 импульсов устанавливается в запертое состояние, счетчик 3 обнуляется, а последний разряд регистра информации блок 1 памяти устанавливается в единичное состояние (не показано). Потенциалом, прчэшедшим через элемент ИЛИ 4, подготавливается к срабатьгоанию элемент И 5. По группе 15 входов в регистр 9 записывается код числа N-1 , а по группе 14 входов в регистр 8 заносится адрес первого элемента множества А. Устройство готово к работе.

Работа устройства инициализируется импульсом по входу.16, в результа

5

0

5

0

5

0

5

0

5

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

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

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

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

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

14

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

Нз блока 1 памяти прочитаны коды всех элементов множества А, но сов падения схемой 11 сравнения не вы- явлены. При этом одновременно присутствуют сигналы на правом выходе схемы 11 сравнения и на выходе последнего разряда блока 1 памяти. Это означает, что первый элемент множества Р не принадлежит множеству А, а следовательно, его код необходимо выдать из устройства в качестве кода первого элемента множества В. Поэтому подготавливаются к срабатьтанию элементы И 5 и 6. По импульсу с третьего выхода распределителя 13 через элемент И 6 открывается группа 7 элементов И и содержимое счетчика 3 проходит на группу 17 вьпсодов. По импульсу на первом выходе распределителя 13 в счетчик 2 записывается адрес первого элемента множества А, а в счетчике 3 формируется код второго элемента множества Р.

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

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

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

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

, o

о 5 Q

.«

с

5

5

17

ти, два счетчика, элемент ИЛИ, два элемента И, группу элементов И, два регистра, две схемы сравненияj генератор импульсов и распределитель импульсов, причем группа адресных выходов устройства соединена с входами первого регистра, выходы которого соединены с информационными входами первого счетчика, ВЬЕХОДЫ которого соединены с адресными входами блока памяти, выходы которого кроме последнего разряда, соединены с первой группой входов первой схемы сравнения, вторая группа входов которой соединена с ин- формационйыми входами группы элемен- - тов И, с выходами второго счетчика и о первой группой входов второй схемы сравнения, вторая группа входов которой соединена с выходами второго регистра, входы которого являются группой информационных входов устройства, вход запуска которого соединен с входом запуска генератора импуль-т сов, выход которого соединен с управляющим входом распределителя импульсов, первый вход которого соединен с первым входом первого элемента И, вы- . ход которого соединен с выходом признака окончания работы устройства, с выходом второй схемы сравнения, с установочными входами блока памяти,распределителя импульсов и входом останова генератора импульсов, выход пО Гшеднего разряда блока памяти соединен с первым входом элемента ИЛИ,выход которого соединен с вторым входом первого элемента И, выходы групп элементов И являются группой выходов устройства, второй и третий выходы распределителя импульсов соединены с управляющим входом блока памяти и со счетным входом первого счетчика соответственно, отличающееся тем, что, с целью повышения быстродействия и сокращения аппаратурных затрат, выход первого элемента И . соединен с управляющим входом первого счетчика, третий выход распределителя импульсов соединен с первым входом второго элемента И, второй вход которого соединен с выходом последнего разряда блока памяти, второй вход элемента ИЛИ соединен с первым выходом первой схемы сравнения, второй выход которого соединен с третьим входом второго элемента И, выход которого соединен с управляющим входом группы элементов И.

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