String comparator for searching for reference character string of arbitrary length

A string comparator for searching the address of a stored string having substantially the same content as that of an input reference string, comprising:

• memory means, including a number of memory cells arranged in a matrix form having a plurality of rows and a plurality of columns, the rows of the memory means being grouped into a plurality of groups, and one string being written to a portion of one column corresponding to one group of rows such that one of the memory cells belonging to one group of rows in the same column has a predetermined binary value written thereto, so that the column position indicates an address of a string stored in each column and a position of one memory cell written with the predetermined binary value of the memory cells belonging to the same column and to the same row group indicates a content of a string stored in the above mentioned portion of one column corresponding to one row group;
• and
• means, coupled to the memory means, and including a plurality of row decoders, each provided in correspondence to one of the plurality of groups of rows and each receiving the input reference string to be compared, and a block decoder controlled by a counter counting a clock signal and for selecting one of the row docoders in accordance with the count value of the counter so as to bring the selected row decoder into an active condition, so that the block decoder selects one of the row groups and the row decoder selectively brought into the active condition selects one row of the memory cell matrix belonging to the selected row group and corresponding to the content of the input reference string to be compared, so that the content of the memory cells belonging to the row selected by the row selecting means is read out;
• wherein the stored strings are composed of a plurality of characters each having a length of J.times.K bits, and wherein the memory cell matrix has a capacity of 2.sup.J .times.K.times.M words by N bits and is divided into K.times.M memory blocks each consisting of 2.sup.J rows by N columns, so that the each character of the strings is divided into K pieces of J bit data and the K pieces of data are sequentially stored in the same numbered column in the respective memory blocks;
• wherein each reference string is composed of a plurality of characters each having a length of J.times.K bits and each character of the reference string is divided into K pieces of J bit data so that the data pieces of the J bit length are sequentially supplied to the string comparator in response to a clock signal, and wherein the row selecting means is associated with means for counting the clock signal so as to supply to the row selecting means the counter output which designates the memory block corresponding to the inputted data piece of the J bit length;
• wherein the row selecting means comprises:
• a first decoder, receiving the data pieces of the reference string to be compared, for decoding the data pieces to 2.sup.J parallel binary signals representing the row position in each memory block corresponding to the content of the received data piece;
• a second decoder, receiving the content of the counting means, for decoding the count output to K.times.M parallel binary signals representing the memory block corresponding to the count output;
• and
• an AND gate array including 2.sup.J .times.K.times.M AND gates which are divided into K.times.M groups, each group having 2.sup.J AND gates, the AND gates of each group having one input connected to receive the parallel binary signals from the first decoder in one-to-one relation and having their other inputs connected in common to receive the corresponding one binary signal from the second decoder, the outputs of all the AND gates being connected to the corresponding rows of the memory cell matrix in one-to-one relation, so that there is selectively driven one row designated by the first decoder in response to the received data piece of the reference string, in one memory block designated by the second decoder.

A string comparator for searching the address of a stored string having substantially the same content as that of an input reference string, comprising:

• memory means including a number of memory cells arranged in a matrix form having a plurality of rows and a plurality of columns, the rows of the memory means being grouped into a plurality of groups, and one string being written to a portion of one column corresponding to one group of rows such that of the memory cells belonging to one group of rows in the same column has a predetermined binary value written thereto, so that the column position indicates an address of a string stored in each column and a position for one memory cell written with the predetermined binary value of the memory cells belonging to the same column and to the same row group indicates a content of a string stored in the above mentioned porton of one column corresponding to one row group;
• and
• means, coupled to the memory means, and including a plurality of row decoders each provided in correspondence to one of the plurality of groups of rows and each receiving the input reference string to be compared, and a block decoder controlled by a counter counting a clock signal and for selecting one of the row decoders in accordance with the count value of the counter so as to bring the selected row decoder into an active condition, so that the block decoder selects one of the row groups and the row decoder selectively brought into the active condition selects one row of the memory cell matrix belonging to the selected row group and corresponding to the content of the input reference string to be compared, so that the content of the memory cells belonging to the row selected by the row selecting means is read out;
• column selecting means for driving in parallel all the columns of the memory cell matrix when the comparator is put in a comparison operation, the column selecting means being responsive to an input address to selectively drive one column of the memory cell matrix corresponding to the input address when the comparator is put in a store operation;
• means for writing the input data in the one column of the memory cell matrix selected by the column selecting means;
• means, connected to all the columns of the memory cell matrix, for reading and outputting the content of the memory cells of all the columns belonging to the row selected by the row selecting means;
• and
• an encoder, receiving the output of the reading means, for encoding the reading means output to an address for the stored string having substantially the same content as that of the input reference string.

A string comparator for searching the address of a stored string having substantially the same content as that of an input reference string, each string composed of a plurality of characters, each having a length of J.times.K bits, the string comparator comprising:

• memory means, including a store part composed of memory cells arranged in a matrix form of 2.sup.J .times.K.times.M rows by N columns and an indicator part arranged in one row by N columns, for indicating the occupation of each column of the memory cell matrix, the rows of the memory means being grouped into a plurality of groups, and one string being written to a portion of one column corresponding to one group of rows such that one of the memory cells belonging to one group of rows in the same column has a predetermined binary value written thereto, so that the column position indicates an address of a string stored in each column and a position of one memory cell written with the predetermined binary value of the memory cells belonging to the same column and to the same row group indicates a content of a string stored in the above mentioned portion of one column corresponding to one row group;
• means, coupled to the memory means and including a plurality of row decoders each provided in correspondence to one of the plurality of groups of rows and each receiving the input reference string to be compared, and a block decoder controlled by a counter counting a clock signal and for selecting one of the row decoders in accordance with the count value of the counter so as to bring the selected row decoder into an active condition, so that the block decoder selects one of the row groups and the row decoder selectively brought into the active condition selects one row of the memory cell matrix belonging to the selected row group and corresponding to the input reference string to be searched;
• reading means for reading the content of the memory cells belonging to the row selected by the row selecting means and outputting the content of the memory cells of the column of the selected row;
• and
• an encoder receiving the output of the reading means and encoding the content of the memory cells of the column in the selected row respectively to the addresses for the input reference string to be searched.

A string comparator for searching the address of an stored string having substantially the same content as that of an input reference string, each string composed of a plurality of characters, each having a length of J.times.K bits, the string comparator comprising:

• memory means including a store part composed of memory cells arranged in a matrix form of 2.sup.J .times.K.times.M rows by N columns and an indicator part arranged in one row by N columns for indicating the occupation of each column of the memory cell matrix, the rows of the memory means being grouped into a plurality of groups, and one string being written to a portion of one column corresponding to one group of rows such that one of the memory cells belonging to one group of rows in the same column has a predetermined binary value written thereto, so that the column position indicates an address of a string stored in each column and a position of one memory cell written with the predetermined binary value of the memory cells belonging to the same column and to the same row group indicates a content of a string stored in the above mentioned portion of one column corresponding to one row group;
• means, coupled to the memory means and including a plurality of row decoders each provided in correspondence to one of the plurality of groups of rows and each receiving the input reference string to be compared, and a block decoder controlled by a counter counting a clock signal and for selecting one of the row decoders in accordance with the count value of the counter so as to bring the selected row decoder into an active condition, so that the block decoder selects one of the row groups and the row decoder selectively brought into the active condition selects one row of the memory cell matrix belonging to the selected row group and corresponding to the input reference string to be searched;
• reading means for reading the content of the memory cells belonging to the row selected by the row selecting means and outputting the content of the memory cells of the column of the selected row;
• and
• an encoder receiving the output of the reading means and encoding the content of the memory cells of the column in the selected row respectively to the addresses for the input reference string to be searched,
• wherein the row selecting means comprises:
• a first decoder receiving input data to be compared or stored and decoding the data to signals corresponding to the row of the memory cell matrix and representing the row position of the memory cell matrix corresponding to the content of the input data;
• a second decoder receiving the content of the counter and decoding the content to signals corresponding to the row of the memory cell matrix and representing the row position of the memory cell matrix corresponding to the content;
• an OR gate array of 2.sup.J OR gates, each OR gate having a first input receiving the corresponding one of the decoded signals from the first decoder and a second input receiving an operation made signal indicating the store operation or comparison operation;
• and
• an AND gate array of 2.sup.J .times.K.times.M AND gates, each AND gate receiving respectively one of the decoded signals from the decoder and the output of the corresponding OR gate in the OR gate array;
• an EXCLUSIVE-OR gate receiving two operation mode signals and outputting a signal to the enable input of both the first and the second decoders;
• an AND gate receiving the same two operation mode signals and outputting a signal to the second inputs of all the OR gates in the OR gate array;
• and
• an OR gate receiving the same two operational mode signals and outputting a signal to drive the line connected to the indicator part.