SU1686464A1 - Device for information searching - Google Patents

Description

one

(21) 4763772/24 (22) 28 11.89 (16) 10.23.91. Bul MeZE

(71) Kiev Polytechnic Institute named after 50th Anniversary of the Great Oct. of Brno Socialist Revolution

(72) E. Bardis (CP), V.I. Korneychuk,

A.P. Markovsky and Yu.N. Chubatyuk (SU) (53) 681.3 (088.8)

(54) DEVICE FOR SEARCHING INFORMATION

(57) The invention relates to computing and can be used to implement access to information as per its

address and content. The aim of the invention is to increase speed. The device contains a group of 1 1-1.M memory blocks, a group of elements NEGATIVE 3.1 Z.M, a register 4 polling features, a group of elements OR 5.1-5.M, a register 6, an encoder 7, elements AND 9, 11, elements NOT 10 , 29, elements OR 12. 31. shaper 13 pulses, counters 15, 28 addresses, frequency divider 18, delay element 19, group of shift registers 21.1-21.К. switch group 23.1-23.M, OR-NOT element 27. comparison circuit 36, The goal is achieved by introducing new elements and links. 2 Il.

, 221

gggpt

Ig

4-1

at

ON 00 O О O

Ј

The invention relates to computing and can be used to implement access to information both by address and content.

The aim of the invention is to increase speed.

FIG. 1 shows a functional diagram of the device; in fig. 2 - time diagrams of the device in search mode.

The device contains a group of blocks 1.1-1.M memory, information output 2 of the device, a group of elements 3.1-Z.M UNEQUAL DETAIL, a register 4 of the indication of the survey, a group of elements OR 5.1-5.M, the register 6, the encoder 7, the output 8 minor bits device address addresses, AND 9 element, NOT 10 element, AND 11 element, OR 12 element, 13 pulse generator, pulse generator output 14, address counter 15, device information detection sign output 16, frequency divider 18 output 17, delay element 19, input 20 clock pulses of the device, a group of shift registers 21.1-21.K, gr the upv inputs 22.1-22.L of the initial state of the device, the switch group 23.1-23.M addresses, the input 24 lower bits of the device address, the input 25 specifies the operation mode of the device, the input 26 start the device, the element OR NOT 27, the counter 28 addresses , NOT element 29, device information input 30, OR element 31, device memory access initiation input 32, device read / write input 33, device input 34 and output 35 of the higher device address bits, comparison circuit 36, required search feature input 37 devices, end 38 output indication, input 39 Omer device search area, M - bit data dnost, L log2M.

The device works as follows.

The information M-bit words are written in the same cells of the 1.1-1.M blocks, one word in each block 1.

In the address reading (write) mode, the lower-order L bits of the address (L log2M) are fed to the input 24 of the device, and the higher-order bits of the address are fed to the input 34. In this case, a single signal is fed to the input 25 of the device. Under the action of this signal, at the outputs of all switches 23, codes identical to the code at input 24 are formed, which arrive at the lower bits of the address inputs of all blocks 1. At the same time, the signal from input 25 passes through the OR-NOT element 27 in the inverse representation initiates reception of a code from the inputs 34

The counter 28, from the outputs of which the code of the higher bits of the address goes to the higher bits of the address inputs of all blocks 1. At the same time, a single signal is sent to the input 32, which passes through the OR element 31. It initiates the operation of blocks 1.

When reading on the zero signal supplied to the input 33. in blocks 1, an M-bit read operation is performed.

0 information word on output 2 of the device.

When recording on a single signal supplied to input 33, in blocks 1, a write operation is performed at the address

5 M-bit information word supplied to the input 30 of the device.

In the information search mode, the M-digit code of the polling feature is input to input 37, the input code 34 is supplied

0 Z zones in the memory from which the search is performed (it is assumed that the entire memory volume is divided into M words in each), the code of the zone number to which the search is performed is inputted to input 39, the zero signal goes to input 33 , to the input 20 - a series of clock pulses, to the input 26 - a start signal in the search mode. The behavior of the device in the search mode is illustrated by the timing charts in FIG. 2

0 The clock signal sequence input to input 20 (FIG. 2), which are delayed by delay element 19, is input to frequency divider 18. At the output of the latter, 5 s internal synchronization pulses are formed, the frequency of which is half the frequency of the pulses at the input 20 and the front of which is shifted relative to the pulses at the input 20 (Fig. 2).

0 The start signal passes through the OR-NOT 27 element. It initiates entering the code from input 34 to counter 28, from the bit outputs of which the above code of zone number Z goes to the address inputs (senior bits) of all blocks 1. In addition , the start control signal, having passed through the OR 12 element, is fed to the input of the imaging unit 13, which forms a start signal at the sopm output 14 (FIG. 2), which.

0 enters the control input of the counter 15, sets all its bits to zero, coming through the element NOT 29 to the input of the register 6, sets all its bits to zero, arriving at the control inputs of all the shift registers 21, initiates reception of a code on registers 21c of the corresponding inputs 22. In this case, register 01.101 .. 01. is entered into register 21.1 into register 21.2 - code 00110011 ... 0011, into register 21.3 - code 0000111 h ... 00001111, etc. Accordingly with

the outputs of the first (senior) bits of the registers 21 to the input of the switch 23.1 remove the code 00 ... O, from the outputs of the second bits of the registers 21 to the input of the switch 23.2 remove the code 00 ... 01, from the outputs of the K-x bits (K - -1, M) of the registers 21 to the input of the switch 23. To remove the code K-1. The said codes from the inputs of the switches 23 under the action of the zero signal at the input 25 are switched to their outputs and further to the lower bits of the address inputs of the corresponding memory blocks 1. Accordingly, in the first memory block 1.1, the Z cell is addressed, in the second memory block 1.2 - (2H) - the cell, in the Kth block 1.K of the memory - (Z + K-1) -a cell. Accordingly, from the output of each kth block 1.K of the memory, the Kth bit of the (Z + K-1) -ro word is read. The reading is performed upon arrival at the input 20 of an external clock pulse, which, through the OR element 31, is fed to the control inputs of the sample of all the memory blocks 1.

On the Kth element of the ZKK UNEQUALITY parameter, the Kth bit of the () -ro word is compared with the Km bit of the polling sign. If these bits do not match, a single signal is generated at the output of the Z.K UNEQUALITY element, which through the OR5K element arrives at the installation input of the Kth bit of the bis register by the arrival of a clock pulse from input 20 (FIG. 2). register b is set to one, thereby (Z + K-1) -e word is excluded from the further search process. The code reception operation is performed on register b in the presence of an internal clock pulse from output 17 of the divider 18. With the next clock signal arriving at input 20 (in the absence of an internal clock pulse at output 17 and, therefore, at the control input of register 6) a cyclic shift to the left (towards the higher bits) of the contents of the register 6. With the arrival of a positive pulse front from output 17, one is added to the contents of the address counter 15 and the cyclic shift is The contents of all the registers 21. From the bits of the bits of the same name of the registers 21 to the inputs of the switches 23.1-23.M, codes 1, 2, 3 М, 0 are issued, which

commute to the lower bits of the address inputs of the corresponding blocks of 1.1-1 .M memory. From the output of each K-th block 1. To the memory, the k-th bit of the (g + (K) toM) word is read, which is compared to the K-th bit of the polling sign by the item Z. K of UNABILITY. Single signal

the non-coincidence of the output of element 3K UNEMNATABILITY through the element OR 5 K of the group with the arrival of a positive front of the external clock pulse establishes 5 units and a register 6, thereby excluding (Zt (K) mndM) -e word from the process of further comparison .

Then again with the arrival of a clock signal at input 20, a cyclic shift of register b is performed. With the arrival of the signal at the output 17, the contents of the registers 21 are cyclically shifted, the content of the counter 15 is increased by one unit, and the described comparison cycle is repeated.

In the general case, on the lth search cycle (.M}) comparing with the bit outputs of registers 21 to the inputs of the switches 23.1-23.M, codes are issued

0 respectively equal to (l + M-1) modM. which commute to the lower bits of the address inputs of the corresponding 1.1-1.M memory blocks. From the output of each Kth block 1.K of memory, the Kth bit is read (Zt

5 K-2 + l) mod M) -th word, which is compared with the K-th bit of the polling feature from register 4 on the Z.K UNEMATICAL DIAGRAM element, while the mismatch signal, passing through the OR 5.K element, is set to This is the K-th bit of register b, thereby excluding (Z fk -2tl) modM) -e word from the process of further comparison, since regardless of the coincidence of the excluded word in the remaining digits with the sign of the poll, one in 5 times the de register b corresponding to (Z + (k - -2 + l) modM) -My word, is rewritten from the output of the corresponding register bit 6 through the element OR 5. To and each write operation in register 6.

0If all words in the zone with addresses from Z-ro

until p + M-1) on the lth comparison cycle will be excluded (i.e., all bits of register 6 will be set to one), then a single signal is generated at the output

5 of the element 9 and this signal initiates the transition to the new zone: the signal increases by one the contents of the counter 28, providing a transition to the (Z + 1) -u zone, passing through the element OR 12, goes to

0, the input of the trigger generator 13, which sets all bits of the register 6 and the counter 15 to zero. The bits of the registers 21 are reset (by receiving the code c

5 inputs 22).

If during M comparison cycles not all words in the zone are excluded (i.e. one of the bits of register 6 is set to zero), then zero in register 6 marks the position in the zone of the word that coincides with the indication of polling by all M

discharges At the output of And 9, there is a zero signal, which, inverting by the element NOT 10, opens for passing the overflow signal from the counter 15 an element 11, from which output to the output 16 of the device, a signal of information detection is output. The high-order bits of the address of the search word are read from the outputs 35 of the device, and the low bits from the outputs 8.

If the search word is not in the memory, then the signal appearing at exit 38, when the code on counter 28 is equal to the search code supplied to inputs 39, records search procedures.

Claims (1)

Invention Formula A device for searching information containing a group of memory blocks, a group of address switches, the first address counter, a register, a poll sign register, an encoder, the first OR element, the first AND element, the information input of the poll sign register connected to the input of the required device search sign, information the inputs of the memory blocks of the group are connected to the information input of the device, the group of lower-order bits of the address input of the K-th memory block is connected to the output of the K-th switch of the address K 1 ... M, where M is the data size, high The bits of the address input of each memory block are connected to the output of the first address counter, the information input of which is connected to the input of the higher bits of the device address, the output of the information detection feature is connected to the output of the first element I. speed, a group of shift registers, a second address counter, a group of OR elements are entered into it. the second element is OR, the second element is AND, two elements are NOT, the group of elements is UNEMNAL, the element is OR — NOT, the pulse driver, the delay element, the frequency divider, the comparison circuit, the information output of the K-th memory block is connected to the first input of the K-th element UNEQUAL DETAILS of the group, the second input and output of which are connected respectively to the output of the K.th digit of the register of the sign and to the first input of the Kth element OR of the group whose output is connected to the input of the initial setting of the Kth digit of the register, the output of the older digit and entrance w at the shift of the low-order bit of which are connected, the output of the K-th register bit is connected to the second input of the k-th element of the OR group, to the K-th input of the encoder and to the k-th input of the second element And whose output is connected to the first input of the first element or through the first the element is NOT connected to the first input of the first element AND, the output of the first element OR is connected to the counting input of the first address counter and the input of the pulse former, the output of which is connected to the inputs 0 entries of the shift registers and to the installation input in O of the second address counter, the overflow output of which is connected to the second input of the first element. And, the output of the frequency divider is connected to the counting input 5 second address counter, register entry input, synchronization inputs of group shift registers, first input of second OR element, device sync pulse input connected to synchronization input 0 register and through the delay element with the input of the frequency divider, the installation input K of the shift register of the group is connected to the K-th input of the initial state of the device group, the output of the higher bits of the K-th 5 of the group's shift register is connected to the fill input when the lower bit of the K-th group shift register is shifted, and the output of the K-th bit j-ro of the shift register O 1, L) is connected to the j-th bit of the first 0 of the k-ro input of the switch of the group address, the second input of which is connected to the input of the lower bits of the device address, the control input of the switches of the address of the group is connected to the input of the mode reference 5 operation of the device and to the first input of the element OR-NOT, the output of which is connected to the input of the record of the first address counter, the second input of the elements OR-NOT, the synchronous input of the poll sign register and 0, the second input of the first element OR is connected to the device start input, the control inputs for selecting a group of memory blocks are connected to the output of the second element OR. whose first input is connected to 5 of initiating access to the device memory, the control inputs for reading and reading of the memory blocks of the group are connected to the read input of the device, the first and second inputs and output of the comparison circuit are connected respectively to the output of the first address counter, the input of the search area number and the display after the device has finished working, the output and input of the initial installation of the first counter of the address are connected respectively to the output of the higher bits of the device address and to the output of the second element I, the output of the K-th group memory block is connected to K- mu discharge information output device, the output of the pulse former through the second element is NOT connected to the input of the initial installation; output of the lower bits of the address of the device register; the output of the encoder is connected to the WE Uto and,-, and, 4i 4   LL nv HV receive code. s96ig -ffV- . .- V v “--- A ---  coo. nsnAnna to uslmayu V-f L / zxzir - m CL 2 L -four nv.,