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

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

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

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

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

Недостатком известного устройства также являются узкие функциональные возможности так как оно не позволяет изменять состав множеств в процессе работы

Цель изобретения - расширение функциональных возможностей за счет изменения анализируемых множеств в процессе работы

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

N

СЛ О

тов множества первой группы устройства подключены соответственно к входам первой группы первого узла сравнения, выход которого подключен к выходу признака завершения поиска дополнения множества и к входу установки в О первого счетчика, выходы которого подключены соответственно к входам второй группы первого узла сравнения, соответственно к входам первой группы второго узла сравнения и соответственно к первым входам элементов И первой группы, выходы которых подключены соответственно к выходам дополнения множества устройства, выход второго узла сравнения подключен к входу установки в О первого триггера, выход которого подключен к вторым входам элементов И первой группы, входы адреса подмножества устройства подключены соответственно к информационным входам второго счетчика, выходы которого подключены соответственно к первым входам элементов И второй группы, выходы которых подключены соответственно к адресным входам блока памяти, выходы которого подключены соответственно к входам второй группы второго узла сравнения, первый и второй выходы распределителя импульсов подключены соответственно к первым входам первого и второго элементов И, выход второго элемента И подключен к входам установки в О второго счетчика и второго триггера, выход которого подключен к первому входу первого элемента ИЛИ, выход которого подключен к вторым входам первого и второго элементов И, третий выход распределителя импульсов подключен к вторым входам элементов И второй группы, четвертый выход распределителя импульсов подключен к счетному входу второго счетчика и третьим входам элементов И первой группы, выход генератора тактовых импульсов подключен к первому входу режима распределителя импульсов, введены коммутатор, с третьего по пятый узлы сравнения, с третьего по пятый триггеры, элементы ИЛИ с ВТОРОГО по шестой, элементы И с третьего по девятый и третий счетчик, при этом выход первого узла сравнения подключен к первому входу второго элемента ИЛИ, выход которого подключен к входу считывания блока памяти, к второму входу режима распределителя импульсов, к входу останова генератора импульсов и к входу установки в О третьего триггера, инверсный выход которого подключен к первому входу третьего элемента И, выход которого подключен к первому входу третьего элемента И, выход которого подключен к первому входу третьего элемента ИЛИ и к входу установки в 1 четвертого триггера, инверсный выход которого подключен к первому входу четвертого элемента И, к первому входу пятого элемента И и к первому входу шестого элемента И, выход которого подключен к четвертым входам элементов И первой группы, прямой выход четвертого триггера подключен к первому входу седьмого элемента И, выход которого подключен к второму входу второго элемен0 та ИЛИ, к входу записи блока памяти, к выходу признака завершения записи элементов множеств устройства, к первому входу четвертого элемента ИЛИ и к входу установки в О четвертого триггера, выходы

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

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

0 элемента И к второму входу четвертого элемента И, выход которого подключен к входу установки в 1 третьего триггера и к второму входу третьего элемента ИЛИ, выход которого подключен к входу установки в 1

5 второго триггера и к входу запуска генератора тактовых импульсов, выход первого элемента И подключен к второму входу пятого элемента И, выход которого подключен к счетному входу первого счетчика и к входу

0 установки в 1 первого триггера, выход второго элемента И и четвертый выход распределителя импульсов подключены соответственно к первому и второму входам шестого элемента ИЛИ, выход которого

5 подключен к счетному входу третьего счетчика, выходы которого подключены соответственно к входам первой группы пятого узла сравнения, выход которого подключен к второму входу четвертого элемента ИЛИ, к вто0 рому входу шестого элемента И. к второму входу первого элемента ИЛИ и к третьему входу третьего элемента ИЛИ, входы постоянных значений устройства подключены соответственно к входам второй группы

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

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

Устройство для определения дополнения множества содержит блок 1 памяти, с первого по третий счетчики 2-4, коммутатор 5, распределитель б импульсов, генератор 7 тактовых импульсов, первую и вторую группы 8 и 9 элементов И. узлы 10-14 сравнения соответственно с первого по пятый, триггеры 15-19 соответственно с первого по пятый, элементы ИЛИ 20-25 соответственно с первого по шестой, элементы И 26-34 соответственно с первого по девятый. Входы 35 элементов множества первой группы соединены с первой группой информационных входов узла 10 сравнения. Устройство содержит также входы 36 адреса подмножества, вход 37 режима определения дополнения множества, входы 38-40 - соответственно с первого по третий входы режи- ма коррекции множества, входы 41 элементов множества второй группы, выход 42 признака завершения поиска дополнения множества, выходы 43 дополнения мно жества, входы 44 постоянных значений, входы 45 нулевого кода, выход 46 признака завершения записи элементов множеств устройства 46 и вход 47 нулевого потенциала.

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

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

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

от 1 до К, где К - число элементов множества Р. Так как подмножества А изменяются динамически (по числу и составу элементов), то для каждого подмножества А в блоке 1 памяти зарезервировано до К ячеек памяти.

0 Во всех множествах один и тот же элемент представлен одним и тем же числом.

Устройство имеет два основн ых режима работы: режим определения дополнения некоторого множества и режим коррекции

5 подмножества, причем последний режим имеет два подрежима: добавление нового элемента в множество и исключение из множества заданного элемента.

Режимы работы устройства не совме0 щаются во времени.

При включении питания распределитель 6 импульсов устанавливается в исходное состояние - отсутствуют положительные потенциалы на всех его выходах. Гене5 ратор 7 заперт (не формирует импульсов). Регистр информации блока памяти и счетчик 2 обнуляются. Все триггеры устройства а также счетчики 3 и 4 устанавливаются в нулевое состояние (цепи начальной уста0 новки на чертежах не показаны).

При подготовке к работе на входах 35 постоянно присутствует двоичный код числа К+1, а на входах 36 - начальный адрес требуемого подмножества А. После этого уст5 ройство готово к работе.

В режиме определения дополнения множества сигнал запуска режима определения дополнения множества поступает на вход 37 устройства и через открытый эле0 мент И 29 устанавливает в единичное состояние триггер 17, а также через элемент ИЛИ 22 устанавливает в единичное состояние триггер 16. Нулевым сигналом с триггера 17 запрещается поступление на устройство че5 рез элемент И 28 сигнала запуска режима коррекции множеств, сигналом с элемента ИЛИ 22 запускается генератор 7 и распределитель 6 начинает работу. С прямого выхода триггера 16 через элемент ИЛИ 20

0 открываются элементы И 26 и 27. Импульсом с первого выхода распределителя 6 через элементы И 26 и 30 триггер 15 устанавливается в единичное состояние, а содержимое счетчика 2 инкрементируется

5 (т.е. устанавливается код первого, а в дальнейшем очередного элемента множества Р). На выходе блока 1 памяти - нулевой код. следовательно, узел 11 сравнения сигнала не выдает. По импульсу с второго выхода распределителя 6 через элемент 27 триггер

16 возвращается в исходное (нулевое) состояние, а в счетчик 3 записывается значение первого адреса подмножества А. Этим же сигналом через элемент ИЛИ 25 инкре- ментируется счетчик 4, подсчитывающий количество элементов множества А (которое для любого множества А равно, например, К). (Если в множестве А число элементов меньше, чем в множестве Р, то пустые ячейки блока памяти содержат нулевой код).

Импульсом с третьего выхода распределителя 6 адрес первого (в дальнейшем очередного) элемента множества А через группу элементов И 9 поступает на адресные входы блока 1 памяти, и на его выходах формируется код первого элемента множества А. Если код этого (или любого другого) элемента множества А совпадает с кодом первого (очередного) элемента множества Р, узел 11 сравнения формирует сигнал, по которому триггер 15 обнуляется. По импульсу с четвертого выхода распределителя 6 содержимое счетчиков 3 и 4 инкрементиру- ется (т.е. формируется адрес следующего элемента множества А). При этом группа элементов И 8 не открывается, так как отсутствует сигнал с выходов блоков 31 и 14 (не закончено сравнение всех элементов множества А с первым или очередным элементом множества Р).

Затем снова появляется импульс на первом выходе распределителя 6, но так как элемент И 26 закрыт, никаких действий не производится, как и по сигналу с второго выхода распределителя, вследствие того, что элемент И 27 также закрыт. По сигналу с третьего выхода распределителя из блока 1 памяти считывается код следующего элемента множества А, сравниваясь с первым элементом множества Р, а по сигналу с четвертого выхода распределителя содержимое счетчиков 3 и 4 вновь инкременти- руется. Таким образом, из блока 1 памяти считываются последовательно все элементы множества А, которые сравниваются с первым (очередным) элементом множества Р.

После,считывания из блока 1 последнего (К-го) элемента множества А (среди которых могут быть и нулевые коды - отсутствие элементов, что не оказывает влияния на работу устройства, так как среди элементов множества Р нет нулевого, следовательно узел 11 не срабатывает на пустые ячейки) четвертым выходом распределителя счетчик 4 переводится в состояние К+1. На вхо- дах44 постоянно поддерживается код числа К+1, следовательно, в этот момент времени срабатывает узел 14 сравнения, на элемент И 31 поступает разрешающий сигнал и производится анализ первого этапа сравнения. Если хотя бы один элемент множества А совпал с первым (очередным) элементом множества Р, триггер 15 оказывается в нулевом состоянии и группа 8 элементов 1/1 8 не открывается. Если совпадения не было, триггер 15 оказывается в единичном состоянии и разрешает срабатывание группы 8 элементов И. Таким образом, при совпаде0 нии трех управляющих сигналов на входах элементов И группы 8 на выход 43 выдается элемент дополнения множества А, т.е. множества В.

Сигнал с выхода узла 14 сравнения по5 ступает на входы элементов 23 и 20, а также на установочный вход триггера 16 через элемент ИЛИ 22. По сигналу с элемента 23 счетчик 4 сбрасывается в нулевое состояние. По сигналам с блоков 20 и 16 срабаты0 вают в соответствующий момент времени элементы И 26 и 27, по сигналу с элемента И 26 счетчик 2 формирует код следующего элемента множества Р, а триггер 15 устанавливается в исходное (единичное) состояние.

5 По сигналу с элемента И 27 триггер 16 возвращается в нулевое состояние, а содержимое счетчика 4 инкрементируется По сигналу с второго выхода распределителя также в счетчик 3 снова записывается адрес

0 первого элемента множества А. В дальнейшем устройство работает аналогично описанному до тех пор, пока по очередному выходному импульсу с первого выхода распределителя 6 содержимое счетчика 2 не

5 совпадает с кодом на входе 35 (числом К+1). При совпадении этих чисел (при окончании анализа всех элементов множества Р) срабатывает узел 10 сравнения, по сигналу с которого устройство устанавливается в ис0 ходное состояние: распределитель переводится в нулевое состояние, запирается генератор 7. счетчик 2 и регистр информации блока 1 памяти обнуляются, триггер 17 также обнуляется. Сигнал на выходе 42 сиг5 нализирует получателю об окончании формирования множества В. Устройство готово к работе.

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

В режиме добавления элемента устройство работает следующим образом. По входам 36 подается адрес первого элемента модифицируемого множества А, на входы 41 подается код добавляемого элемента, на вход 39 подается сигнал, определяющий режим добавления элемента, переводящий триггер 19 в нулевое состояние. После этого устройство готово к работе в режиме добавления элемента (подрежиме режима коррекции множества).

Коррекция (в данном случае добавление элемента) начинается после подачи на вход 38 устройства импульса запуска режима коррекции, который устанавливает триггер

18через элемент И 28 (в случае отсутствия работы устройства в режиме определения дополнения множества этот элемент открыт) в единичное состояние. Сигнал с инверсного выхода триггера 18 запрещает поступление в устройство в процессе коррекции сигнала запуска режима определения дополнения множества по входу 37, а также снимает разрешающий потенциал с элементов И 30 и 31, отключая совокупность блоков, в которых нет необходимости в данном режиме работы устройства (режим коррекции). С прямого выхода триггера 18 снимается разрешающий сигнал на элемент и 32.

Аналогично предыдущему режиму через элемент или 22 устанавливается в единичное состояние триггер 16. начинают работать генератор 7 и распределитель 6. Нулевой сигнал с прямого выхода триггера

19переключает коммутатор 5 в состояние-, при котором на его выходы коммутируются выходы 41 устройства. Этот же сигнал запрещает работу элемента И 34: сигнал с инверсного выхода триггера 19 открывает элемент И 33.

Сигнал с первого выхода распределителя в данном режиме не используется. Сигналы с второго выхода распределителя наращивают содержимое счетчика 4, что в данном режиме также не имеет значения. Рабочими являются третий и четвертый такты распределителя. По второму выходу распределителя в счетчик 3 заносится адрес первого элемента модифицируемого множества А. По сигналу с третьего выхода распределителя 6 блок 1 памяти формирует на выходах код первого элемента модифицируемого множества А. На входы 45 постоянно подается нулевой код, таким образом, узел 12 сравнения срабатывает при обнаружении пустой ячейки. Если ячейка не пуста,

сигнал с четвертого выхода распределителя 6 инкрементирует счетчик 3 и в дальнейшем формируется код очередного элемента корректируемого множества. Если узел 12 срабатывает, сигнал с его выхода через элементы 33, 24 и 32 выводится на вход записи блока 1 памяти, где по заданному адресу записывается код элемента с входов 41. Импульсом записи устанавливается в ис0 ходное состояние генератор 7, распределитель 6, через элемент ИЛИ 21 обнуляется регистр информации блока .1 памяти, через элемент 23 устанавливается в нулевое состояние счетчик 4, сбрасывается триггер 18

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

В режиме исключения элемента из множества работа устройства аналогична опи0 санной для предыдущего режима (добавления элемента), однако предварительно, триггер 19 устанавливается в единичное состояние, переключая выходы коммутатора на входы 47 (на которых посто5 янно присутствует нулевой код), открывается элемент И 34 и закрывается элемент И 33. т.е. вместо узла 12 задействован узел 13 сравнения. Аналогично производится перебор адресов ячеек корректируемого множе0 ства. При обнаружении по некоторому адресу заданного входами 41 элемента срабатывает узел 13 сравнения, через элементы И 34, ИЛИ 24 и И 32 в соответствующую ячейку блока 1 памяти записывается нуле5 вой код (элемент удаляется). Сигналом записи устройство аналогично описанному переводится в исходное состояние.

Таким образом, устройство позволяет наряду с определением дополнения множе0 ства производить коррекцию множеств в процессе работы, т.е. динамически изменять состав множеств.

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

5 выход которого подключен к выходу признака завершения поиска дополнения множества устройства и к входу установки в О первого счетчика, выходы которого подключены соответственно к входам второй группы первого узла сравнения, соответственно

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

0 группы третьего узла сравнения и соответственно к входам первой группы четвертого узла сравнения, выходы третьего и четвертого узлов сравнения подключены соответственно к первым входам восьмого и

5 девятого элементов И выходы которых подключены соответственно к первому и второму входам пятого элемента ИЛИ, выход которого подключен к второму входу седьмого элемента И, первый вход режима кор0 рекции множества устройства и вход режима определения дополнения множества устройства подключены соответственно к второму входу третьего элемента И и к второму входу четвертого элемента И, вы5 ход которого подключен к входу установки в 1 третьего триггера и к второму входу третьего элемента ИЛИ, выход которого подключен к входу установки в 1 второго rpnirepa и к входу запуска генератора так0 товых импульсов, выход первого элемента И подключен к второму входу пятого элемента И, выход которого подключен к счетному входу первого счетчика и к входу установки в 1 первого триггера, выход второго эле5 мента И и четвертый выход распределителя импульсов подключены соответственно к первому и второму входам шестого элемента ИЛИ, выход которого подключен к счетному входу третьего счетчика, выходы

0 которого подключены соответственно к входам первой группы пятого узла сравнения, выход которого подключен к второму входу четвертого элемента ИЛИ, к второму входу шестого элемента И, к второму входу лерво5 го элемента ИЛИ и к третьему входу третьего элемента ИЛИ, входы постоянных значений устройства подключены соответственно к входам второй группы пятого узла сравнения, выход четвертого элемента ИЛИ

0 подключен к входу установки в О третьего счетчика, вход нулевого потенциала устройства подключен к информационному входу коммутатора, выходы которого подключены соответственно к информационным входам

5 блока памяти, второй и третий входы режима коррекции множества устройства подключены .соответственно к входам установки в О и в 1 пятого триггера, прямой выход которого подключен к управляющему входу коммутатора и к второму входу

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

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