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

 

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

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

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

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

На фиг. 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, что обеспечивает его высокое быстродействие, так как прототипу требуется на ту же процедуру время, вчетверо большее.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4