BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention generally relates to a content addressable memory having a function for extending the width of data to be searched to a plurality of words. More particularly, the present invention relates to a content addressable memory having such a mechanism that, if a plurality of words are combined to form one entry, and each of the words constituting the entry is searched to detect a match for all the words, then a match for one entry is detected.  
           [0003]    2. Description of the Related Art  
           [0004]    A content addressable memory (CAM) includes a plurality of memory words arranged (hereinafter referred to as “words”) each having digital data therein. The CAM receives search data, and searches for a memory word containing digital data of the bit pattern matched with the entire portion or a predetermined portion of the bit pattern of the received search data.  
           [0005]    [0005]FIG. 8 is a circuit block diagram of the fundamental structure of a conventional CAM  100 . The CAM  100  includes a great number of words  110 _ 1 ,  110 _ 2 , . . . , and  110 _n composed of memory cells of m bits which are arranged side-by-side in the horizontal direction as viewed in FIG. 8 to form one word. The CAM  100  further includes a search data register  120  which receives and latches the search data of one word. The search data latched by the search data register  120  is supplied to the memory cells that form each word via search bit lines  130 _ 1 ,  130 _ 2 , . . . , and  130 _m, where the entire portion or a predetermined portion of the bit pattern of the search data is compared to the bit pattern of the portion corresponding to that bit pattern among the storage data stored in each word to detect a match or mismatch. A match signal of logic ‘1’ is output onto the match line corresponding to the word matched with the bit pattern among match lines  140 _ 1 ,  140 _ 2 , . . . , and  140 _n that correspond to the words  110 _ 1 ,  110 _ 2 , . . . , and  110 _n, respectively. The remaining match lines have logic ‘0’. As used herein, logic ‘1’ indicates a power supply potential, and logic ‘0’ indicates a ground potential.  
           [0006]    The signals output on the match lines  140 _ 1 ,  140 _ 2 , . . . , and  140 _n are stored in flag registers  150 _ 1 ,  150 _ 2 , . . . , and  150 _n, respectively. As an example shown in FIG. 8, it is assumed that ‘0’, ‘1’, ‘1’, ‘0’, . . . , ‘0’, and ‘0’ are stored in the flag registers  150 _ 1 ,  150 _ 2 ,  150 _ 3 ,  150 _ 4 , . . . ,  150 _n- 1 , and  150 _n, respectively. The signals stored in the flag registers  150 _ 1 ,  150 _ 2 , . . . , and  150 _n are input to a priority encoder  160 . An encode pulse EP is also input to the priority encoder  160 . Each time an encode pulse EP is input, an address signal AD corresponding to a higher priority flag register in the flag registers (the flag registers  150 _ 2  and  150 _ 3  in this example) that store a signal of logic ‘1’ is sequentially output according to a predetermined priority. Herein, the smaller the suffix, the higher the priority. Therefore, when one encode pulse EP is input, the memory address corresponding to the flag register  150 _ 2  is output. The address signal AD output from the priority encoder  160  is then input to an address decoder  170 , if necessary. The address decoder  170  decodes the input address signal AD, and outputs an access signal (a signal of logic ‘1’ in this example) onto a word line (the word line  180 _ 2  in this example) corresponding to the input address signal AD among word lines  180 _ 1 ,  180 _ 2 , . . . , and  180 _n corresponding to the words  110 _ 1 ,  110 _ 2 , . . . , and  110 _n, respectively. The data stored in the word  110 _ 2  corresponding to the word line  180 _ 2  on which the access signal is output is read by an output register  190 .  
           [0007]    When another encode pulse EP is input, the address of the word  110 _ 3  corresponding to the flag register  150 _ 3  is obtained. Accordingly, the CAM  100  is a memory which searches the storage data which is stored in the words  110 _ 1 ,  110 _ 2 , . . . , and  110 _n by using the entire portion or a predetermined portion of the search data to obtain the address of the word containing the storage data matched therewith and to read the entire data which is stored in that word, if necessary.  
           [0008]    In the context of a content addressable memory having such a fundamental structure, there has been proposed a technique to extend the width of data to be searched for a match to two or more words. FIG. 9 is a block diagram of an example of the content addressable memory having a data width extension capability, as described in Japanese Patent Application Publication No. Hei 7-226091. The same components as those in the content addressable memory shown in FIG. 8 are designated by the same reference numerals, and a description thereof is not repeated.  
           [0009]    The match lines  140 _ 1 ,  140 _ 2 , . . . which extend from the words  110 _ 1 ,  110 _ 2 , . . . are connected to first input terminals of AND gates  200 _ 1 ,  200 _ 2 , . . . , respectively. Second input terminals of the AND gates  200 _ 2 ,  200 _ 3 , . . . are connected to the output terminals of OR gates  210 _ 2 ,  210 _ 3 , . . . , respectively, and first input terminals of the OR gates  210 _ 2 ,  210 _ 3 , . . . are connected to a first search control line  220 . However, the OR gate corresponding to the uppermost AND gate  200 _ 1  is omitted in FIG. 9, and a second input terminal of the AND gate  200 _ 1  is directly connected to the first search control line  220 .  
           [0010]    The output terminals of the AND gates  200 _ 1 ,  200 _ 2 , . . . are connected to the data input terminals of first flag registers  230 _ 1 ,  230 _ 2 , . . . , respectively. The output terminals of the first flag registers  230 _ 1 ,  230 _ 2 , . . . are connected to the input terminals of second flag registers  240 _ 1 ,  240 _ 2 , . . . , respectively. The output terminals of the second flag registers  240 _ 1 ,  240 _ 2 , . . . are connected to the priority encoder  160  shown in FIG. 8 (not shown in FIG. 9), and are also connected to second input terminals of the OR gates  210 _ 2 ,  210 _ 3 , . . . , respectively, which correspond to the memory words one stage below in FIG. 9.  
           [0011]    A match result latch signal S 1  which is output on a match result latch control line  250  is input to the clock terminals of each first register and each second flag register. The input data which is input from the data input terminals D of each first and second registers is latched according to the match result latch signal S 1 . Specifically, the input data is latched by each first flag register at the rise time “a” of the match result latch signal S 1 , and the input data is latched by each second flag register at the fall time “b” of the match result latch signal S 1 .  
           [0012]    A match search operation for the thus constructed content addressable memory is now described. It is assumed, as shown in FIG. 9, that the storage data A, B, C, D, C, F, . . . are stored in the memory words  110 _ 1 ,  110 _ 2 ,  110 _ 3 , _ 4 ,  110 _ 5 ,  110 _ 6 , . . . , respectively. To search the storage data individually rather than in combination, a first search timing signal S 2  is output onto the first search control line  220  at the time of inputting search data REF_DATA for the purpose of search operation. Given that data ‘B’ is input as search data REF_DATA, then a match signal of logic ‘1’ is output onto the match line  140 _ 2  corresponding to the word  110 _ 2  which stores the data ‘B’, and is input to the AND gate  200 _ 2 . In addition, the first search timing signal S 2  is also input to the AND gate  200 _ 2  via the OR gate  210 _ 2 . Thus, a signal of logic ‘1’ is output from the AND gate  200 _ 2 . At this time, a signal of logic ‘0’ is output onto the remaining match lines, and the corresponding AND gates  200 _ 1 ,  200 _ 3 ,  200 _ 4 , . . . thus output a signal of logic ‘0’.  
           [0013]    The signal of logic ‘1’ output from the AND gate  200 _ 2  is latched by the first flag register  230 _ 2  at the rise time “a” of the match result latch signal S 1  output on the match result latch control line  250 , and is latched by the second flag register  240 _ 2  at the subsequent fall time “b” of the match result latch signal S 1 .  
           [0014]    A signal of logic ‘0’ is latched by the remaining first flag registers  230 _ 1 ,  230 _ 3 ,  230 _ 4 , . . . at each timing at which the signal of logic ‘1’ is latched by the first flag register  230 _ 2 , and is then latched by the remaining second flag registers  240 _ 1 ,  240 _ 3 ,  240 _ 4 , . . . at each timing at which the signal of logic ‘1’ is latched by the second flag register  240 _ 2 . Accordingly, the signals of logic ‘0’, ‘1’, ‘0’, . . . which are latched by the second flag registers  240 _ 1 ,  240 _ 2 ,  240 _ 3 , . . . are input to the priority encoder  160  shown in FIG. 8, so that the address signal AD of the memory word  110 _ 2  can be obtained.  
           [0015]    The search operation for data of the extended width is now described. In this example, the data of two words composed of data ‘B’ and data ‘C’ is searched.  
           [0016]    First, data ‘B’ is searched in the same manner as described above. Thus, a signal of logic ‘1’ is latched by the first and second flag registers  230 _ 2  and  240 _ 2  corresponding to the word  110 _ 2 . Next, data ‘C’ is input as search data REF_DATA to do a search. At this time, the first search timing signal S 2  is not output on the first search control line  220 , and the first search control line  220  is maintained in the state of logic ‘0’. When data ‘C’ is input as search data REF_DATA to do a search, a match signal of logic ‘1’ is output onto the match lines  140 _ 3  and  140 _ 5  corresponding to the memory words  110 _ 3  and  110 _ 5 , respectively. Since the signal of logic ‘1’ latched by the second flag register  240 _ 2  is input to the OR gate  210 _ 3 , the match signal on the match line  140 _ 3  is passed through the AND gate  200 _ 3 , and therefore a signal of logic ‘1’ indicating a match is latched by the first and second flag registers  230 _ 3  and  240 _ 3 . On the other hand, since the signal of logic ‘0’ latched by the second flag register  240 _ 4  is input to the OR gate  210 _ 5 , the match signal on the match line  140 _ 5  is interrupted by the AND gate  200 _ 5 , and therefore a signal of logic ‘0’ indicating a mismatch is latched by the first and second flag registers  230 _ 5  and  240 _ 5 . In this way, a data match of two words composed of a pair of data ‘B’ and data ‘C’ is detected. A data match of three or more words is detected in the same way.  
           [0017]    Although the content addressable memory shown in FIG. 9 has a data width extension capability, the data of extended two words, three words or the like must be stored in adjacent memory words in a predetermined order. That is, if a plurality of data to be searched are stored in memory words which are apart from each other or are reversely ordered, e.g., data ‘B’ is stored after data ‘C’, a data match of a plurality of combined data cannot be detected.  
           [0018]    The data structure which requires such a search operation is shown in FIG. 10. FIG. 10 illustrates the data structure in which a data group is composed of sets of four pieces of data which are given attributes I, II, III, and IV, respectively. For clarification of the data group and attribute concept, as an example, the data groups in group numbers  1 ,  2 ,  3 ,  4 , and so on include data belonging to an individual, indicating the name in attribute I, the date of birth in attribute II, the address in attribute III, etc.  
           [0019]    Suppose that the data groups comprising a plurality of data given attributes I, II, III, and IV are stored in the content addressable memory for the purpose of search operation. For example, if the data group in group No.  1  is searched, in some cases, a user may desire to search for data ‘A’ and data ‘B’ in this order to read the remaining data ‘C’ and ‘D’ in the data group containing a data match, or, for example, may desire to search for data ‘A’ and data ‘D’ to read the remaining data ‘B’ and ‘C’, or to search for data ‘B’ before data ‘A’.  
           [0020]    However, the content addressable memory (see FIG. 9) having a data width extension capability cannot perform such a search operation. Furthermore, if data ‘A’ and data ‘B’ are searched for, this content addressable memory cannot distinguish a pair of the data ‘A’ in the column of attribute I and the data ‘B’ in the column of attribute II in the row of group No.  1  from a pair of the data ‘A’ in the column of attribute II and the data ‘B’ in the column of attribute III in the row of group No.  4 . For example, even though the information of attributes III and IV of a particular person where a match is found between the “name” information of attribute I and the “date of birth” information of attribute II is desired, noise other than the required information, such as a further match detection between a pair of attributes II and III, might be generated.  
           [0021]    The aforementioned content addressable memory further has problems in view of the power consumption. For a search operation for a data group having the data structure shown in FIG. 10, when the data group is searched for a particular attribute, the memory words containing other attributes do not need to be searched, but be searched, as well as the memory word containing the particular attribute. In general, the power consumed by a content addressable memory is largely consumed by the search data lines and match lines. It is therefore important that unnecessary operations for these lines be reduced in order to reduce the power consumption.  
           [0022]    For simplification of illustration, in the foregoing content addressable memory, memory words are arranged in a one-dimensional manner. However, a content addressable memory having a large capacity has a two-dimensional structure including a plurality of memory word blocks each being arranged in a one-dimensional manner, and priority encoders in the vertical and horizontal directions in the figure. The content addressable memory having such a two-dimensional structure is well known in the art, and a further illustration or description thereof is omitted herein.  
           [0023]    Accordingly, as described above, a conventional content addressable memory having one entry (in which a plurality of memory words are combined in order to form one data group) which is extended to a plurality of words is associated with the following problems:  
           [0024]    (1) A match search (AND search) cannot be applied to words of which the addresses are apart from each other in one entry.  
           [0025]    (2) The words constituting an entry cannot be searched in an arbitrary order.  
           [0026]    (3) A memory word does not have the ability to distinguish data attributes, possibly resulting in an unnecessary search result in some cases.  
           [0027]    (4) All the words are always to be searched, thereby significantly increasing the power consumption.  
         SUMMARY OF THE INVENTION  
         [0028]    Accordingly, in order to overcome the foregoing problems, it is an object of the present invention to provide a content addressable memory capable of searching one entry composed of plurality of words in an arbitrary word order, while preventing unintended word search, thereby significantly reducing the power consumption.  
           [0029]    As used herein, a group of the memory words at the same number in entries where one entry is composed of a plurality of words is hereinafter referred as a logical segment.  
           [0030]    To this end, in one aspect of the present invention, there is provided a content addressable memory having a function for extending a data width, comprising: a plurality of memory blocks having a plurality of CAM words; physical segments each including one or more memory blocks; entry configuration set means for setting the number of CAM words which are combined to form one entry; and a logical-segment-to-physical-segment converting circuit for converting logical segments constituting one entry to the physical segments according to the setting of the entry configuration set means.  
           [0031]    In another aspect of the present invention, there is provided a content addressable memory having a function for storing a plurality of entries composed of a combination of a plurality of words and searching the entries for each logical segment, comprising: a plurality of memory blocks including a plurality of CAM words for storing the data of one word constituting the entries; and physical segments each including one or more memory blocks, each physical segment including: a search bit line; a plurality of one-word circuits which search for a match between the data stored in the CAM word and search data driven on the search bit line to output a match flag which is a match or mismatch result; and a search bit line driver for driving the search bit line according to the search data, wherein, when the match is searched for, the search bit line only in a physical segment to be searched is driven by the search bit line driver.  
           [0032]    Preferably, each of the physical segments includes a match flag control signal generating circuit for generating a match flag control signal which is a timing signal for capturing and holding a match flag output from the one-word circuit, and, when the match is searched for, the match flag control signal only in a physical segment to be searched is generated.  
           [0033]    Preferably, the content addressable memory further comprises: an entry configuration set register for setting the number of words which are combined to form the entries; and a logical-segment-to-physical-segment converting circuit for converting a logical segment to be searched to a physical segment according to the setting of the entry configuration set register, wherein one or a plurality of words are combined to form each of the entries.  
           [0034]    Preferably, each of the one-word circuits includes a CAM word having a plurality of CAM cells, and word logic for processing a match flag output from the CAM word; the word logic includes a match flag register for holding the match flag, an AND chain having the match flags of the plurality of words coupled each other, and an entry match output circuit for outputting a match flag for the entries; the word having the first address or the final address in the plurality of words constituting each of the entries is the representative word of each corresponding entry; if a word in each of the entries is not the representative word, an AND result of the match flags of that word and the previous word is output from the AND chain; and if a word in each of the entries is the representative word, the AND chain is logically separated from the next word, and an AND result of the plurality of words constituting each corresponding entry is output as the entry match output from the entry match output.  
           [0035]    Preferably, the content addressable memory further comprises an initialization unit for initializing all the match flag registers to be in a match state before a first match search.  
           [0036]    Preferably, the CAM cells are mismatch-detection CAM cells for maintaining all the match flags in a physical segment not to be searched in the initial state or a match state and for capturing the match flags in the corresponding match flag registers.  
           [0037]    In another aspect of the present invention, there is provided a content addressable memory comprising: a plurality of memory blocks having a plurality of one-word circuits; physical segments each including one or more memory blocks; entry configuration set means for setting the number of CAM words which are combined to form one entry; a logical-segment-to-physical-segment converting circuit for converting logical segments constituting one entry to the physical segments according to the setting of the entry configuration set means; and a word circuit chain having the maximum number of corresponding one-word circuits belonging to each physical block which are combined to form one entry, the one-word circuits being connected in series across the physical block. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0038]    [0038]FIG. 1 is a schematic structural view of a content addressable memory according to the present invention;  
         [0039]    [0039]FIGS. 2A to  2 C are conceptual views of an example relationship between physical segments and logical segments;  
         [0040]    [0040]FIG. 3 is a table showing an example relationship between the entry configuration and the entry representative physical segment instruction signal;  
         [0041]    [0041]FIG. 4 is a table showing an example relationship among the entry configuration, the logical-segment-to-be-searched number, and the physical-segment-to-be-searched designation signal;  
         [0042]    [0042]FIG. 5 is a schematic structural view of an exemplary one-word circuit;  
         [0043]    [0043]FIG. 6 is a schematic structural view of an exemplary CAM cell;  
         [0044]    [0044]FIG. 7 is a schematic structural view of an exemplary one-word circuit in the case where one entry is composed of a combination of two words;  
         [0045]    [0045]FIG. 8 is a circuit block diagram of the fundamental structure of a conventional content addressable memory;  
         [0046]    [0046]FIG. 9 is a block diagram of a conventional content addressable memory having a data width extension capability; and  
         [0047]    [0047]FIG. 10 is a table showing an example of data having the group structure. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0048]    A content addressable memory according to the present invention is described in detail with reference to the drawings taken in conjunction with the preferred embodiments.  
         [0049]    [0049]FIG. 1 is a schematic block diagram of the internal structure of a content addressable memory  10  according to the present invention. The content addressable memory  10  is a memory which can be set so that one entry is composed of one word (equal to m bits, for example, m=72), or a combination of two or up to four words. The content addressable memory  10  includes a memory array  12 , an entry set register  14  for setting the entry configuration, a logical-segment-to-physical-segment converting circuit  16 , a timing generating circuit  18 , and a priority encoder  20 . For simplification of illustration, one entry can be composed of a combination of up to four words in the following description, but may be composed of more than four words, for example, up to 16 words.  
         [0050]    In the content addressable memory  10  shown in FIG. 1, the memory array  12  includes four (at least the maximum number of words combined) memory blocks  22  each having N words (N−1, 2, 3, . . . ). In other words, the memory array  12  includes a total of  4 N words. In the content addressable memory  10 , therefore, the total number of entries is  4 N,  2 N,. or N if one entry is composed of one word, two words, or four words, respectively.  
         [0051]    The words in the memory array  12  are designated by addresses  4 n,  4 n+1,  4 n+2, and  4 n+3, where n=0, 1, 2, and so on. In this illustration, a memory block  22  containing N words designated by address  4 n is referred to as “physical segment 0”. Likewise, memory blocks  22  containing N words designated by addresses  4 n+1,  4 n+2, and  4 n+3 are referred to as “physical segment 1”, “physical segment 2”, and “physical segment 3”, respectively. Although one memory block corresponds to one physical segment herein, the present invention is not limited thereto. One physical segment may be composed of a plurality of memory blocks, and the memory blocks belonging to one physical segment may be physically apart from each other.  
         [0052]    The memory block  22  of each of the physical segments  0  to  3  includes one-word circuits  24  of N words, a search bit line driver  26 , search bit lines  27 , a match flag control signal generating circuit  28 , and a match flag control signal line  29 . A data bit line for inputting and outputting storage data to and from each word is not directly related to the present invention, and is not described herein. The data bit line may be common to or separated from the search bit lines. The search bit lines comprise a pair of search bit lines in this illustration, but may alternatively comprise a single search bit line instead of the pair.  
         [0053]    In the memory block  22 , each one-word circuit  24  stores the data of one word, searches for a match between the stored data and the search data, and outputs a match or mismatch result (match flag). The one-word circuit  24  includes CAM words  30  composed of CAM cells of m bits, and word logic  32  for processing the match line outputs from the CAM words  30 . The one-word circuit  24  is described in detail later.  
         [0054]    In response to a physical-segment-to-be-searched instruction signal PSS&lt; 3 : 0 &gt; input from the logical-segment-physical-segment converting circuit  16 , the search bit line driver  26  in the memory block  22  of a physical segment to be searched drives a pair of search bit lines SB&lt;m− 1 : 0 &gt; and /SB&lt;m− 1 : 0 &gt; according to search data SD&lt;m− 1 : 0 &gt; externally supplied to the content addressable memory  10 .  
         [0055]    The physical-segment-to-be-searched instruction signal PSS&lt; 3 : 0 &gt; instructs the memory block  22  of a physical segment to be searched. This signal is input from the logical-segment-to-physical-segment converting circuit  16  to the memory block  22  of each of the corresponding physical segments  0  to  3 .  
         [0056]    In addition to the physical-segment-to-be-searched instruction signal and the search data, a search bit line output timing signal (not shown) which instructs a timing of driving the search bit lines is also input to the search bit line driver  26  from the timing generating circuit  18 . The search bit lines  27  driven by the search bit line driver  26  are connected to the CAM words  30  of all the one-word circuits  24  in the memory block  22  of each corresponding physical segment.  
         [0057]    The content addressable memory  10  is provided with the search bit line driver  26  for each memory block  22 , so that the driving of the search bit lines  27  can be controlled in each memory block  22 . Accordingly, if one entry is composed of a combination of a plurality of words, the search bit lines  27  in the memory block  22  of a physical segment to be searched can only be driven, while the search bit lines  27  in the memory block  22  of a physical segment not to be searched are not driven, thereby significantly reducing the power consumption.  
         [0058]    The match flag control signal generating circuit  28  in the memory block  22  generates a match flag control signal which is a timing signal of holding, in the word logic  32 , the match flag output onto the match line from the CAM word  30  in each one-word circuit  24 .  
         [0059]    A match flag control timing signal which instructs a timing of holding the match line output is input to the match flag control signal generating circuit  28  from the timing generating circuit  18 . A first search/AND search instruction signal (FIRST) which instructs either a first search or an AND search is input to the match flag control signal generating circuit  28  from a unit external to the content addressable memory  10 . The above-noted physical-segment-to-be-searched instruction signal PSS is also input from the logical-segment-to-physical-segment converting circuit  16 .  
         [0060]    In this embodiment, the match flag control signal generating circuit  28  generates a match flag control signal for the memory blocks  22  of all the physical segments if a first search is instructed (FIRST=‘1’). If an AND search is instructed (FIRST=‘0’), it generates a match flag control signal only for the memory block  22  of a physical segment to be searched. The match flag control signal is supplied to the word logic  32  of all the one-word circuits  24  in the memory block  22  of each corresponding physical segment.  
         [0061]    The entry configuration set register  14  and the logical-segment-to-physical-segment converting circuit  16  in the content addressable memory  10  function to logically reconstruct the memory array  12  composed of the memory blocks  22  of the physical segments  0  to  3 .  
         [0062]    In this embodiment, if one entry is composed of one word (see FIG. 2A), all the physical segments  0  to  3  correspond to logical segment  0 . If one entry is composed of a combination of two words (see FIG. 2B), the physical segments  0  and  2  correspond to logical segment  0 , and the physical segments  1  and  3  correspond to logical segment  1 . If one entry is composed of a combination of four words (see FIG. 2C), the physical segments  0  to  3  correspond to logical segments  0  to  3 , respectively.  
         [0063]    The entry configuration set register  14  sets the number of words having sequential addresses which are combined to form one entry. Based on this set value, an entry representative physical segment instruction signal ES&lt; 3 : 0 &gt; is output, and is then supplied to the word logic  32  of all the one-word circuits  24  in the memory block  22  of each corresponding physical segment. This signal is also supplied to the logical-segment-to-physical-segment converting circuit  16 .  
         [0064]    [0064]FIG. 3 is a table showing an example relationship between the entry configuration and the entry representative physical segment instruction signal. As shown in the table of FIG. 3, if one entry is composed of one word, the entry configuration set register  14  outputs an entry representative physical segment instruction signal ES&lt; 3 : 0 &gt;=‘1111’, in which all the memory blocks  22  of the physical segments  0  to  3  are the entry representative physical segments.  
         [0065]    If one entry is composed of a combination of two words, an entry representative physical segment instruction signal ES&lt; 3 : 0 &gt;=‘1010’ is output, in which the memory blocks  22  of the physical segments  3  and  1  are the entry representative physical segments. If one entry is composed of a combination of four words, an entry representative physical segment instruction signal ES&lt; 3 : 0 &gt;=‘1000’ is output, in which the memory block  22  of the physical segment  3  is the entry representative physical segment.  
         [0066]    In response to the setting of the entry configuration set register  14 , the logical-segment-to-physical-segment converting circuit  16  converts logical-segment-to-be-searched number LSS&lt; 1 : 0 &gt;, which is externally input to the content addressable memory  10 , to physical segment number, and outputs a physical-segment-to-be-searched designation signal PSS&lt; 3 : 0 &gt;. The physical-segment-to-be-searched designation signal PSS&lt; 3 : 0 &gt; is supplied to the search bit line driver  26  and the match flag control signal generating circuit  28  in the memory block  22  of each corresponding physical segment.  
         [0067]    [0067]FIG. 4 is a table showing an example relationship among the entry configuration, the logical-segment-to-be-searched number, and the physical-segment-to-be-searched designation signal.  
         [0068]    As shown in the table of FIG. 4, if one entry is composed of one word, once the logical segment  0  is designated according to a logical-segment-to-be-searched number LSS&lt; 1 : 0 &gt;=‘00’, a physical-segment-to-be-searched designation signal PSS&lt; 3 : 0 &gt;=‘1111’ is output. Then, all the memory blocks  22  of the physical segments  0  to  3  are to be searched.  
         [0069]    If one entry is composed of a combination of two words, once the logical segment  0  is designated according to a logical-segment-to-be-searched number LSS&lt; 1 : 0 &gt;=‘00’, a physical-segment-to-be-searched designation signal PSS&lt; 3 : 0 &gt;=‘0101’ is output. Then, the memory blocks  22  of the physical segments  0  and  2  are to be searched. Once the logical segment  1  is designated according to a logical-segment-to-be-searched number LSS&lt; 1 : 0 &gt;=‘01’, a physicalsegment-to-be-searched designation signal PSS&lt; 3 : 0 &gt;=‘1010’ is output. Then, the memory blocks  22  of the physical segments  1  and  3  are to be searched.  
         [0070]    If one entry is composed of a combination of four words, once the logical segment  0  is designated according to a logical-segment-to-be-searched number LSS&lt; 1 : 0 &gt;=‘00’, a physical-segment-to-be-searched designation signal PSS&lt; 3 : 0 &gt;=‘0001’ is output. Then, the memory block  22  of the physical segment  0  is to be searched. Likewise, once the logical segments  1 ,  2 , and  3  are designated according to logical-segment-to-be-searched numbers LSS&lt; 1 : 0 &gt;=‘01’, ‘10’, and ‘11’, respectively, physical-segment-to-be-searched designation signals PSS&lt; 3 : 0 &gt;=‘0010’, ‘0100’, and ‘1000’ are output, respectively, and then the memory blocks  22  of the physical segments  1 ,  2 , and  3  are to be searched, respectively.  
         [0071]    The timing generating circuit  18  in the content addressable memory  10  generates various signals such as an encode-start signal which is supplied to the priority encoder  20  described just below, in addition to the search bit line output timing signal and the match flag control timing signal. The various signals generated by the timing generating circuit  18  are supplied to corresponding elements. For clarification of illustration, the connection of the signals output from the timing generating circuit  18  is omitted in FIG. 1.  
         [0072]    The priority encoder  20  sequentially encodes and outputs the addresses of the words where a match is detected according to a predetermined priority. The priority encoder  20  contains the entry match outputs for all the words. Upon receiving an encode-start signal from the timing generating circuit  18 , the priority encoder  20  outputs, for example, the address of a higher priority word. If one entry is composed of a combination of a plurality of words, the address of the entry representative word is output.  
         [0073]    The one-word circuit  24  is now described.  
         [0074]    [0074]FIG. 5 is a schematic structural diagram of an example of the one-word circuit  24 .  
         [0075]    As described above, the one-word circuit  24  includes a CAM word  30  and word logic  32 , as shown in FIG. 5.  
         [0076]    The CAM word  30  stores the data of one word, and searches for a match detection between the stored data and the search data to output a match flag which is a result of the detection to a match line. The CAM word  30  includes CAM cells  34  of m bits.  
         [0077]    [0077]FIG. 6 is a schematic structural diagram of an example of the CAM cell  34 .  
         [0078]    The CAM cell  34  shown in FIG. 6 is a mismatch-detection CAM cell, and includes a memory cell  36  which stores the data of one bit, and a match detect circuit  38  which compares the data of one bit stored in the memory cell  36  with the search data driven on a pair of search bit lines SB and /SB to output a match flag which is a result of the comparison on a match line ML.  
         [0079]    For simplification of illustration, the memory cell  36  in the CAM cell  34  is not specifically shown in FIG. 6, but may be implemented by any well-known SRAM cell or DRAM cell, or any various ROM cell which can store the data of one bit. In FIG. 6, a circuit for writing/reading data to/from the memory cell  36  is also omitted. This data write/read circuit may be implemented by any well-known circuit.  
         [0080]    The match detect circuit  38  includes four NMOS (n-channel MOS) transistors  40 ,  42 ,  44 , and  46 . The NMOS transistors  40  and  42  are connected in series between the match line ML and the ground line, of which the gates are connected to the inverting output /D of the memory cell  36  and the search bit line SB, respectively. The NMOS transistors  44  and  46  are connected in series between the match line ML and the ground line, of which the gates are connected to the output D of the memory cell  36  and the barred search bit line /SB, respectively.  
         [0081]    In the CAM cell  34  shown in FIG. 6, before a match search operation, the search bit lines SB and /SB are discharged in advance and the match line ML is precharged. When the search bit lines SB and /SB are driven to ‘10’, ‘01’, or ‘00’ according to the search data (data 1, data 0, or Don&#39;t Care) in the match search operation, the match line ML is discharged if a mismatch is detected. If a match is detected, the match line ML is maintained in a precharged state.  
         [0082]    There is no limitation on the configuration of the CAM cell  34 , and either the mismatch-detection or match-detection CAM cell, or otherwise any well-known CAM cell, is available. Preferably, the content addressable memory  10  according to the present invention uses a mismatch-detection CAM cell because the match line in the memory block  22  of a physical segment not to be searched is maintained in the initial state (in a match state), and is not charged or discharged, thereby reducing the power consumption due to the match line.  
         [0083]    Referring to FIG. 5, the word logic  32  in the one-word circuit  24  includes a match flag register  48  for holding the match line output from the CAM word  30 , an AND gate  50  and an OR gate  52  which form an AND chain having match flags of a plurality of words coupled with each other, and an AND gate  54  serving as an entry match output circuit for outputting a result of the entry detection when one entry is composed of a combination of a plurality of words.  
         [0084]    The match flag register  48  has the data input terminal D to which the match line output from the CAM word  30  is input, and the data latch control terminal to which the match flag control signal is input from the match flag control signal generating circuit  28  in the memory block  22  of each corresponding physical segment. In FIG. 5, once the match flag register  48  receives the match flag control signal, it captures the match line output at a timing of the rising edge.  
         [0085]    The AND gate  50  constituting an AND chain has a first input terminal to which the output Q of the match flag register  48  is input, and a second input terminal to which the AND chain output of an adjacent word is input. Therefore, the AND gate  50  outputs a signal of logic ‘1’ if the output from the match flag register  48  of this word indicates logic ‘1’, or a match, and if the AND chain output from an adjacent word indicates logic ‘1’, or a match.  
         [0086]    The OR gate  52  which outputs an AND chain signal has a first input terminal to which the output of the AND gate  50  is input, and a second input terminal to which an entry representative physical segment instruction signal is input. The entry representative physical segment instruction signal instructs the entry representative word which outputs a match signal for the entry if one entry is composed of a combination of a plurality of words. The entry representative physical segment instruction signal indicates logic ‘1’ if a physical segment is the entry representative word, and logic ‘0’, otherwise.  
         [0087]    In this embodiment, if one entry is composed of a combination of a plurality of words, the physical segment containing the word having the largest address for that entry is referred to as the entry representative physical segment. Therefore, the address of the word in the memory block  22  of the entry representative physical segment is output as a match address as a search result. Should the word having the smallest address in an entry be the entry representative word, it is only required that an AND chain be reversely directed.  
         [0088]    As the AND chain output, an AND result of the match flags of that word and the previous word is output if that word is not the entry representative word, which is then provided for an AND search on the next word. On the contrary, if it is the entry representative word, logic ‘1’ is output regardless of the AND result, and is then supplied to the AND chain input of a first one-word circuit in the next entry. In this way, the AND chain is logically separated on the basis of the entry representative word.  
         [0089]    The AND gate  54  functioning as an entry match output circuit has a first input terminal connected to the output of the AND gate  50 , and a second input terminal connected to the entry representative physical segment instruction line. Thus, as the entry match output, an AND result of the match flags of the plurality of words in an entry is output from the AND gate  54  if that word is the entry representative word. Otherwise, or if not the entry representative word, logic ‘0’ indicating a mismatch is output.  
         [0090]    As previously described, in the content addressable memory  10 , a plurality of one-word circuits  24  (up to four in this embodiment) can be combined to form one entry. The case where one entry is composed of a combination of two words is described, by way of example.  
         [0091]    [0091]FIG. 7 is a schematic structural diagram of one-word circuits in the case where one entry is composed of a combination of two words.  
         [0092]    As previously described, in this example, one entry is composed of word i and word i+1, and the word i+1 is the entry representative word. That is, entry representative physical segment instruction signals which are input to the word i and the word i+1 are set to logic ‘0’ and logic ‘1’, respectively.  
         [0093]    Since word i−1 is the entry representative word of another entry, the AND chain input of the word i indicates logic ‘1’. As a result, as shown in FIG. 7, an AND chain is formed such that the word i and the word i+1 are logically coupled with each other. The match flag held in the match flag register  48  of the word i is propagated through the AND chain to the word i+1, and an AND result of the match flags of the word i and the word i+1 is output as the entry match output from the word i+1.  
         [0094]    A search process in the case where one entry is composed of a combination of two words is now described with reference to the schematic structural diagram of FIG. 7.  
         [0095]    First, an initialization unit (not shown) initializes all the match flag registers  48  to be in a match state in order to correctly propagate a series of AND search results to the entry representative word. As in this embodiment, if the CAM cell  34  is of the mismatch-detection type, since all the match lines in the memory block  11  of a physical segment not to be searched are maintained in the initial state or a match state, the match flag may be captured into the match flag register  48  at the time of a first search.  
         [0096]    In the case of a first search (FIRST=‘1’), which is not reflected by the previous search result, the search bit lines in the memory block  22  of a physical segment to be searched are only driven, while the search bit lines in the memory block  22  of a physical segment not to be searched are maintained in a waiting state (both SB and /SB are set to ‘0’ in this embodiment).  
         [0097]    Then, a match between the data stored in the CAM words  30  and the search data is searched for at the same time in a physical segment to be searched, and a match flag is output to each corresponding match line. The match line outputs for the words belonging to a physical segment not to be searched are maintained in the initial state or a match state. Thereafter, in response to a data capture pulse applied to both match flag control signals at a timing of establishing the state of the match lines, a match line output is held in each corresponding match flag register  48 .  
         [0098]    Since the match flag registers  48  of the words belonging to a physical segment not to be searched are maintained in the initial state or a match state, even if the memory block  22  of either physical segment containing the word i or the word i+1 is to be searched for a first search, the search result can be correctly reflected to the entry match output for the entry representative word i+1. Accordingly, if one entry is composed of a combination of a plurality of words, a correct search result can be achieved if any word is first searched for a match.  
         [0099]    In the case of an AND search (FIRST=‘0’), which is reflected by the previous search (first search in this embodiment) result, as in the first search, the search bit lines in a physical segment to be searched are only driven according to the search data. Thereafter, a data capture pulse is applied only to the match flag control signal of a word to be searched at a timing of establishing the state of the match lines, and a match line output is held in each corresponding match flag register  48 .  
         [0100]    In the case of an AND search, since the search result of the first search is held in the match flag register  48  of a word not to be searched, even if the memory block  22  of either physical segment containing the word i or the word i+1 is to be searched for an AND search, a correct AND search result for both can be output as the entry match output from the entry representative word i+1. Accordingly, the content addressable memory  10  according to the present invention can achieve a match search in an arbitrary order.  
         [0101]    The aforementioned AND search result is output as the entry match output from the entry representative word. Then, the addresses of the entry representative words are sequentially output from the priority encoder  20  according to a predetermined priority.  
         [0102]    As described above, a plurality of one-word circuits  24  are combined, and the search lines and the data capture into the match flag registers  48  are individually controlled, so that a correct AND search result can be obtained regardless of the searched order. In effect, the search bit lines and the match line of a word to be searched are only driven while the search bit lines and the match line of a word not to be searched are not driven, thereby greatly reducing the power consumption as compared to a conventional content addressable memory.  
         [0103]    Since the match flag register  48  of a word not to be searched is maintained in the initial state or a match state, for example, if one entry is composed of a combination of four words, a match between the words of which the addresses are apart from each other in an entry can be searched, such as an AND search for a first word and a third word. This allows for a match search while distinguishing attributes of the data stored in each word, and a correct search result can be always achieved.  
         [0104]    Although the match flag register  48  is implemented as an edge-sensitive register (which is known as a master-slave flip-flop) in the illustrated embodiment, the present invention is not limited thereto. A level-sensitive register (which is known as a latch) may also be used. In this case, as known in the art, a timing control is only required such that the latch be closed after the state of a match line has been established.  
         [0105]    Although one entry is composed of a combination of up to four words in the illustrated embodiment, the present invention is not limited thereto, and one entry may be composed of a combination of any number of words.  
         [0106]    While the memory block  22  of each physical segment includes the number of words corresponding to the number of entries in the illustrated embodiment, the present invention is not limited thereto, each physical segment may be divided into a plurality of blocks.  
         [0107]    If each physical segment is divided into a plurality of memory blocks, the search bit line driver  26  and the match flag control signal generating circuit  28  may be shared by the plurality of divided memory blocks in each physical segment, or may otherwise be separately provided for each memory block so that the search bit line drivers  26  and the match flag control signal generating circuits  28  in the respective memory blocks are operated at the same timing.  
         [0108]    The content addressable memory of the present invention basically provides the above-described features.  
         [0109]    Although the content addressable memory according to the present invention has been described in detail, the present invention is not limited to the illustrated embodiment, and a variety of modifications or changes may be made without departing from the spirit and scope of the invention.  
         [0110]    As described above, the content addressable memory according to the present invention allows a plurality of words constituting an entry to be searched for a match in an arbitrary order. In addition, it also allows words of which the addresses are away from each other in an entry to be searched for a match. Furthermore, in the content addressable memory according to the present invention, the search bit lines in a memory block not to be searched are not driven, thereby largely reducing the power consumption. In the content addressable memory according to the present invention which incorporates mismatch-detection CAM cells, the match line in a memory block not to be searched can be maintained in the initial state and is not charged or discharged, thereby further reducing the power consumption due to the match line.
A content addressable memory having a function for extending a data width to a plurality of words includes an entry configuration set unit which sets the number of words to form one entry, and a logical-segment-to-physical-segment converting circuit for converting the logical segments in one entry to the physical segments according to the setting of the entry configuration. The content addressable memory further includes a word circuit chain having the maximum number of one-word circuits belonging to each physical block which are combined to form one entry. The one-word circuits have CAM words associated therewith, and are connected in series over the physical block. A group of the words at the same number in entries where one entry is composed of a plurality of words forms a logical segment. The thus constructed content addressable memory is capable of an AND search for the words of which the addresses are apart from each other in one entry, or allows the words within one entry to be searched in an arbitrary order. Furthermore, a search operation for a portion of the words in one entry is used to do a match search for the entry. In addition, unintended word search is prevented, thereby reducing the power consumption.