JPH0833896B2 - Failure detection method for character string retrieval device - Google Patents

Description

The present invention relates to a failure detection method in a character string search device.

[Conventional technology]

One of the character string search devices is one in which a plurality of cells each consisting of a pair of a key register for one character and a comparator are connected in cascade. In this character string search device, each character forming a key word is set in the key register of each cell, and the character of the key register is used as one input of the comparator of the cell, and the character string to be searched is searched. The data sequentially cut out in character units are simultaneously given as the other input of the comparator of each cell, and the comparison result signal is transmitted to the subsequent cell to search whether or not the target character string matches the key word. The feature of this is that the logical structure is simple and suitable for LSI.

For this type of character string search device, for example, AC
M SIGIR conf. June 6-8, 1983, PP3-9.

[Problems to be solved by the invention]

In a character string search device configured by connecting a plurality of cells each consisting of a pair of the key register and the comparator in a cascade, conventionally, no consideration has been given to the failure detecting means of the key register and the comparator, and the reliability of There was a problem in terms.

Generally, in an information processing apparatus, a redundant bit is added to data and a check circuit is provided to enable detection of a failure in a register or the like. If this is applied to the key register failure detection of the character string search device, the redundant bit of the key register in each cell, the check circuit, occupies about 20% of the gate amount constituting the cell. In the case of an apparatus for searching a large number of character strings by connecting cells in a cascade of, for example, several hundred bytes, there is a problem that although it involves a large amount of hardware resources, it does not contribute at all to the failure detection of the comparator.

It is an object of the present invention to provide a character string search device configured by connecting a plurality of cells each consisting of a pair of a key register and a comparator in a cascade, without providing redundant bits or a check circuit for each key register. It is to detect the key register failure of the cell and also to ensure the normality of the comparator match detect function.

[Means for solving problems]

The above object is achieved by providing means for supplying the other input of the comparator with data having the same value as the setting data for the key register when setting the key word for the key register.

[Action]

A character string search device capable of performing a search process with a key word of n characters has at least key registers KR _{1 to} KR _n and CP ₁
~ CP _n comparator. Prior to inputting the data to be searched to the character string search device, key words are sequentially set in units of characters in KR ₁ to KR _n . When the KR ₁ is first character key word is set, the value of the KR ₁ is input to one of the CMP _1, the data equivalent to the data input to KR ₁ is to simultaneously CPM ₁ of the other input Is input, CPM ₁ should output a match signal if KR ₁ and CMP ₁ are normal. Therefore, when you set the first character of the key word to KR ₁ , check the value of the match signal of CMP ₁ ,
If the value is "1" (match), the normality of the match detection function of KR ₁ and CMP ₁ can be confirmed, and if the value is "0" (mismatch), the match detection function of KR ₁ or CMP ₁ Can detect failures. Sequentially by running, can confirm the normality of the coincidence detection comparator setting key words and at the same time as the key register of each cell with respect to more KR ₁ the operation of ~KR _n, CMP ₁ ~CMP _n.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of a character string search device to which the failure detection system of the present invention is applied.

Reference numeral 101 is a register, 103 is a register that receives the output signal 102 of the register 101, 105 is an incrementer that receives the output signal 104 of the register 103 as input, and outputs a value obtained by adding 1 to the value of the signal 104 to 106. , Its output 106 is register 101
Input signal. That is, the registers 101 and 103 and the incrementer 105 constitute a counting circuit, which is initialized by the reset signal 100 of the register 101. 110 is a key set instruction signal, 111 is a flip-flop that receives the value of the set instruction signal 110, and 113 is a flip-flop 1
It is a flip-flop which receives the value of the output signal 112 of 11 and outputs a signal 114.

141-144 are cells connected in cascade, and the comparison result of the key and the data in the cells becomes output signals 151-154 and propagates to the cells of the next stage. In this example, for simplicity of explanation, only cells in four stages are shown. 150 is an output signal of the comparison result of the cell (not shown) in the preceding stage of the cell 141,
An output signal 154 is connected to a cell (not shown) in a subsequent stage of the cell 144. A decoder 120 decodes the value of the output 102 of the register 101 and outputs the signals 121 to 124 by using the signal 112 as an output enable signal. 130 is also a decoder, which decodes the value of the output 104 of the register 113 and outputs the signal 11
Signals 131 to 134 are output using 4 as an output enable signal. 161 to 164 are signals for notifying the occurrence of a failure at the time of setting a key in each cell, which is ORed by the OR circuit 165 and held by the flip-flop 167 via the output signal 166.

170 is a 9-bit input data line including 1 bit of parity bit, and is input to the data register 171. The output signal 172 of the data register 171 is the cells 141-144.
Is input to the parity check circuit 173 and is checked by the parity check circuit 173. When the parity check circuit 173 detects a data error, the value of the output signal 174 becomes "1" and is held in the flip-flop 175. The output signal 168 of the flip-flop 167 and the output signal 176 of the flip-flop 175 are ORed by the OR circuit 177, and the output signal 178 notifies the host device of the occurrence of the failure.

An 8-bit data line of the input data line 170 excluding the parity bit is connected to cells 141 to 144 for use as a key setting path. Eight data lines of 172 excluding the parity bits are also connected to the cells 141 to 144 for supplying the searched data at the time of searching.
Reference numeral 180 is a signal line indicating that the data to be searched is supplied to the input data line 170, and its value is the flip-flop 18
The value of the output signal 182 of the flip-flop 181 is held in the flip-flop 183. The output signal 184 of the flip-flop 183 is ORed with the output signal 114 of the flip-flop 113 by the OR circuit 185, and the output signal 186 of the OR circuit 185 becomes the set condition of the flip-flop 175.
An OR circuit 187 outputs an OR output 188 of the signals 112 and 182, and the output signal 188 is a setting condition of the register 171.

FIG. 2 is a block diagram showing the internal structure of one cell. Here, the cell 142 of FIG. 1 is shown. 201 is a key register (KR ₂ ) for input data line 170 in FIG.
The 8-bit data excluding the parity bit is fetched when the output signal 122 of the decoder 120 in FIG. 1 is "1". Reference numeral 203 denotes a comparator (CMP ₂ ) which receives the value of the output signal 202 of the register 201 as one input and outputs the value of 8-bit data excluding the parity bit from the output 172 of the input data register 171 of FIG. The other input. COM ₂ 203 outputs "1" when a match is detected and "0" when a mismatch is detected. 205 is an AND circuit, which is the output signal 204 of the CMP ₂ 203.
And the AND value of the value of the comparison result output signal 151 of the preceding cell 141 is output to the signal line 206. A flip-flop 207 inputs the value of the signal 206 and propagates the comparison result output signal 152 to the cell 143 at the next stage. 208 is an inverting circuit (inverter)
Then, a value obtained by inverting the value of the signal 204 is output to the signal line 209. 210 is an AND circuit that ANDs the value of the signal 209 and the value of the output signal 132 of the decoder 130 in FIG. 1, and outputs the AND output to the signal line 162.

Next, the operation at the time of key setting in FIGS. 1 and 2 will be described with reference to the time chart in FIG.

First, the signal 100 becomes "1", and 101, 103 and 105
The counting circuit composed of is initialized. That is,
The value of the register 101 becomes _{0 at} the phase of the clock T _{0 at} the point A, and therefore the register 10 becomes at the phase of the next clock T _1.
The value of 3 becomes 0. After that, the key is four cells 141-144
Since the key set instruction signal 110 becomes “1” for four cycles in the phase of T ₀ , the flip-flop 11
1 latches the signal 110 at T ₁ , and the flip-flop 113 latches the output signal 112 of the flip-flop 111 at T ₀ . The value of the key to be set in the key registers KR ₁ to KR _{4 of} the cells 141 to 144 is sent to the data input line 170 one cycle later than the key set instruction signal 110 by half a cycle.

On the other hand, in the register 101, the value of the flip-flop 113 is “1”.
During this period, it is triggered by the phase of T ₁ and holds the value added by 1 for each cycle. That is, register 10
The value of 1 indicates the cell number for setting the key transmitted to the input data line 170 during the key setting operation, and the decode signals 121 to 124 obtained by decoding the value of the register 101 by the decoder 120. It has become a trigger condition key register KR ₁ ~KR ₄ in each cell 141-144. Therefore, the key value of the data input line 170 is latched in the key register 201 (KR ₂ ) of the cell 142 at the phase of T _{0 at} the point C. In this way, the decode signal 121 of the decoder 120 is
The key values of the data input line 170 are sequentially set to KR ₀ to KR ₄ of the cells 141 to 144 by using ˜124 as a trigger.

Normally, after the key word is set to KR ₀ to KR _n , the data to be searched is sequentially transmitted to the data input line 170, and the register 171 latches the value of the data input line 170 on a cycle-by-cycle basis. In FIG. 1, when the key is set, the key value of the data input line 170 is latched in the register 171 for each cycle. Therefore, looking at cell 142,
The value of the key corresponding to the key register 201 (KR ₂ ) is set at the T ₀ phase of point C, and at the same time, the same value is latched in the register 171 and held for one cycle until the next T ₀ phase. It As described above, the data on the data input line 170 includes the parity bit and is latched in the register 171 including the parity bit.

The normality of the key data of the register 171 is checked by the parity check circuit 173. If there is an error, the value of the signal 174 becomes "1" and the flip-flop 175
Held in. In the example of FIG. 3, since the abnormality of the key data to be set in KR ₂ is found in the path from 170 to 175, the flip-flop 175 is in the phase of T _{1 at} the point D.
Has been set.

Flip-flop 175 is not set if the data normality on the path from 170 to 175 is confirmed, but if there is a failure in key register KRi, flip-flop 1
67 is set. That is, for example, when there is a failure in KR ₂ of the cell 142, at the point C, the 8-bit key pattern set in the key register 201 (KR ₂ ) and the register 17
8-bit key except the parity bit set to 1. Since the patterns do not match, the value of the output signal 204 of the comparator 203 is "0" in FIG. 2, and the signal 209 obtained by inverting the value of the signal 204 by the inverter 208 is "1". In the cycle in which the value of the register 171 and the value of the key register 201 should match, the value of the register 103 is decoded by the decoder 130.
Of the decoded signals 131 to 134 obtained by decoding with
During the period when 132 is “1”, the AND condition of the AND circuit 210 is satisfied during the period of “1” of the signal 132, and the fault detection line 1
Since "1" is output to 62, the flip-flop 167 is set at the phase of T _{1 at} the point D. Even if the value of the register 171 and the value of the key register 201 match, the comparator 2
If the 03 match detection function is faulty, the D point
The flip-flop 167 is set at the phase of T ₁ .

At the time of search, the key value of the key register 201 (KR ₂ ) becomes one input of the comparator 203, and the output 172 of the register 171 is given to the other input of the comparator 203 as search target data, Both match, and the comparison result signal of the preceding cell
When 151 is “1”, the AND condition of the AND circuit 205 is satisfied, and the flip-flop 207 becomes “1”. Further, the output 152 of the flip-flop 207 is transmitted to the next-stage cell as a comparison result signal. In the first-stage cell, the comparison result input is fixed to "1".

〔The invention's effect〕

According to the present invention, in a character string search device configured by connecting a plurality of cells each consisting of a pair of a key register and a comparator in cascade, each key register can be operated without degrading the failure detection function of the key register. Since it is not necessary to add a parity bit to the parity check circuit and to install a parity check circuit, a hardware reduction effect of about 20% can be obtained compared to the case of configuring with a key register with parity check. , With the same amount of hardware, about 20%
It is possible to search with a long key.

Further, in the present invention, since the failure of the key register is detected by using the comparator, the failure of the coincidence detection function of the comparator can be detected at the same time, so that the failure detection function can be further improved and the character string search device It has the effect of preventing malfunctions.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of a character string retrieval device to which the present invention is applied, FIG. 2 is a detailed diagram of one cell in FIG. 1, and FIG. 3 is a key setting in FIGS. 1 and 2. 7 is a time chart for explaining the operation at the time. 141 to 144 ... cell, 170 ... key word and search target data input line, 171 ... register, 161-164 ... fault detection line, 167,175 ... fault detection flip-flop, 201
...... Key register, 203 …… Comparator.

Claims (1)

[Claims] 1. A key register holding characters forming a key word, and the contents of the key register as one input, and data sequentially cut out in character units from a search target character string as another input. A failure detection method in a character string search device in which a plurality of cells each including a comparator are connected in a cascade, wherein an input means for inputting characters forming a key word and a search target character string and a key word A means for designating the operation of setting the constituent characters in the key register or the operation of searching for the key word from the search target character string, and the operation of searching for the key word from the search target character string, Data that is cut out in character units from the search target character string is sequentially stored, and the data register sent to each cell and the characters that make up the key word are set in the key register. In the operation, the means for sequentially designating the cells and generating the timing for setting each character forming the key word input from the input means to the key register in the different cell, and the key word are In the operation of setting in the key register, at the same time when the characters forming the key word are set in the key registers, the characters forming the key word input from the input means are set in the data register at the same time. Means for setting the key word to the key register of each cell and inputting it to the comparator as a character string to be searched when checking the existence of a match. A failure detection method for a character string search device characterized by: