SU1494015A1 - Device for exhaustive search of combinations - Google Patents

Abstract

The invention relates to automation and computing and can be used to simulate the control modes of functioning multiprocessor systems with distributed memory, as well as to solve combinatorial problems. The purpose of the invention is to expand the functionality of the device by selecting combinations with a given attribute. The device contains the ring shift registers 1, the shift register 4, the counter 5, the register of the sign 7, the comparison circuit 6, the trigger 10, the elements AND 11, OR 3, OR-NOT 8, delay 9, the drivers 2 pulses. The introduction of the trigger, the elements OR, OR NOT, the register of the feature and the pulse formers allows the generation of a signal indicating that the generated combination corresponds to the desired feature. 1 il.

Description

The invention relates to automation and computing and can be used to simulate the control modes of a multiprocessor system (MPS) with shared memory, as well as in solving combinatorial problems.

The purpose of the invention is to expand the functionality of the device by selecting combinations with a given attribute.

The drawing shows a functional diagram of the proposed device.

The device contains n annular shift registers 1, n pulse formers 2 on the trailing edge, n elements OR 3, shift register 4, counter 5, comparison circuit 6, feature register 7, HS-NE 8 element 8 delay element 9, trigger 10, AND element 11, the input 12 of the initial installation of the device, the input 13 of the feature of the selected combinations, the clock inputs 1A and 15, the output 16 of the end of enumeration, the information outputs 7, -17, and the output 18 of the reliability of the output information of the device.

The device works as follows

At the input 12 of the initial installation of the device, a pulse signal is applied, which in all ring registers 1 sets the binary code 10 ,,, 10. At input 13, the sign code m is sent and written to register 7 to select the combinations. The first pulse is fed to the input 14 of the first series of pulses, which zeroes the counter 5 and enters the synchronous input of the ring register 1, as a result of which the code in the ring register 1 is shifted to the right by one bit and becomes 010o, ooo. the transfer from the last bit of the ring-register 1 does not occur, as a result of which the shaper 2 does not start on the trailing edge. The software code “О”, which is recorded in register 4, is shifted by the signal from the output of delay element 9 “With a delay equal to the maximum transition process time by shifting codes in ring registers 1, the first impulse from input 14 is through the delay element 9 arrives at the single input of the trigger 10 and sets it to the single state. A single signal from the output of the trigger 10 is fed to the input element And 1I and allows the supply from the input 15 of the device of the second series of pulses to the synchronous input of the register 4 shift. Upon the arrival of the next pulse signal, the contents of the shift register 4 are shifted by one bit to the right and from the last digit goes to the counting input of the counter 5, which counts the number of units AND in register 4, the pulses of the second series pass through the element 11 until all register bits 4 will not be equal to zero. In this case, a single signal from the output of the element OR-NOT 8, the input of which receives the contents of all bits of register 4, is fed to the zero input of the trigger 10 and converts it to the zero state. The zero signal from the output of the trigger 10 is fed to the input of the element 11 and blocks the second pulse of the second series at the register 4 clock. 7, In case of equality of the codes from the output of the comparison circuit 6, a single signal is output to output 18 of the reliability of the output information of the device. A single signal at output 18 means that the information outputs of the device 17 contain binary codes corresponding to the code specified in register 7.

Upon arrival of the next pulse from input 14, the code B shifts the ring register 1 by one bit to the right and the cycle repeats. When shifting to the right in the i-th ring register of the binary code O. ,, 01, by resetting a single signal from the last bit of the ring register, the i-th shaper of 2 pulses is triggered on the falling edge, which supplies a pulse signal to the synchronous input (i-bl) -ro (, l, nl) of the ring register 1 and shifts the contents of the last in this case the code in the i-th ring register 1 becomes equal to 10 ... O. A complete enumeration of all n combinations ends with the output of a single signal from the output of the n-th shaper 2 pulses on the falling edge, which arrives at the output 16 of the device. In this case, at the output of all ring registers I, a code 10 ... 0 is set. Thus, the proposed device selects from all n combinations such that the number of like bits is equal to a given number m. When the device selects all n 1 permutations from the n combinations.

Claims (1)

Claim device A brute force device comprising n circular n-bit shift registers (n is the number of combinations), a n-th double shift register, a counter, a comparison circuit, an AND element, the setting inputs of all the ring shift registers being connected to the setting input of the device , which is characterized by the fact that, in order to expand the functionality of the device by selecting matches with a given attribute, it contains a register of the characteristic, a trigger, a delay element, n ILK elements, an OR-NOT element, and n impulse drivers ca, wherein the delay element input is a clock input of the first device and is connected to the counter input of the installation and to the synchronization input of the first circular shift register serial output i-ro (, n) of the ring shift register 0 five five 0 five connected to the input of the i-ro pulse generator, the output of the j-th j "I, p-1) pulse generator connected to the clock input of the (j + l) -th ring shift register, i.e. the bit outputs of all ring shift registers are connected to inputs i -ro element OR, the output of the i-ro element OR is connected to the i-th bit input of the shift register, the serial output of the shift register is connected to the counting input of the counter, the bit outputs of the shift register are connected to the inputs of the element OR NOT, the output of the element OR NOT connected to sync input circuit compared and to the zero input of the trigger, the output of the delay element is connected to the control input of the shift register and to the single input of the trigger, the output of the trigger is connected to the first input of the And element, the second input of which is the second clock input of the device, the output of the And element is connected to the clock input the shift register, the input of the register of the sign is the input of the sign of the device, the output of the register of the sign and the output of the counter are connected respectively to the first and second information inputs of the comparison circuit, the output of the comparison circuit Is the output of the reliability of the result of the device, the bit outputs of all ring shift registers are the information outputs of the device, the output of the nth pulse generator is the output of the end of operation of the device.