Multilevel content addressable memory, multilevel coding method of and multilevel searching method

Abstract

A multilevel content addressable memory, a multilevel coding method and a multilevel searching method are provided. The multilevel coding method includes the following steps. A highest decimal value of a multilevel-bit binary data is obtained. A length of a digital string data is set as being the highest decimal value of the multilevel-bit binary data. The multilevel-bit binary data is converted into the digital string data. If a content of the multilevel-bit binary data is an exact value, a number of an indicating bit in the digital string data is the exact value.

Claims

1. A multilevel coding method of a stored word or an input search word for a multilevel content addressable memory (MCAM), comprising: obtaining a highest decimal value of a multilevel-bit binary data; setting a length of a digital string data as being the highest decimal value of the multilevel-bit binary data; converting the multilevel-bit binary data into the digital string data, wherein if a content of the multilevel-bit binary data is an exact value, a number of an indicating bit in the digital string data is the exact value.

2. The multilevel coding method according to claim 1, wherein the indicating bit in the digital string data is piled up at a right side of the digital string data.

3. The multilevel coding method according to claim 1, wherein the indicating bit in the digital string data is piled up at a left side of the digital string data.

4. The multilevel coding method according to claim 1, wherein the indicating bit in the digital string data is arranged with a predefined pattern.

5. The multilevel coding method according to claim 1, wherein the indicating bit is 0 or 1.

6. The multilevel coding method according to claim 1, wherein if the content of the multilevel-bit binary data is a range from a low decimal value to a high decimal value, the number of the indicating bit in the digital string data is the low decimal value, and a sum of the number of the indicating bit and a number of a wildcard bit in the digital string data is the high decimal value.

7. The multilevel coding method according to claim 6, wherein if the content of the multilevel-bit binary data is the range, the wildcard bit is piled up after the indicating bit in the digital string data.

8. The multilevel coding method according claim 1, wherein the digital string data of the stored word is divided into more than one parts and stored in more than one NAND strings.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a multilevel content addressable memory (MCAM) according to one embodiment.

(2) FIG. 2 illustrates the content of the input search word and the stored word.

(3) FIG. 3 shows a flowchart of the multilevel coding method of the stored word or the input search word for the MCAM.

(4) FIG. 4 shows part of one NAND string stored one of the digital string data of the stored word.

(5) FIG. 5 shows the memory array.

(6) FIG. 6 shows the digital string data stacked in one NAND string.

(7) FIG. 7 shows the memory array with stacked digital string data.

(8) FIG. 8 shows the stored word divided into more than one parts.

(9) FIGS. 9 to 14 illustrate several examples of the comparison operation for the digital string data and the digital string data.

(10) FIG. 15 shows a flowchart of the multilevel searching method for the MCAM.

(11) In the following detailed description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the disclosed embodiments. It will be apparent, however, that one or more embodiments may be practiced without these specific details. In other instances, well-known structures and devices are schematically shown in order to simplify the drawing.

DETAILED DESCRIPTION

(12) Please refer to FIG. 1, which shows a multilevel content addressable memory (MCAM) 100 according to one embodiment. The MCAM 100 includes an input encoder 110, a memory array 120 and an output encoder 130. The memory array 120 includes a plurality of NAND strings STi. Each of the NAND string STi stores one stored word WDi. The input encoder 110 receives an input search word WQ. The input search word WQ is compared with the stored words WDi and then outputs a plurality of comparison results RSi. The output encoder 130 receives the comparison results RSi from the NAND strings STi. For example, if one of the stored words WDi is matched with the input search word WQ, the comparison result RSi is a match signal, such as “1”; if one of the stored words WDi is not matched with the input search word WQ, the comparison result RSi is a mismatch signal, such as “0.” The output encoder 130 outputs the addresses of the NAND strings STi whose stored words WDi are matched with the input search word WQ.

(13) Please refer to FIG. 2, which illustrates the content of the input search word WQ and the stored word WDi. In one embodiment, the input search word WQ is composed of a plurality of multilevel-bit binary data qj. As shown in FIG. 2, the multilevel-bit binary data qj is “111”, “011”, “001” and “000.” The decimal value of “111”, “011”, “001” and “000” are “7”, “3”, “1” and “0” respectively. The stored word WDi is composed of a plurality of multilevel-bit binary data dij. As shown in FIG. 2, the multilevel-bit binary data dij is “010”, “100”, “111” and “001.” The decimal value of “010”, “100”, “111” and “001” are “2”, “4”, “7” and “1” respectively.

(14) In the present embodiment, each of the multilevel-bit binary data qj is converted into a digital string data qsj. For example, “111”, “011”, “001” and “000” are converted into “1111111”, “00001111”, “0000001” and “0000000.”

(15) Similarly, each of the multilevel-bit binary data dij is converted into a digital string data dsij. For example, “010”, “100”, “111” and “001” are converted into “0000011”, “0001111”, “1111111” and “0000001.”

(16) Please refer to Table I, which illustrates the digital string data qsj, dsij converted from the multilevel-bit binary data qj, dij according to one embodiment. The decimal value of the multilevel-bit binary data qj, dij is 0, 1, . . . , 6, 7. The highest decimal value of the multilevel-bit binary data qj, dij is 7. The length of the digital string data qsj, dsij is equal to or larger than the highest decimal value of the multilevel-bit binary data qj, dij. In each of the digital string data qsj, dsij, “1” is an indicating bit. In the example of the table I, the content of the multilevel-bit binary data qj, dij is an exact value, a number of the indicating bit (“1”) in the digital string data qsj, dsij is the exact value. The length of the multilevel-bit binary data qsj, dsij is highest decimal value thereof (the multilevel-bit binary data qsj, dsij is three bits, the highest binary value of the multilevel-bit binary data qsj, dsij is “111” and the highest decimal value of the multilevel-bit binary data qsj, dsij is “7”).

(17) TABLE-US-00001 TABLE I multilevel-bit binary decimal digital string data qsj, data qj, dij value dsij 000 0 0000000 001 1 0000001 010 2 0000011 011 3 0000111 100 4 0001111 101 5 0011111 110 6 0111111 111 7 1111111

(18) Further, as shown in table I, the indicating bit (“1”) in the digital string data qsj, dsij is piled up at a right side of the digital string data qsj, dsij. In other embodiment, the indicating bit (“1”) in the digital string data qsj, dsij may be piled up at the left side of the digital string data qsj, dsij, or may be arranged with a predefined pattern.

(19) Base on above, a multilevel coding method of the stored word WDi or the input search word WQ is provided. Please refer to FIG. 3, which shows a flowchart of the multilevel coding method of the stored word WDi or the input search word WQ for the MCAM 100. In step S110, the highest decimal value of the multilevel-bit binary data qj, dij is obtained. In step S120, the length of the digital string data qsj, dsij is set as being the highest decimal value of the multilevel-bit binary data qj, dij. Then, in step S130, the multilevel-bit binary data qj, dij is converted into the digital string data qsj, dsij.

(20) In other embodiment, the content of the multilevel-bit binary data qj, dij may be a range. Please refer to table II, which illustrates the digital string data qsj, dsij according to another embodiment. If the content of the multilevel-bit binary data qj, dij is a range, a wildcard bit (“X”) is used in the digital string data qsj, dsij. The wildcard bit (“X”) is also called a don't care bit.

(21) TABLE-US-00002 TABLE II multilevel-bit binary data decimal digital string data qsj, qj, dij value dsij 011 3 0000111 010, or 011 2-3 0000X11 011, or 100, or 101 3-5 00XX111 101 5 0011111 011, or 100, or 101 3-5 00XX111 011, or 100, or 101, or 110 3-6 0XXX111 100, or 101, or 110 4-6 0XX1111 100, or 101, or 110, or 111 4-7 XXX1111

(22) As shown the 7-th row in table II, the content of the multilevel-bit binary data qj, dij is a range from 4 to 6. The high decimal value of the range is 6 and the low decimal value of the range is 4. The range window is 3. The number of the indicating bit (“1”) in the digital string data qsj, dsij is 4. The number of the wildcard bit (“X”) in the digital string data qsj, dsij is 2. The wildcard bit (“X”) is piled up after the indicating bit (“1”) in the digital string data qsj, dsij. A sum of the number of the indicating bit (“1”) and the number of the wildcard bit (“X”) in the digital string data qsj, dsij is 6.

(23) That is, the indicating bit (“1”) and the wildcard bit (“X”) are arranged according to the following equations (1) to (3).
the number of the indicating bit=the low decimal value of the range  (1)
the number of the wildcard bit=the range window−1  (2)
the number of the indicating bit+the number of the wildcard bit=the high decimal value of the range  (3)

(24) Please refer to FIG. 4, which shows part of one NAND string STi stored one of the digital string data dsij of the stored word WDi. As shown in FIG. 4, the decimal value of the multilevel-bit binary data dij is a range of 3 to 6, the digital string data dsij is “0XXX111.” The digital string data dsij can be stored in the NAND string STi in sequence. Two transistors TR1, TR2 in each cell CL of the NAND string STi are used together to define “1”, “0” or “X.” For example, if the transistor TR1 is programmed at a low voltage level and the transistor TR2 is programmed at a high voltage level, the content in this cell CL is defined as “0.” If the transistor TR1 is programmed at the high voltage level and the transistor TR2 is programmed at the low voltage level, the content in this cell CL is defined as “1.” If the transistor TR1 is programmed at the low voltage level and the transistor TR2 is programmed at the low voltage level, the content in this cell CL is defined as “X.” In another embodiment, “1”, “0” and “X.” can be defined by other encoding scheme.

(25) Please refer to FIG. 5, which shows the memory array 120. A plurality of NAND strings STi can be arranged in the memory array 120 as a database for simultaneous searching operation. The input search word WQ inputted from the word lines WL will be compared with all of the stored words WDi stored in the NAND strings STi. That is to say, a plurality of instances can be searched in one comparing operation, and an ultra-highly-parallel searching function can be achieved.

(26) Please refer to FIG. 6, which shows the digital string data dsij stacked in one NAND string STi. For the memory array 120 with sufficient number of word lines WL, the digital string data dsij in the stored word WDi can be stacked in one NAND string STi.

(27) Please refer to FIG. 7, which shows the memory array 120 with stacked digital string data dsij. The NAND strings STi that the digital string data dsij are stacked in are arranged in the memory array 120 as a database for simultaneous searching operation. The digital string data qsj of the input search word WQ inputted from the word lines WL will be compared with the stacked digital string data dsij of all of the stored words WDi. That is to say, a plurality of instances can be searched in one comparing operation, and an ultra-highly-parallel searching function can be achieved.

(28) Please refer to FIG. 8, which shows the stored word WDi divided into more than one parts. If the stored word WDi is longer than one NAND string STi can accommodate, it is possible to divide the stored word WDi into to more than one parts and store the stored word WDi in more than one NANS strings. The digital string data qsj is inputted to the corresponding part. The comparison results RSij corresponding the parts can be combined by an AND operation to obtain the comparison results RSi.

(29) Please refer to FIGS. 9 to 14, which illustrate several examples of the comparison operation for the digital string data qsj and the digital string data dsij. As shown in FIG. 9, the digital string data qsj is 5, and the digital string data dsij is 5. The digital string data qsj is equal to the digital string data dsij, so the comparison results RSij is the match signal, such as “1.”

(30) As shown in FIG. 10, the digital string data qsj is 2, and the digital string data dsij is 4. The digital string data qsj does not overlap the digital string data dsij, so the comparison results RSij is the mismatch signal, such as “0.”

(31) As shown in FIG. 11, the digital string data qsj is 2-4, and the digital string data dsij is 5-6. The digital string data qsj does not overlap the digital string data dsij, so the comparison results RSij is the mismatch signal, such as “0.”

(32) As shown in FIG. 12, the digital string data qsj is 4, and the digital string data dsij is 3-6. The digital string data qsj overlaps the digital string data dsij, so the comparison results RSij is the match signal, such as “1.”

(33) As shown in FIG. 13, the digital string data qsj is 2-4, and the digital string data dsij is 4. The digital string data qsj overlaps the digital string data dsij, so the comparison results RSij is the match signal, such as “1.”

(34) As shown in FIG. 14, the digital string data qsj is 2-4, and the digital string data dsij is 4-6. The digital string data qsj overlaps the digital string data dsij, so the comparison results RSij is the match signal, such as “1.”

(35) Based on above, a multilevel searching method for the MCAM 100 is provided. Please refer to FIG. 15, which shows a flowchart of the multilevel searching method for the MCAM 100. In step S210, at least one stored word WDi is stored in at least one NAND string STi. Next, in step S220, the input search word WQ is inputted to the NAND string STi. Then, in step S230, the comparison result RSi is outputted. If the digital string data qsj of the input search word WQ overlap the digital string data dsij of the stored word WDi, the comparison result RSi is a match signal, such as “1.” If the digital string data qsj of the input search word WQ do not overlap the digital string data dsij of the stored word WDi, the comparison result RSi is a mismatch signal, such as “0.”

(36) In the embodiments described above, the indicating bit (“1”) and the wildcard bit (“X”) are used to define the content of the digital string data qsj, dsij. In one embodiment, the indicating bit may be “0.” Please refer to Table III, which illustrates the digital string data qsj, dsij converted from the multilevel-bit binary data qj, dij according to one embodiment. In the example of the table III, content of the multilevel-bit binary data qj, dij is an exact value, a number of the indicating bit (“0”) in the digital string data qsj, dsij is the exact value.

(37) TABLE-US-00003 TABLE III multilevel-bit binary decimal digital string data qsj, data qj, dij value dsij 000 0 1111111 001 1 1111110 010 2 1111100 011 3 1111000 100 4 1110000 101 5 1100000 110 6 1000000 111 7 0000000

(38) In the embodiments described above, the indicating bit (“1” or “0”) in the digital string data qsj, dsij is piled up at a right side of the digital string data qsj, dsij. In other embodiment, the indicating bit (“1” or “0”) in the digital string data qsj, dsij may be piled up at the left side of the digital string data qsj, dsij, or may be arranged with a predefined pattern. Please refer to table IV, the indicating bit (“1”) in the digital string data qsj, dsij is piled up at the left side of the digital string data qsj, dsij.

(39) TABLE-US-00004 TABLE IV multilevel-bit binary decimal digital string data qsj, data qj, dij value dsij 000 0 0000000 001 1 1000000 010 2 1100000 011 3 1110000 100 4 1111000 101 5 1111100 110 6 1111110 111 7 1111111

(40) Please refer to table V, the indicating bit (“1”) in the digital string data qsj, dsij is arranged with a predefined pattern. For example, the indicating bit (“1”) is alternately piled up at the left side and the right side of the digital string data qsj, dsij.

(41) TABLE-US-00005 TABLE V multilevel-bit binary decimal digital string data qsj, data qj, dij value dsij 000 0 0000000 001 1 1000000 010 2 1000001 011 3 1100001 100 4 1100011 101 5 1110011 110 6 1110111 111 7 1111111

(42) According to the embodiment described above, the multilevel-bit binary data is converted into the digital string data, such that data in the stored word WDi and the input search word WQ can be defined with valid ranges for search/comparison. Furthermore, an ultra-high throughput can be obtained from the wide memory array 120. For example, a NAND chip has 16 KB (=128 kb) sensing parallelism, so the MCAM 100 can perform 128 k string comparison at the same time.

(43) It will be apparent to those skilled in the art that various modifications and variations can be made to the disclosed embodiments. It is intended that the specification and examples be considered as exemplary only, with a true scope of the disclosure being indicated by the following claims and their equivalents.