Устройство для определения разности множеств Советский патент 1993 года по МПК G06F15/38 

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

Цель изобретения - расширение области применения за обработки множеств с произвольным расположением элементов.

На фиг. 1 приведена структурная схема устройства для определения разности множеств; на фиг. 2 - структурная схема блока синхронизации.

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

Блок синхронизации (фиг. 2) содержит элемент 25 ИЛИ, первый и второй элементы 26 и 27 И, распределитель 28, триггер 29 и генератор 30 тактовых импульсов.

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

00 4

множества в устройстве помечается единицей в старшем разряде памяти (на фиг. 1 помечен пунктиром); остальные элементы в данном разряде содержат нули. Элементы множеств закодированы числами (в двоичной форме) от 1 до К, где К - мощность множества Р.

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

При включении питания распределитель 28 блока 8 устанавливается в исходное состояние: на всех его выходах - нули. Генератор 30 закрыт; счетчики 3 и 4 обнулены (соответствующие цепи не показаны на фиг. 1,2).

Подготовка устройства к работе осуществляется подачей на входы 13 начального адреса уменьшаемого множества А, а на входы 14 - начального адреса вычитаемого множества В, После этого устройство готово к работе.

Запуск работы устройства осуществляется подачей импульса на вход 15 пуска устройства, который устанавливает в еди- ничное состояние триггер 29 и запускает генератор 30. Распределитель 28 начинает циклически формировать импульсы на своих выходах (последовательно, с первого по четвертый 19-22). Устанавливаясь в единичное состояние, триггер 29 открывает через элемент ИЛИ 25 элементы И 26 и 27, а также переписывает с входов 13 код в счетчик 4. По сигналу с выхода первого распределителя 28 формируется сигнал на выходе элемента И 26, который инкрементирует содержимое счетчика 4 (таким образом, для более корректной работы устройства и обслуживания им полного уменьшаемого множества следует на входах 13 устанавливать код адреса на единицу меньше начального). Сигналом с второго выхода распределителя 28 формируется сигнал на выходе элемента И 27, устанавливающий в единичное состояние триггер 10 и записывающий в счетчик 3 код с входов 14; триггер 29 возвращается в исходное состояние; открываются элементы группы И 7 и начальный адрес уменьшаемого множества (А) поступает на адресные входы блока памяти 2. Сигналом с выхода 21 блока 8 открывается группа 5 элементов И и выдает на адресные входы блока памяти 1 начальный адрес вычитаемого множества (В). Первые элементы множеств А и В поступают на входы схемы сравнения 9. При их совпадении на вход сброса триггера 10 поступает сигнал, устанавливающий его в нуль. В противном случае ничего не происходит.

Сигналом с выхода 22 блока 8 счетчик 3 инкрементируется. Далее процесс продолжается аналогично, за исключением того, что элементы И 26 и 27 закрыты в следующих циклах. На схеме сравнения 9 последо- вательно сравниваются элементы

множества В с первым элементом множества А. При совпадения любого элемента множества В с элементом множества А триггер 10 устанавливается в нуль.

После достижения последнего элемента

0 множества В с последнего разряда блока памяти 1 формируется сигнал, подготавливающий к срабатыванию элементы И 26 и 27; формируется разрешающий сигнал на блок 6, который, если триггер 10 не сбро5 шен в нуль, в момент формирования сигна: ла на выходе 22 блока 8 выдает первый элемент множества А на выход 16 устройства, что означает, что первый элемент множества А не содержится в множестве

0 В. В противном случае элемент на выход 16 не выдается.

Затем, с началом нового цикла распределителя сигналом с выхода 19 блока 8 содержимое счетчика 4 инкрементируется, и

5 далее процесс перебора всех элементов множества В повторяется для следующего элемента множества А.

Когда перебор элементов множества А достигает его последнего элемента, в по0 следнем разряде блока 2 формируется сигнал, подготавливающий к срабатыванию элемент 11. После перебора для последнего элемента множества А всех элементов множества В сигналом с выхода последнего раз

5 ряда блока 1 через элемент задержки 12 формируется сигнал на выходе элемента 11, который подается пользователю, сигнализируя об окончании операции определения разности множеств; обнуляет регистры ин0 формации блоков памяти 1 и 2; устанавливаете исходное состояние распределитель 28 и генератор 30. Операция закончена.

Следует отметить, что после каждого цикла работы сигналом с элемента И 26

5 триггер 10 устанавливается в единичное состояние.

Таким образом, в результате работы устройства на выходе 16 формируется последовательность элементов множества А, не

0 входящих в множество В, т.е. разность А - В. При подаче на вход уменьшаемого множества начального адреса универсального множества на выходе возможно формирование дополнения для некоторого выбранного

5 подмножества В. Следовательно, данное устройство реализует операцию разности множеств и, как дополнение, операцию получения дополнения заданного множества до универсального (последняя операция реализуется прототипом).

Формула изобретения Устройство для определения разности множеств, содержащее блок синхронизации, первый вход которого соединен с входом пуска устройства, первый счетчик, информационный вход которого соединен с входом начального адреса первого множества устройства, а выход - с первыми входами элементов И первой группы, выходы которых соединены с адресными входами первого блока памяти, выходы разрядов которого, кроме последнего, соединены с первым входом схемы сравнения, выход которой соединен с нулевым входом триггера, выход которого соединен с первыми вхо- дами элементов И второй группы, вторые входы которых соединены с выходом последнего разрядов первого блока памяти и с вторым входом блока синхронизации, первый, второй, третий и четвертый выходы ко- торого соединены соответственно со счетным входом второго счетчика, с входом записи первого счетчика, с вторыми входами элементов И первой группы, со счетным входом первого счетчика, выходы элемен- тов И второй группы являются информационным выходом устройства, четвертый выход блока синхронизации соединен с

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

8

Y9 Л20

w

22

.2

Изобретение относится к вычислительной технике и может быть использовано в системах управления банками данных. Целью изобретения является расширение области применения устройства за счет обработки множеств с произвольным расположением элементов/Устройство содержит два блока памяти, два счетчика, схему сравнения, три группы элементов И, триггер, элемент И, элемент задержки и блок синхронизации. 2 ил.

Г

f5

Фиг. 2.

g