RU2022353C1 - Device for determining complement of a set - Google Patents
Device for determining complement of a set Download PDFInfo
- Publication number
- RU2022353C1 RU2022353C1 SU904858939A SU4858939A RU2022353C1 RU 2022353 C1 RU2022353 C1 RU 2022353C1 SU 904858939 A SU904858939 A SU 904858939A SU 4858939 A SU4858939 A SU 4858939A RU 2022353 C1 RU2022353 C1 RU 2022353C1
- Authority
- RU
- Russia
- Prior art keywords
- input
- output
- inputs
- unit
- register
- Prior art date
Links
Images
Landscapes
- Complex Calculations (AREA)
Abstract
Description
Изобретение относится к вычислительной технике и может быть использовано в системах управления банками данных. The invention relates to computer technology and can be used in database management systems.
Целью изобретения является повышение быстродействия устройства. The aim of the invention is to improve the performance of the device.
Цель достигается тем, что в устройство для определения дополнения множества, содержащее регистр, вход которого является информационным входом устройства, первую схему сравнения, первый и второй входы которой соединены соответственно с выходами регистра и счетчика, счетный вход которого соединен с первым выходом блока управления, а выход - с первым входом первого блока анализа элементов и с первыми входами элементов И группы, вторые входы и выходы которых соединены соответственно с выходом триггера и с информационным выходом устройства, причем единичный вход триггера соединен с вторым выходом блока управления, первый адресный вход устройства соединен с вторым входом первого блока анализа элементов, вход пуска устройства соединен с первым входом блока управления, третий и четвертый выходы которого соединен соответственно с третьим и четвертым входами первого блока анализа элементов, введены второй блок анализа элементов, элемент ИЛИ, вторая схема сравнения и элемент задержки, при этом выход счетчика соединен с первым входом второго блока анализа элементов, второй, третий и четвертый входы которого соединены соответственно с вторым адресным входом устройства, третьим и четвертым выходами блока управления, второй вход которого соединен с пятыми входами первого, второго блоков анализа элементов, установочным входом счетчика, выходом конца работы устройства и выходом элемента задержки, вход которого соединен с выходом первой схемы сравнения, выход второй схемы сравнения соединен с третьим входом блока управления и с третьими входами элементов И группы, нулевой вход триггера соединен с выходом элемента ИЛИ, первый и второй входы которого соединены соответственно с первыми выходами первого и второго блоков анализа элементов, вторые входы и шестые выходы которых соединены соответственно с первым и вторым входами второй схемы сравнения и с первым выходом блока управления, причем первый (второй) блок анализа элементов содержит коммутатор, узел памяти, два элемента ИЛИ, элемент задержки, сумматор, схему сравнения, регистр и элемент И, выход которого является первым выходом блока анализа элементов, первый, второй, пятый и шестой входы которого являются соответственно первым входом схемы сравнения, первым информационным входом коммутатора и первым, вторым входами первого элемента ИЛИ, выход которого соединен с управляющим входом коммутатора, а через элемент задержки с первым входом второго элемента ИЛИ, второй вход и выход которого соединены соответственно с третьим (четвертым) входом анализа элементов и управляющим входом регистра, информационный вход которого соединен с выходом коммутатора, второй информационный вход которого соединен с выходом сумматора, первый вход которого соединен с входом "единица" ("минус единица") устройства, а второй - с выходом регистра, с вторым выходом блока анализа элементов и с адресным входом узла памяти, выход которого соединен с вторым входом схемы сравнения, выход которой соединен с первым входом элемента И, второй вход которого соединен с четвертым (третьим) входом блока анализа элементов. The goal is achieved by the fact that in the device for determining the complement of the set containing the register, the input of which is the information input of the device, the first comparison circuit, the first and second inputs of which are connected respectively to the outputs of the register and counter, the counting input of which is connected to the first output of the control unit, and output - with the first input of the first block analysis of elements and with the first inputs of elements AND groups, the second inputs and outputs of which are connected respectively to the output of the trigger and the information output of the device, moreover, the single input of the trigger is connected to the second output of the control unit, the first address input of the device is connected to the second input of the first block of element analysis, the input of the start of the device is connected to the first input of the control unit, the third and fourth outputs of which are connected respectively to the third and fourth inputs of the first block of element analysis , the second element analysis unit, the OR element, the second comparison circuit and the delay element are introduced, while the output of the counter is connected to the first input of the second element analysis unit, the second, third the second and fourth inputs of which are connected respectively to the second address input of the device, the third and fourth outputs of the control unit, the second input of which is connected to the fifth inputs of the first, second blocks of element analysis, the installation input of the counter, the output of the end of the device and the output of the delay element, the input of which is connected with the output of the first comparison circuit, the output of the second comparison circuit is connected to the third input of the control unit and to the third inputs of the AND elements of the group, the zero input of the trigger is connected to the output of the element LI, the first and second inputs of which are connected respectively to the first outputs of the first and second units of analysis of elements, the second inputs and sixth outputs of which are connected respectively to the first and second inputs of the second comparison circuit and the first output of the control unit, the first (second) unit of analysis of elements contains a switch, a memory node, two OR elements, a delay element, an adder, a comparison circuit, a register and an AND element, the output of which is the first output of the element analysis unit, the first, second, fifth and sixth inputs of which are respectively the first input of the comparison circuit, the first information input of the switch and the first, second inputs of the first OR element, the output of which is connected to the control input of the switch, and through the delay element with the first input of the second OR element, the second input and output of which are connected respectively to the third (fourth ) the input of element analysis and the control input of the register, the information input of which is connected to the output of the switch, the second information input of which is connected to the output of the adder, the first input of which It is connected to the unit input (minus one) of the device, and the second to the register output, to the second output of the element analysis unit and to the address input of the memory node, the output of which is connected to the second input of the comparison circuit, the output of which is connected to the first input element And, the second input of which is connected to the fourth (third) input of the block analysis of elements.
На фиг. 1 приведена структурная схема устройства для определения дополнения множества; на фиг. 2 - структурная схема блока управления; на фиг. 3 - структурная схема первого (второго) блока анализа; на фиг. 4 - временные диаграммы работы устройства. In FIG. 1 is a block diagram of a device for determining complement of a plurality; in FIG. 2 is a block diagram of a control unit; in FIG. 3 is a structural diagram of a first (second) analysis unit; in FIG. 4 - time diagrams of the operation of the device.
Устройство для определения дополнения множества (фиг. 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. The device for determining the complement of the set (Fig. 1) contains the first and
Блок 7 управления (фиг. 2) содержит первый и второй элементы ИЛИ 24 и 25, первый и второй элементы 26 и 27 задержки, первый и второй триггеры 28 и 29, генератор 30 тактовых импульсов, первый и второй элементы И 31 и 32. The control unit 7 (Fig. 2) contains the first and
Блок 1 (2) анализа элементов (фиг. 3) содержит коммутатор 33, регистр 34, узел 35 памяти, схему 36 сравнения, сумматор 37, первый и второй элементы ИЛИ 38 и 39, элемент 40 задержки и элемент И 41. Block 1 (2) analysis of elements (Fig. 3) contains a
Устройство работает следующим образом. The device operates as follows.
Пусть Р - универсальное множество, а А - множество, являющееся подмножеством Р. Тогда дополнением множества А является множество В =
, также являющееся подмножеством множества Р и содержащее элементы, не принадлежащие множеству А. Различные (возможно всевозможные) подмножества множества Р хранятся в идентичной форме в узлах 35 памяти блоков 1 и 2 анализа элементов. Элементы каждого подмножества находятся в смежных ячейках памяти узлов 35. Элементы множества Р закодированы числами от 1 до К в двоичной форме (К - число элементов универсального множества Р). Во всех случаях один и тот же элемент представлен одинаковым кодом.Let P be a universal set, and A a set that is a subset of P. Then the complement of A is the set B = , which is also a subset of the set P and contains elements that do not belong to the set A. Various (possibly all kinds) subsets of the set P are stored in identical form in the
Таким образом, в узлах 35 памяти каждое подмножество А имеет начальный и конечный адреса. По начальному адресу записывается число "О" (не являющееся элементом универсального множества Р). Thus, in
В исходном состоянии все последовательные элементы находятся в нулевом состоянии (триггеры 8, 29 и 29). На выходах 16 и 17 имеются нулевые потенциалы. Генератор 30 не вырабатывает импульсы. Содержимое счетчика 4 нулевое, регистра 3 произвольное, ненулевое. Содержимое регистров 34 блоков 1 и 2 произвольное, но различное. Уровни сигналов с выходов схем сравнения, элементов И и ИЛИ нулевые. Коммутатор 33 при нулевом сигнале на управляющем входе соединяет свои выходы с выходами сумматора 37. Соответствующие цепи начальной установки не показаны на фигурах. In the initial state, all consecutive elements are in the zero state (
При подготовке к работе на входе 12 устанавливается и записывается в регистр 3 число К + 1, а на входах 13 и 14 устанавливаются коды соответственно начального и конечного адресов требуемого подмножества А. In preparation for work at input 12, the number K + 1 is set and recorded in
Запуск устройства осуществляется подачей короткого импульса на вход 15, далее работа устройства протекает в соответствии с временными диаграммами фиг. 4. The device is started by applying a short pulse to input 15, then the operation of the device proceeds in accordance with the time diagrams of FIG. 4.
Импульс запуска поступает на элемент 26 задержки через элемент ИЛИ 24. Элемент 26 задержки имеет три выхода, сигналы на которых появляются последовательно. Импульс с первого выхода элемента 26 задержки проходит через элемент ИЛИ 25 и подтверждает (при запуске) нулевое состояние триггера 28 и триггера 29. Импульс с второго выхода 19 инкрементирует содержимое счетчика 4 (при запуске до "1"). Этот же импульс поступает в блоки 1 и 2 анализа на элементы ИЛИ 38 и осуществляет следующие операции: переключает коммутатор 33 в состояние, когда на его выходы коммутируются коды с входов 13 и 14 соответственно, проходя через элементы 40 и ИЛИ 39 (задержка выбирается достаточной для того, чтобы на входах регистра 34 установились потенциалы с выходов коммутатора 33), формирует импульс на вход синхронизации регистра 34, записывая в него код с выходов коммутатора 33 (это соответственно начальный и конечный адреса подмножества). По этим адресам анализа записаны в ячейках "О", что на выходе элемента И 41 не вызывает в начальный момент формирования сигнала, так как содержимое счетчика - нулевое. The trigger pulse is supplied to the
Сигнал с третьего выхода элемента 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 формируется единичный сигнал. The signal from the third output of element 26 (output 18) sets the
Второй тактовый импульс проходит через открытый элемент И 31 и переключает триггер 29 вновь в нулевое состояние, поступает на четвертый вход блока 2 и третий вход блока 1. В этом такте в блоке 1 проводятся те же операции, что на первом такте в блоке 2 (но с инкрементированием адреса в сумматоре). Если, например, сигналы на входах схемы 36 в данном случае равны, то на ее выходе формируется сигнал (что означает, что данный элемент подмножества Р входит в состав множества А) и этот сигнал через элемент ИЛИ 10 сбрасывает в нулевое состояние триггер 8. Таким образом процесс повторяется попеременно для блоков 1 и 2. The second clock pulse passes through the open element And 31 and switches the
В некоторый момент времени (опрос блоков 1 и 2 идет навстречу друг другу) после очередного такта работы содержимое регистров 34 обоих блоков совпадает. При этом срабатывает схема 6 сравнения и сигнал с ее выхода (означающий окончание анализа первого элемента множества Р) поступает на группу 9 элементов И. Если данный элемент множества Р содержится среди элементов подмножества А, то триггер 8 находится в нулевом состоянии и на выходах группы 9 сигналы не формируются. Если же данного элемента множества Р нет среди элементов подмножества А, то триггер 8 находится в единичном состоянии, код элемента поступает через группу 9 на выход устройства (этот элемент по определении содержится в дополнении множества А - множестве В). Сигнал со схемы 6 через элемент ИЛИ 24 поступает в элемент 26, и повторяется процесс работы устройства для следующего элемента множества Р. При этом содержимое счетчика 4 равно "2" (формируется второй элемент множества Р). Для устройства безразлично, в каком состоянии находятся к моменту начала второго этапа блоки 1 и 2, а также триггер 29 - на время формирования импульсов с выходов элемента 26 процесс анализа приостанавливается, а затем продолжается сначала для нового элемента множества Р. At some point in time (
Для каждого элемента множества Р устройство работает аналогично. For each element of the set P, the device works similarly.
По окончании К-го такта перебора элементов множества Р счетчик 4 переходит в состояние К + 1, срабатывает схема 5 сравнения. Сигнал с выхода схемы 5 проходит через элемент 11 задержки (для завершения переходных процессов, вызванных схемой 6 по окончании очередного этапа работы) и устанавливает устройство в исходное состояние: обнуляет счетчик 4, записывает в регистры блоков 1 и 2 начальный и конечный адреса элементов множества А, обнуляет триггеры 28 и 29. После этого устройство готово к новому циклу работы. At the end of the Kth cycle of enumerating the elements of the set P, the
Таким образом, устройство позволяет произвести определение дополнения множества приблизительно за К х М тактов работы генератора 30, что обеспечивает его высокое быстродействие, так как прототипу требуется на ту же процедуру время, вчетверо большее. Thus, the device allows determining the complement of the set for approximately K x M clock cycles of the
Claims (1)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
SU904858939A RU2022353C1 (en) | 1990-08-10 | 1990-08-10 | Device for determining complement of a set |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
SU904858939A RU2022353C1 (en) | 1990-08-10 | 1990-08-10 | Device for determining complement of a set |
Publications (1)
Publication Number | Publication Date |
---|---|
RU2022353C1 true RU2022353C1 (en) | 1994-10-30 |
Family
ID=21531964
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
SU904858939A RU2022353C1 (en) | 1990-08-10 | 1990-08-10 | Device for determining complement of a set |
Country Status (1)
Country | Link |
---|---|
RU (1) | RU2022353C1 (en) |
-
1990
- 1990-08-10 RU SU904858939A patent/RU2022353C1/en active
Non-Patent Citations (2)
Title |
---|
Авторское свидетельство СССР N 1176346, кл. G 06F 15/38, 1984. * |
Авторское свидетельство СССР N 1267436, кл. G 06F 15/38, 1985. * |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
RU2022353C1 (en) | Device for determining complement of a set | |
SU1753475A1 (en) | Apparatus for checking digital devices | |
RU1835543C (en) | Appliance for sorting of numbers | |
SU840887A1 (en) | Extremum number determining device | |
SU1529293A1 (en) | Device for shaping test sequence | |
SU1185325A1 (en) | Device for searching given number | |
SU1256010A1 (en) | Processor for implementing operations with elements of fuzzy sets | |
SU1168965A1 (en) | Device for tracing nodes of network area | |
RU2042187C1 (en) | Device for generation of uniform distribution of random integers | |
RU1789993C (en) | Device for editing table elements | |
JP2667702B2 (en) | Pointer reset method | |
SU1444744A1 (en) | Programmable device for computing logical functions | |
SU1536365A1 (en) | Information input device | |
SU1453401A1 (en) | Random number generator | |
SU494745A1 (en) | Device for the synthesis of multi-cycle scheme | |
JPS6043592B2 (en) | Large capacity static shift register | |
SU1488833A1 (en) | Address generator for walsh transformation | |
SU763965A1 (en) | Buffer memory | |
SU1290423A1 (en) | Buffer storage | |
RU1795471C (en) | Fast transform processor | |
SU1405058A1 (en) | Test code generator | |
SU1411738A1 (en) | Digital function converter | |
SU1437974A1 (en) | Generator of pseudorandom sequences | |
SU551702A1 (en) | Buffer storage device | |
SU1283858A1 (en) | Device for checking memory blocks |