TW202305803A - Multilevel content addressable memory, multilevel coding method and multilevel searching method - Google Patents

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 value of a multilevel-bit binary data is obtained. A length of a digital string data is set as being the highest 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.

Description

Multi-level content addressable memory, multi-level encoding method and multi-level search method

The present disclosure relates to a memory, an encoding method and a searching method, and in particular relates to a multi-level content addressable memory, a multi-level encoding method and a multi-level searching method.

Content addressable memory (content addressable memory, CAM) is a special form of memory, which can identify the address stored in the storage word with the same content according to the input search word. Content addressable memory can serve a variety of applications, especially pattern matching and searching.

Generally speaking, CAM compares the stored word with the input search word in binary form. That is to say, the data stored in the storage word and the input search word are binary 0 or 1.

This disclosure relates to a multi-level content addressable memory, a multi-level encoding method and a multi-level search method, which convert multi-bit binary data into digital string data, so that the data can be defined in various ranges to perform Search and compare.

According to one aspect of the present disclosure, a multilevel encoding method for a stored word or an input search word of a multilevel content addressable memory (MCAM) is proposed. The multi-stage encoding method includes the following steps. Get one of the highest decimal values of a multilevel-bit binary data. Set the length of a digital string data to the highest decimal value of the multi-bit binary data. Convert multi-bit binary data to digital string data. If the content of one of the multi-bit binary data is an exact value, the number of indicating bits of one of the digital string data is an exact value.

According to another aspect of the present disclosure, a multilevel search method for a multilevel content addressable memory (MCAM) is proposed. The multi-stage search method includes the following steps. Store several storage words in several NAND strings. Enter an input search word into these NAND strings. Each of the stored word and the input search word is converted from a multi-bit binary data to a digital string data. If one of the contents of the multi-bit binary data is an exact value, then the number of flag bits of one of the digital string data is an exact value. Output a comparison result. If the digital string data of the input search word overlaps with the digital string data of one of the stored word groups, the comparison result is a matching signal.

According to yet another aspect of the present disclosure, a multilevel content addressable memory (MCAM) is proposed. The multi-level content addressable memory includes an input encoder, a memory array and an output decoder. The input encoder is used for receiving an input search word. A memory array includes several NAND strings. Each NAND string is used to store a storage word. Each stored word and input search word are each converted from a multi-bit binary data to a digital string data. If one of the contents of the multi-bit binary data is an exact value, then the number of flag bits of one of the digital string data is an exact value. The output decoder is used to receive comparison results from the NAND strings.

In order to have a better understanding of the above and other aspects of the present disclosure, the following specific embodiments are described in detail in conjunction with the attached drawings as follows:

Please refer to FIG. 1 , which illustrates a multilevel content addressable memory (MCAM) 100 according to an embodiment. MCAM 100 includes an input encoder 110 , a memory array 120 and an output encoder 130 . The memory array 120 includes several NAND strings STi. Each NAND string STi stores a storage word WDi. The input encoder 110 receives an input search word WQ. The input search word WQ is compared with these stored words WDi, and several comparison results RSi are output. The output encoder 130 receives comparison results RSi from the NAND strings STi. For example, when one of the stored words WDi matches the input search word WQ, the comparison result RSi is a matching signal, such as "1"; when one of the stored words WDi does not match the input search word WQ, the comparison result RSi is a mismatch signal, such as "0". The output encoder 130 outputs the address of the NAND string storing the word WDi matching the input search word WQ.

Please refer to Figure 2, which illustrates the contents of the input search word WQ and the storage word WDi. In one embodiment, the input search word WQ is composed of several multilevel-bit binary data qj. As shown in FIG. 2, the multi-bit binary data qj are, for example, "111", "011", "001" and "000". The decimal values of "111", "011", "001" and "000" are "7", "3", "1" and "0" respectively. The storage word WDi is composed of multi-bit binary data dij. As shown in FIG. 2, the multi-bit binary data dij are, for example, "010", "100", "111" and "001". The decimal values of "010", "100", "111" and "001" are "2", "4", "7" and "1" respectively.

In this embodiment, each multi-bit binary data qj is converted into digital string data (digital string data) qsj. For example, "111", "011", "001", and "000" are converted to "1111111", "00001111", "0000001", and "0000000", respectively.

Similarly, each multi-bit binary data dij is converted into digital string data dsij. For example, "010", "100", "111", and "001" are converted to "0000011", "0001111", "1111111", and "0000001", respectively.

Please refer to Table 1, which illustrates an example of converting multi-bit binary data qj, dij into digital string data qsj, dsij according to an embodiment. The decimal values of the multi-bit binary data qj, dij are 0, 1, . . . , 6, 7. The highest decimal value of multi-bit binary data qj, dij is 7. The length of the digital string data qsj, dsij is equal to or greater than the highest decimal value of the multi-bit binary data qj, dij. In the digital string data qsj and dsij, "1" is an indicating bit. In the example in Table 1, the decimal value of the multi-bit binary data qj, dij is the exact value, and the number of flag bits (ie "1") of the digital string data qsj, dsij is the exact value. The length of the digital string data qsj, dsij is the highest decimal value of the multi-digit binary data qj, dsij (here is three bits, the highest binary value is "111", the highest decimal value is "7" ). Multi-bit binary data qj, dij decimal value Digital string data qsj, 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 Table I

Furthermore, as shown in Table 1, the flag bits (that is, "1") of the digital string data qsj, dsij are accumulated on the right side of the digital string data qsj, dsij. In other embodiments, the flag bit (namely "1") of the digital string data qsj, dsij can be stacked on the left side of the digital string data qsj, dsij or stacked according to a predetermined rule.

According to the above content, a multi-level encoding method for storing word WDi or inputting search word WQ is provided. Please refer to FIG. 3 , which shows a flow chart of the multi-level encoding method of the storage word WDi or the input search word WQ of the MCAM 100 . In step S110, the highest decimal value of the multi-bit binary data qj, dij is obtained. In step S120, set a length of the digital string data qsj, dsij to be the highest decimal value of the multi-bit binary data qj, dij. Next, in step S130, convert the multi-bit binary data qj, dij into digital string data qsj, dsij.

In other embodiments, the content of the multi-bit binary data qj, dij can be a range. Please refer to Table 2, which illustrates the digital string data qsj, dsij according to an embodiment. When the multi-bit binary data qj and dij are within a range, a wildcard bit (ie "X") is used in the digital string data qsj and dsij. The wildcard bit (ie "X") is also known as the don't care bit. Multi-bit binary data qj, dij decimal value Digital string data qsj, 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 Table II

As shown in column 7 of Table 2, the content of the decimal value of the multi-bit binary data qj, dij is in the range of 4 to 6. The highest decimal value in this range is 6, and the lowest decimal value in this range is 4. The range window is 3. The number of flag bits (that is, "1") in the digital string data qsj and dsij is 4. The number of wildcard characters (namely "X") in the digital string data qsj and dsij is 2. In the digital string data qsj, dsij, the wildcard bit (that is, "X") is piled up after the flag bit (that is, "1"). In the digital string data qsj, dsij, the sum of the number of flag bits (that is, "1") and the number of wildcard bits (that is, "X") is 6.

………………（1）

………………………..（2）

……………………………………..（3） That is to say, flag bits (namely "1") and wildcard bits (namely "X") are arranged according to the rules of the following formulas (1) to (3).

………………(1)

………………………..(2)

…………………………………..(3)

Please refer to FIG. 4, which shows a part of a NAND string STi, which stores one of the digital string data dsij of the storage word group WDi. As shown in FIG. 4, the decimal value of the multi-bit binary data dij is in the range of 3 to 6, and the digital string data dsij is "0XXX111". The digital string data dsij can be sequentially stored in the NAND string STi. The two transistors TR1 and TR2 of the memory cell CL of the NAND string STi are used together to define "1", "0" or "X". For example, when the transistor TR1 is programmed to a low voltage level and the transistor TR2 is programmed to a high voltage level, the content of the memory cell CL is defined as “0”. When the transistor TR1 is programmed to a high voltage level and the transistor TR2 is programmed to a low voltage level, the content of the memory cell CL is defined as “1”. When the transistor TR1 is programmed to a low voltage level and the transistor TR2 is programmed to a low voltage level, the content of the memory cell CL is defined as “X”. In other embodiments, other encoding methods may also be used to define "1", "0" and "X".

Please refer to FIG. 5, which illustrates a memory array 120 according to an embodiment. Several NAND strings STi can be arranged in the memory array 120 as a database for synchronous searching. The input search word WQ input to word line WL will be compared with all storage words WDi of these NAND strings. That is to say, multiple data can be compared at the same time at one time, so as to achieve ultra-high-speed parallel search function.

Please refer to FIG. 6, which shows the digital string data dsij stacked in the same NAND string STi. If the memory array 120 has a sufficient number of word lines WL, the digital string data dsij of the storage word group WDi can be stacked in the same NAND string STi.

Please refer to FIG. 7, which shows a memory array 120 based on stacked digit string data dsij. The NAND string STi of the stacked digital string data dsij can be arranged in the memory array 120 as a database for synchronous searching. The digital string data qsj of the input search word WQ is input to the word line WL, and compared with the digital string data dsij of all the stored word WDi. That is to say, multiple data can be compared at the same time at one time, so as to achieve ultra-high-speed parallel search function.

Please refer to FIG. 8, which shows that the storage word WDi is divided into several parts. If the storage word WDi is longer than one NAND string STi, the storage word WDi can be divided into several parts and stored in multiple NAND strings STi. The digital string data qsj is then input to the corresponding part. Multiple comparison results RSij of multiple parts can be integrated through AND operation to obtain one comparison result RSi.

Please refer to Figures 9-14, which illustrate the comparison procedure of the digital string data qsj and the digital string data dsij. As shown in FIG. 9, the digit string data qsj is 5, and the digit string data dsij is 5. The digital string data qsj is equal to the digital string data dsij, so the comparison result RSij is a matching signal, for example, "1".

As shown in FIG. 10, the digit string data qsj is 2, and the digit string data dsij is 4. The digital string data qsj does not overlap with the digital string data dsij, so the comparison result RSij is a mismatch signal, for example, "0".

As shown in Fig. 11, the digit string data qsj is 2-4, and the digit string data dsij is 5-6. The digital string data qsj does not overlap with the digital string data dsij, so the comparison result RSij is a mismatch signal, for example, "0".

As shown in FIG. 12, the digit string data qsj is 4, and the digit string data dsij is 3-6. The digital string data qsj is overlapped with the digital string data dsij, so the comparison result RSij is a matching signal, for example, "1".

As shown in FIG. 13, the digit string data qsj is 2-4, and the digit string data dsij is 4. The digital string data qsj is overlapped with the digital string data dsij, so the comparison result RSij is a matching signal, for example, "1".

As shown in FIG. 14, the digit string data qsj is 2-4, and the digit string data dsij is 4-6. The digital string data qsj is overlapped with the digital string data dsij, so the comparison result RSij is a matching signal, for example, "1".

As described above, a multi-stage search method for MCAM 100 is provided. Please refer to FIG. 15 , which shows a flow chart of the multi-stage search method of the MCAM 100 according to an embodiment. In step S210, at least one storage word WDi is stored in at least one NAND string STi. Next, in step S220, the input search word WQ is input into the NAND string STi. Then, in step S230, the comparison result RSi is output. When the digital string data qsj of the input search word WQ overlaps the digital string data dsij of the stored word WDi, the comparison result RSi is a matching signal, for example, "1". When the digital string data qsj of the input search word WQ does not overlap with the digital string data dsij of the stored word WDi, the comparison result RSi is a mismatch signal, such as "0".

According to the above-mentioned embodiment, the flag bit (ie "1") and the wildcard bit (ie "X") can be used to define the content of the digital string data qsj, dsij. In an embodiment, the flag bit can also be "0". Please refer to Table 3, which illustrates the conversion from multi-bit binary data qj, dij to digital string data qsj, dsij. In the example in Table 3, the content of the multi-bit binary data qj, dij is an exact value, and the number of flag bits (ie "0") of the digital string data qsj, dsij is this exact value. Multi-bit binary data qj, dij decimal value Digital string data qsj, 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 Table three

In the above embodiment, the flag bits (ie "1" or "0") of the digital string data qsj, dsij are accumulated on the right side of the digital string data qsj, dsij. In other embodiments, the flag bits (ie, "1" or "0") of the digital string data qsj, dsij can be stacked on the left side of the digital string data qsj, dsij, or stacked in a predetermined order. Please refer to Table 4, the flag bits (that is, "1") of the digital string data qsj, dsij are accumulated on the left side of the digital string data qsj, dsij. Multi-bit binary data qj, dij decimal value Digital string data qsj, 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 Table four

Please refer to Table 5, the flag bits (namely "1") of the digital string data qsj and dsij are piled up according to a predetermined rule. For example, flag bits (namely "1") are alternately arranged on the left and right of the digital string data qsj, dsij.

According to the above various embodiments, by converting multi-bit binary data into digital string data, the data can be defined into various ranges for searching and comparison. In addition, multiple data can be compared at the same time, so as to achieve ultra-high-speed parallel search function. For example, a NAND chip has a sensing capability of 16KB (=128kb), and the MCAM 100 can perform a comparison procedure of 128k strings at the same time.

To sum up, although the present disclosure has been disclosed above with embodiments, it is not intended to limit the present disclosure. Those with ordinary knowledge in the technical field to which this disclosure belongs may make various changes and modifications without departing from the spirit and scope of this disclosure. Therefore, the scope of protection of this disclosure should be defined by the scope of the appended patent application.

100: Multilevel Content Addressable Memory (MCAM) 110: input encoder 120: memory array 130: output encoder CL: memory cell dij: multi-bit binary data dsij: digital string data qj: multi-bit binary data qsj: digital string data RSi, RSij: comparison results S110, S120, S130, S210, S220, S230: steps STi: NAND string TR1, TR2: Transistor WDi: storage word group WL: character line WQ: Enter a search word

FIG. 1 illustrates a multilevel content addressable memory (MCAM) according to an embodiment. Figure 2 illustrates the content of entering a search word and storing a word. Fig. 3 shows the flow chart of the multi-level encoding method for storing words or inputting search words in MCAM. FIG. 4 shows a portion of a NAND string storing one of the digit string data of the storage word. FIG. 5 illustrates a memory array according to one embodiment. Figure 6 shows digital string data stacked on the same NAND string. Figure 7 shows a memory array based on stacked bit string data. Figure 8 shows that the storage word is divided into several parts. Figures 9 to 14 exemplify the comparison procedure between digital string data and digital string data. FIG. 15 shows a flowchart of a multi-stage search method for MCAM according to an embodiment.

dij: multi-bit binary data

dsij: digital string data

qj: multi-bit binary data

qsj: digital string data

WDi: store words

WQ: Enter a search word

Claims (10)

A multilevel encoding method for a stored word of a multilevel content addressable memory (MCAM) or an input search word (input search word), comprising: Obtain one of the highest decimal values of a multilevel-bit binary data; Set a length of digital string data to be the highest decimal value of the multi-bit binary data; converting the multi-bit binary data into the digital string data, wherein if one of the contents of the multi-bit binary data is an exact value, the number of an indicating bit of the digital string data is the exact value. The multi-level encoding method as described in Claim 1, wherein the flag bits of the digital string data are accumulated on the right or left side of the digital string data. The multi-level encoding method as claimed in claim 1, wherein the flag bits of the digital string data are stacked according to a predetermined order. The multi-level encoding method as described in Claim 1, wherein if the content of the multi-bit binary data is in a range from a low decimal value to a high decimal value, the flag bit of the digital string data The number of elements is the low decimal value, and the sum of the number of the flag bits of the digital string data and the number of wildcard bits of the digital string data is the high decimal value. The multi-level encoding method as described in claim 4, wherein if the content of the multi-bit binary data is within the range, the wildcard bit is piled up after the flag bit. A multilevel search method for multilevel content addressable memory (MCAM), including: storing a plurality of storage words in a plurality of NAND strings; Inputting an input search word into the NAND strings, wherein the storage words and the input search word are each converted from a multi-bit binary data to a digital string data, if the multi-bit binary data one of the contents is an exact value, the number of flag bits of the digital string data is the exact value; and Outputting a comparison result, wherein if the digital string data of the input search word overlaps with the digital string data of one of the stored word groups, the comparison result is a matching signal. The multi-level search method as described in Claim 6, wherein the flag bits of the digital string data are stacked on the right or left side of the digital string data, or stacked according to a predetermined order. The multi-level search method as described in claim 6, wherein if the content of the multi-bit binary data is in a range from a low decimal value to a high decimal value, the flag bit of the digital string data The number of elements is the low decimal value, and the sum of the number of the flag bits of the digital string data and the number of wildcard bits of the digital string data is the high decimal value. The multi-level search method as described in claim 8, wherein if the content of the multi-bit binary data is within the range, the wildcard bit is piled up after the flag bit. A multilevel content addressable memory (multilevel content addressable memory, MCAM), including: an input encoder for receiving an input search word; A memory array including a plurality of NAND strings, each of the NAND strings is used to store a storage word, wherein each of the storage word and the input search word are each converted from a multi-bit binary data to a digital word string data, if the content of one of the multi-bit binary data is an exact value, then the number of flag bits of the digital string data is the exact value; and An output decoder is used to receive a plurality of comparison results from the NAND strings.

Images