Use of bloom filter and improved program algorithm for increased data protection in CAM NAND memory

• US 8,780,635 B2
• Filed: 08/01/2013
• Issued: 07/15/2014
• Est. Priority Date: 11/09/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Li, Yan, Sprouse, Steven T.
• Primary Examiner(s): Byrne, Harry W
• Application Number:
  US13/957,248
• Publication Number:
  US 20140136764A1
• Time in Patent Office: 348 Days
• Field of Search: 36518501-18533
• US Class Current: 365/185.17
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G11C 11/5642 Sensing or reading circuits; Data output circuits
• 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/08 Address circuits; Decoders; Word-line control circuits
• CPC Class Codes: G11C 16/22 Safety or protection circuits preventing unauthorised or accidental access to memory cells
• CPC Class Codes: G11C 16/3459 Circuits or methods to verify correct programming of nonvolatile memory cells
• CPC Class Codes: G11C 2213/75 Array having a NAND structure comprising, for example, memory cells in series or memory elements in series, a memory element being a memory cell in parallel with an access transistor

Abstract

Various techniques for extending the capabilities of CAM NAND type memories are discussed. Multi-block or even full chip search operations can be performed. In addition to the inherent AND property of NAND strings, the memory array has an inherent OR property between NAND string from different blocks along the same bit line that can be exploited through multi-block CAM-type operations. To reduce data-dependent word line to word line effects, in multiple data dependent sensing operations, the sensing can be broken up into sub-operations that avoid data dependent values on adjacent word lines. To improve data protection, subsequent to writing a memory block with indices, the word lines are read back and compared bit-by-bit with their intended values and the results are accumulated to determine whether any of indices include error. A bloom filter can also be used as an initial check during data search operations in order to provide increased data protection.

Claims

1. A method of operating a memory system including a memory circuit having an array of non-volatile formed according to a NAND type of architecture, the method comprising:

storing each of a first plurality of data patterns along one of a corresponding first plurality of NAND strings of the memory array;

storing a first bloom filter corresponding to first plurality of data patterns on the memory circuit;

storing an ECC protected copy of each of the first plurality of data patterns on the memory circuit; and

subsequently performing a search operation, the search operation including;

receiving a search pattern;

performing a comparison of the search pattern against the first bloom filter;

in response to a positive result from the comparison of the search pattern against the first bloom filter, performing a determination of which of the first plurality of NAND strings conduct in response to the memory cells thereof being biased according to the search pattern; and

in response to a negative result from the determination, searching the copies of the first plurality of data patterns for a match with the search pattern.

2. The method of claim 1, further comprising prior to storing the first plurality of data patterns:

receiving the first plurality of data patterns from a host device to which the memory system is connected;

subsequently storing the first plurality of data patterns in a RAM memory of the memory system; and

on the memory system, subsequently arranging the first plurality of data patterns stored in the RAM memory into pages of data so that when written into first array, the first plurality data patterns arranged to orientated along NAND strings of the first array.

3. The method of claim 2, further comprising:

prior to storing the first bloom filter and subsequent to receiving the first plurality of data patterns from the host device, generating the first bloom filter on the memory system from the first plurality of data patterns.

4. The method of claim 2, further comprising:

prior to storing the ECC protected copies of the first plurality of data patterns and subsequent to receiving the first plurality of data patterns from the host device, generating on the memory system the ECC protected copies of the first plurality of data patterns.

5. The method of claim 1, wherein the first bloom filter is stored oriented along a bit line of the memory array.

6. The method of claim 1, wherein the first bloom filter is stored oriented along a word line of the memory array.

7. The method of claim 6, wherein the first bloom filter is stored with ECC protection.

8. The method of claim 7, further generating the first bloom filter and the ECC protection therefor on the memory system.

9. The memory system of claim 1, wherein the ECC protected copies of the first plurality of data patterns are stored with metadata on the memory system.

10. The memory system of claim 1, wherein the memory array is formed of a plurality of blocks and the first plurality of NAND strings correspond to a block of the memory array.

11. The memory system of claim 1, wherein the memory array is formed of a plurality of blocks, and the first bloom filter is one of a plurality of bloom filters stored in a block of the memory used for the storage of bloom filters corresponding to a respective plurality of data patterns.

12. The memory system of claim 1, further comprising:

in response to finding a match for the search pattern among the copies of the first plurality of data patterns, subsequently writing a copy of the matched data pattern along a NAND string of the memory array.

13. The memory system of claim 1, further comprising:

updating the first bloom filter to reflect the writing of a copy of the matched data pattern.

14. A method of operating a memory circuit including an array of non-volatile memory cells having a NAND type of architecture, comprising:

receiving one or more indices;

writing the one or more indices along a corresponding one or more NAND strings of a first block of the memory array;

subsequently individually reading back a plurality of word lines of the array to determine the value of the corresponding bit stored therealong for each of the indices;

for each of the word lines read back, performing a comparison of the value of the corresponding bit stored therealong with the value of the corresponding bit as received for each of the indices and, based upon the comparisons, determining whether any of the bits as read back contain error; and

for each NAND string, individually accumulating the error determined based upon the comparisons for the plurality of word lines to determine whether the bits of the index stored along the corresponding NAND string contain one or more errors.

15. The method of claim 14, further comprising:

in response to determining a first index as stored along a NAND string contains error, subsequently re-writing the first index along a NAND string of a second block of the memory array.

16. The method of claim 15, further comprising:

updating meta-data associated with the indices to reflect said re-writing of the first index.

17. The method of claim 16, further comprising:

writing the updated meta-data to the memory array.

18. The method of claim 17, wherein the updated meta-data is ECC protected.

19. The method of claim 15, further comprising:

marking the NAND string with the first index determined to contain error as obsolete.

20. The method of claim 19, wherein said marking as obsolete includes programming a bit on the NAND string along a word line used to indicate obsolete indices.

21. The method of claim 14, wherein the one or more indices are received by the memory circuit formed into a plurality of pages and the writing of the indices comprises writing each of the pages along one of the plurality of word lines.

22. The method of claim 21, further comprising:

subsequent to writing the one or more indices and prior to performing the comparison for a given word line, receiving a copy of the page written to the given word line for use in said comparison for the given word line.

23. The method of claim 14, further including:

subsequently performing a scrub operation on the indices.

24. The method of claim 23, wherein the scrub operation includes:

performing a first reading of back a plurality of word lines of the array to determine the value of the corresponding bit stored therealong for each of the indices;

performing a second reading of back a plurality of word lines of the array to determine the value of the corresponding bit stored therealong for each of the indices, where the voltage level applied to the word lines in the second reading back is offset by a margin relative to the first reading back; and

for each of the word lines read back, performing a comparison of the results of the of the first and second reading backs of the corresponding bit stored therealong for each of the indices to determine whether any of the indices are corrupted.

25. The method of claim 24, further comprising:

in response to determining a first index as stored along a NAND string contains error, subsequently re-writing the first index along a NAND string of a second block of the memory array.

26. The method of claim 25, further comprising:

updating meta-data associated with the indices to reflect said re-writing of the first index.

27. The method of claim 26, further comprising:

writing the updated meta-data to the memory array.