Methods and apparatus for pattern matching

• US 9,436,402 B1
• Filed: 04/17/2012
• Issued: 09/06/2016
• Est. Priority Date: 04/18/2011
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: De Santis, Luca, Marotta, Giulio G., Tiburzi, Marco-Domenico, Vali, Tommaso, Roohparvar, Frankie F., Macerola, Agostino
• Primary Examiner(s): Yi, David X
• Assistant Examiner(s): Rankin, Candice
• Application Number:
  US13/449,082
• Time in Patent Office: 1,603 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/608 Details relating to cache mapping
• CPC Class Codes: G06F 3/0628 making use of a particular technique
• CPC Class Codes: G06F 7/20 Comparing separate sets of record carriers arranged in the same sequence to determine whether at least some of the data in one set is identical with that in the other set or sets
• CPC Class Codes: G11C 15/046 using non-volatile storage elements
• CPC Class Codes: G11C 16/0483 comprising cells having several storage transistors connected in series
• CPC Class Codes: G11C 16/06 Auxiliary circuits, e.g. for writing into memory
• CPC Class Codes: G11C 29/50004 of threshold voltage
• CPC Class Codes: G11C 29/50016 of retention
• CPC Class Codes: G11C 7/1006 Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor

Abstract

Methods and apparatus for pattern matching are disclosed. In at least one embodiment, pattern checking is accomplished by reading a page of memory, and comparing the read page with the pattern to be searched in a logic operation. In at least one other embodiment, a pattern to be searched is stored in registers where each bit of the pattern is stored using two register entries and each bit of the array data is stored using two cells of the array.

Claims

1. A method of pattern matching in a memory, comprising:

providing a pattern to be searched in the memory; and

pattern checking for the pattern to be searched in the memory, wherein pattern checking further comprises;

reading at least a portion of a page from the memory;

comparing the at least a portion of the read page and the pattern to be searched;

determining whether a number of bit errors between the at least a portion of the read page and the pattern to be searched is less than or equal to a particular number of bit errors, wherein the particular number of bit errors is greater than or equal to one; and

deeming the comparison a match when the number of bit errors is less than or equal to the particular number of bit errors;

wherein comparing the at least a portion of the read page and the pattern to be searched comprises combining the at least a portion of the read page and the pattern to be searched with an XNOR operation.

2. The method of claim 1, wherein reading at least a portion of a page from the memory comprises reading the at least a portion of the page into a first cache of a page buffer of the memory, and wherein the pattern to be searched is loaded into a second cache of the page buffer of the memory.

3. The method of claim 2, and further comprising detecting when all the data in the first data cache are is except for a determined number N of them.

4. The method of claim 1, and further comprising:

setting a status bit to indicate whether the pattern to be searched has been found.

5. The method of claim 1, and further comprising:

storing an address of a location within the memory where a match of the pattern to be searched begins.

6. The method of claim 1, and further comprising:

storing the number of bit errors.

7. The method of claim 1, wherein reading at least a portion of a page comprises:

setting a starting page address and ending page address; and

reading the page at the starting page address into a first cache.

8. The method of claim 7, wherein pattern checking further comprises:

combining the first cache and a second cache having the pattern to be searched with an XNOR operation; and

determining if a match between the first cache and the second cache has occurred.

9. The method of claim 8, wherein determining if a match between the first cache and the second cache has occurred comprises determining whether at least a particular number of logical 1 values are in the XNOR result.

10. The method of claim 8, wherein the results of the XNOR operation are written to the first cache.

11. The method of claim 8, and further comprising:

if a match of the pattern to be searched and data read into the first cache is found, identifying a location of the start of the match; and

if no match of the pattern to be searched and data read into the first cache is found, incrementing the page address; and

repeating reading a page, combining the first cache and the second cache, and determining if a match has occurred until a match is found or an ending page address is reached.

12. The method of claim 1, wherein the pattern to be searched is a full page pattern.

13. The method of claim 1, wherein the pattern to be searched is less than a full page in size.

14. A method of pattern matching in a memory, comprising:

providing a pattern to be searched in the memory; and

pattern checking for the pattern to be searched in the memory, wherein pattern checking further comprises;

reading at least a portion of a page from the memory, wherein reading at least a portion of a page from the memory comprises reading the at least a portion of the page into a first cache of a page buffer of the memory;

comparing the at least a portion of the read page and the pattern to be searched, wherein the pattern to be searched is loaded into a second cache of the page buffer of the memory;

determining whether a number of bit errors between the at least a portion of the read page and the pattern to be searched is less than or equal to a particular number of bit errors, wherein the particular number of bit errors is greater than or equal to one; and

deeming the comparison a match when the number of bit errors is less than or equal to the particular number of bit errors;

wherein determining whether a number of bit error is greater than or equal to the particular number of bit errors comprises;

programming the first data cache to values resulting from an XNOR combination of the first cache with the second cache; and

determining whether the first data cache contains at least a number of logical 1 values equal to the particular number.

15. A method of pattern matching in a memory, comprising:

programming a pattern to be searched into a plurality of registers of the memory, each bit of the pattern associated with two separate register entries;

pattern checking for the pattern to be searched in the memory, wherein each bit of data stored in the memory is stored in two cells of the memory; and

determining an error count for the pattern checking;

wherein determining an error count comprises;

precharging a selected data line of a string of memory cells of the memory array;

sensing on the data line;

if the data line does not discharge, storing an error count value of zero;

if the data line discharges, precharging the data line, applying a reference current to the data line at a first level sufficient to overcome a single bit non-match in the string, and sensing to determine if the data line discharges;

if the data line does not discharge, storing an error count value equal to one; and

if the data line discharges, incrementing the reference current to a next level sufficient to overcome an additional bit non-match in the string, precharging the data line, sensing, and if the data line discharges, repeating until a maximum reference current is reached or the data line stays charged; and

storing an error count based on the reference current at which the data line remains charged.

16. The method of claim 15, wherein determining an error count further comprises:

determining an error count between the pattern to be searched and a portion of data read from the memory.

17. The method of claim 16, wherein pattern checking comprises comparing selected programmed bits of the pattern to data stored in the memory array.

18. The method of claim 17, wherein comparing results in a match when the cells are coupled to a precharged data line which does not discharge.

19. The method of claim 17, wherein comparing results in a non-match when the cells are coupled to a precharged data line which does discharge.

20. The method of claim 16, wherein comparing is performed using data line activation for specific access lines of the memory array.

21. The method of claim 16, wherein each bit of the pattern is programmed into two bits of the register, wherein gate voltages are applied to gates of two respective cells of the memory responsive to the two programmed bits.

22. The method of claim 21, wherein the two cells are adjacent cells in a same string of the memory.

23. The method of claim 21, wherein pattern checking comprises applying the programmed gate voltages of a selected bit of the pattern to be searched to the two respective cells of the stored data.

24. The method of claim 21, wherein a 0 value in the pattern to be searched is coded as a first voltage in the first bit of the register and a second voltage in the second bit of the register;

and wherein a 1 value in the pattern to be searched is coded as the second voltage in the first bit of the register and the first voltage in the second bit of the register.

25. The method of claim 24, wherein a 0 value is coded in stored data as a first threshold voltage on a first cell and a second threshold voltage on a second cell, and a 1 value is coded in stored data as the second threshold voltage on the first cell and the first threshold voltage on the second cell.

26. The method of claim 16, wherein programming the pattern comprises programming a key word.

27. The method of claim 16, wherein determining an error count further comprises, when at least one non-match error between the pattern to be searched and the data stored in a string of the memory is detected, providing a plurality of pulses to a counter, the number of pulses corresponding to the number of errors in the string.

28. The method of claim 27, wherein determining an error count further comprises:

setting an enable signal when at least one non-match error is found in the string, and

incrementing the counter by a number indicated by a number of pulses applied to the counter equal to the count of non-match errors on the string when the enable signal is set.

29. A memory device, comprising:

an array of memory cells;

circuitry configured to perform a method comprising;

loading, into the memory device, a pattern to be searched within data stored in the array of memory cells; and

pattern checking for the pattern to be searched within data stored in the array of memory cells, wherein pattern checking comprises;

reading at least a portion of a page from the array of memory cells;

comparing the at least a portion of the read page and the pattern to be searched;

determining whether a number of bit errors between the at least a portion of the read page and the pattern to be searched is less than or equal to a particular number of bit errors, wherein the particular number of bit errors is greater than or equal to one; and

deeming the comparison a match when the number of bit errors is less than or equal to the particular number of bit errors; and

deeming the comparison a match when the number of bit errors is less than or equal to the particular number of bit errors;

wherein comparing the at least a portion of the read page and the pattern to be searched comprises combining the at least a portion of the read page and the pattern to be searched with an XNOR operation.

30. A memory device, comprising:

an array of memory cells;

circuitry configured to perform a method comprising;

programming a pattern to be searched into a plurality of registers of the memory, such that each bit of the pattern to be searched is stored as two separate register entries;

pattern checking for the pattern to be searched within data stored in the array of memory cells, wherein each bit of data to be searched in the array of memory cells is stored in a respective two memory cells of the array of memory cells; and

determining an error count for the pattern checking;

wherein determining an error count comprises;

precharging a selected data line of a string of memory cells of the memory array;

sensing on the data line;

if the data line does not discharge, storing an error count value of zero;

if the data line discharges, precharging the data line, applying a reference current to the data line at a first level sufficient to overcome a single bit non-match in the string, and sensing to determine if the data line discharges;

if the data line does not discharge, storing an error count value equal to one;

if the data line discharges, incrementing the reference current to a next level sufficient to overcome an additional bit non-match in the string, precharging the data line, sensing, and if the data line discharges, repeating until a maximum reference current is reached or the data line stays charged; and

storing an error count based on the reference current at which the data line remains charged.