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

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

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

Описание изобретения к патенту

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

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

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

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

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

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

Блок 1 (2) анализа элементов (фиг. 3) содержит коммутатор 33, регистр 34, узел 35 памяти, схему 36 сравнения, сумматор 37, первый и второй элементы ИЛИ 38 и 39, элемент 40 задержки и элемент И 41.

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

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

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

В исходном состоянии все последовательные элементы находятся в нулевом состоянии (триггеры 8, 29 и 29). На выходах 16 и 17 имеются нулевые потенциалы. Генератор 30 не вырабатывает импульсы. Содержимое счетчика 4 нулевое, регистра 3 произвольное, ненулевое. Содержимое регистров 34 блоков 1 и 2 произвольное, но различное. Уровни сигналов с выходов схем сравнения, элементов И и ИЛИ нулевые. Коммутатор 33 при нулевом сигнале на управляющем входе соединяет свои выходы с выходами сумматора 37. Соответствующие цепи начальной установки не показаны на фигурах.

При подготовке к работе на входе 12 устанавливается и записывается в регистр 3 число К + 1, а на входах 13 и 14 устанавливаются коды соответственно начального и конечного адресов требуемого подмножества А.

Запуск устройства осуществляется подачей короткого импульса на вход 15, далее работа устройства протекает в соответствии с временными диаграммами фиг. 4.

Импульс запуска поступает на элемент 26 задержки через элемент ИЛИ 24. Элемент 26 задержки имеет три выхода, сигналы на которых появляются последовательно. Импульс с первого выхода элемента 26 задержки проходит через элемент ИЛИ 25 и подтверждает (при запуске) нулевое состояние триггера 28 и триггера 29. Импульс с второго выхода 19 инкрементирует содержимое счетчика 4 (при запуске до "1"). Этот же импульс поступает в блоки 1 и 2 анализа на элементы ИЛИ 38 и осуществляет следующие операции: переключает коммутатор 33 в состояние, когда на его выходы коммутируются коды с входов 13 и 14 соответственно, проходя через элементы 40 и ИЛИ 39 (задержка выбирается достаточной для того, чтобы на входах регистра 34 установились потенциалы с выходов коммутатора 33), формирует импульс на вход синхронизации регистра 34, записывая в него код с выходов коммутатора 33 (это соответственно начальный и конечный адреса подмножества). По этим адресам анализа записаны в ячейках "О", что на выходе элемента И 41 не вызывает в начальный момент формирования сигнала, так как содержимое счетчика - нулевое.

Сигнал с третьего выхода элемента 26 (выход 18) устанавливает в единичное состояние триггеры 8 и 28. Разрешается работа генератора 30. Открывается элемент И 32. Первый тактовый импульс через элемент И 32 и с задержкой, определяемой элементом 27, переключает по счетному входу триггер 29 в единичное состояние. С выхода 17 тактовый импульс поступает на вход элемента И 41 блока 1, на выходе которого импульс не формируется из-за неравенства кодов на входах схемы 36. Этот же импульс с выхода 17 поступает на третий вход блока 2, где через элемент ИЛИ 39 осуществляет запись в регистр 34 адреса с выхода коммутатора 33, на котором (при отсутствии сигнала с элемента ИЛИ 38, что имеет место в данный момент) модифицированный код конечного адреса, сумматор 37 модифицирует адрес, декрементируя (для блока 2) или инкрементируя (для блока 1) содержимое регистра 34. Таким образом, в первом такте в регистр блока 2 записывается адрес последнего среди значащих элементов подмножества А. Значение соответствующего элемента формируется на выходах узла 35 памяти блока 2 и сравнивается на схеме 36 с содержимым счетчика 4 (первым элементом множества Р), если эти коды совпадают, на выходе "Равно" схемы 36 блока 2 формируется единичный сигнал.

Второй тактовый импульс проходит через открытый элемент И 31 и переключает триггер 29 вновь в нулевое состояние, поступает на четвертый вход блока 2 и третий вход блока 1. В этом такте в блоке 1 проводятся те же операции, что на первом такте в блоке 2 (но с инкрементированием адреса в сумматоре). Если, например, сигналы на входах схемы 36 в данном случае равны, то на ее выходе формируется сигнал (что означает, что данный элемент подмножества Р входит в состав множества А) и этот сигнал через элемент ИЛИ 10 сбрасывает в нулевое состояние триггер 8. Таким образом процесс повторяется попеременно для блоков 1 и 2.

В некоторый момент времени (опрос блоков 1 и 2 идет навстречу друг другу) после очередного такта работы содержимое регистров 34 обоих блоков совпадает. При этом срабатывает схема 6 сравнения и сигнал с ее выхода (означающий окончание анализа первого элемента множества Р) поступает на группу 9 элементов И. Если данный элемент множества Р содержится среди элементов подмножества А, то триггер 8 находится в нулевом состоянии и на выходах группы 9 сигналы не формируются. Если же данного элемента множества Р нет среди элементов подмножества А, то триггер 8 находится в единичном состоянии, код элемента поступает через группу 9 на выход устройства (этот элемент по определении содержится в дополнении множества А - множестве В). Сигнал со схемы 6 через элемент ИЛИ 24 поступает в элемент 26, и повторяется процесс работы устройства для следующего элемента множества Р. При этом содержимое счетчика 4 равно "2" (формируется второй элемент множества Р). Для устройства безразлично, в каком состоянии находятся к моменту начала второго этапа блоки 1 и 2, а также триггер 29 - на время формирования импульсов с выходов элемента 26 процесс анализа приостанавливается, а затем продолжается сначала для нового элемента множества Р.

Для каждого элемента множества Р устройство работает аналогично.

По окончании К-го такта перебора элементов множества Р счетчик 4 переходит в состояние К + 1, срабатывает схема 5 сравнения. Сигнал с выхода схемы 5 проходит через элемент 11 задержки (для завершения переходных процессов, вызванных схемой 6 по окончании очередного этапа работы) и устанавливает устройство в исходное состояние: обнуляет счетчик 4, записывает в регистры блоков 1 и 2 начальный и конечный адреса элементов множества А, обнуляет триггеры 28 и 29. После этого устройство готово к новому циклу работы.

Таким образом, устройство позволяет произвести определение дополнения множества приблизительно за К х М тактов работы генератора 30, что обеспечивает его высокое быстродействие, так как прототипу требуется на ту же процедуру время, вчетверо большее.