Systems and methods for redundantly storing error correction codes in a flash drive with secondary parity information spread out across each page of a group of pages

• US 9,021,336 B1
• Filed: 05/22/2012
• Issued: 04/28/2015
• Est. Priority Date: 05/22/2012
• Status: Active Grant

• Current Assignee: Ip Gem Group, LLC
• Original Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Inventors: Northcott, Philip L.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): DORMAN, CHRISTIAN M
• Application Number:
  US13/477,598
• Time in Patent Office: 1,071 Days
• Field of Search: 714/763, 714/752, 714/773
• US Class Current: 714/773
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD

Abstract

Apparatus and methods provide relatively low uncorrectable bit error rates, low write amplification, long life, fast and efficient retrieval, and efficient storage density such that a solid-state drive (SSD) can be implemented using relatively inexpensive MLC Flash for an enterprise storage application. Both primary parity symbols for primary codewords and secondary parity symbols for secondary codewords are generated. The secondary parity symbols are spread out across each page of a group of pages.

Claims

1. A method of programming data to a plurality of flash memory devices, the method comprising:

receiving data to be programmed;

arranging the received data for distribution among a page stripe such that sequentially received data is to be programmed among the page stripe, wherein the page stripe comprises two or more flash memory pages or two or more integer fractions of flash memory pages;

error correction encoding data to be stored within a particular page or integer fraction to generate primary parity symbols for primary codewords;

generating information portions of secondary codewords by selecting portions of primary codewords, wherein secondary codewords are at least partially orthogonal to primary codewords;

error correction encoding the information portions of the secondary codewords to generate secondary parity symbols for the secondary codewords;

arranging the secondary parity symbols for distribution within the page stripe such that the secondary parity symbols of each secondary codeword are spread out across each page of the page stripe when programmed; and

programming the page stripe with the arranged received data, the primary parity symbols, and the arranged secondary parity symbols;

wherein at least error correction encoding data, generating information portions, and error correction encoding the information portions are performed by an integrated circuit;

wherein at least error correction encoding data, generating information portions, and error correction encoding the information portions are performed concurrently with write operations for an end user.

2. The method of claim 1, further comprising arranging the sequentially received data such that the sequentially received data is broken up and striped across the pages of the page stripe.

3. The method of claim 1, wherein each page of the page stripe is from a different integrated circuit die or plane.

4. The method of claim 1, further comprising:

determining a gear associated with the page stripe; and

retrieving ECC parameters corresponding to the gear for error correction encoding of primary codewords and secondary codewords.

5. The method of claim 1, further comprising:

error correction encoding the secondary parity symbols to be stored within a particular page to generate primary parity on secondary parity; and

programming the page stripe with the primary parity on secondary parity.

6. The method of claim 1, wherein the flash memory devices comprise multi-level memory cells.

7. The method of claim 1, further comprising scrambling the received data with a pseudo-random sequence prior to encoding.

8. The method of claim 1, wherein a number of secondary codewords in the page stripe is prime relative to a total length of a primary codeword.

9. The method of claim 1, further comprising rotating an order of bit assignments to secondary codewords by one position every Cs bits, wherein Cs comprises a number of secondary codewords in the page stripe.

10. The method of claim 1, further comprising rotating an order of n-bit word assignments to secondary codewords by one position every (Cs times n) bits, wherein Cs comprises a number of secondary codewords in the page stripe, and n is one or more.

11. The method of claim 10, wherein n is 8.

12. The method of claim 1, wherein each primary codeword is programmed within a single.

13. The method of claim 1, further comprising calculating a fingerprint for a page based at least partly on a physical address of the page, and storing the fingerprint in the page.

14. The method of claim 13, wherein the fingerprint comprises a hash code generated from at least a portion of the physical address of the page.

15. The method of claim 1, wherein the first error correction code and the second error correction code are generated by calculation of a Bose, Chaudhuri, and Hocquenghem (BCH) code.

16. The method of claim 1, further comprising:

error correction encoding, with an erasure code, data stored and/or to be stored within a page grid to generate tertiary parity symbols for tertiary codewords, wherein the erasure code is of sufficient strength to recover a missing page of the page grid; and

arranging the tertiary parity symbols for distribution across a last page stripe of the page grid to be programmed such that the tertiary parity symbols are broken up and spread for programming across the last page stripe;

wherein programming the page stripe for the last page stripe further comprises programming with the arranged tertiary parity symbols.

17. The method of claim 16, further comprising arranging two or more page stripes into a page grid, wherein each page of the page grid is from a different integrated circuit die or plane.

18. The method of claim 17, wherein the page grid comprises Wg page stripes, and wherein each of the Wg page stripes comprises Ws pages or Ws integer fractions of pages, wherein the tertiary parity symbols of the erasure code have sufficient strength to recover the missing page of the page grid and Ws−

1/WsWg of the secondary codewords.

19. The method of claim 17, wherein the page grid comprises 4 page stripes, and wherein page stripe comprises 4 pages or 4 integer fractions of pages, wherein the tertiary parity symbols of the erasure code have sufficient strength to recover the missing page of the page grid and 3/16 of the secondary codewords.

20. The method of claim 16, further comprising:

error correction encoding the tertiary parity symbols to be stored within a particular page of the last page stripe to generate primary parity on tertiary parity (PoTP); and

programming the last page stripe with the primary parity on tertiary parity.

21. The method of claim 16, wherein a number of tertiary codewords in the page grid is prime relative to a total length of a primary codeword.

22. The method of claim 16, further comprising rotating an order of bit assignments to tertiary codewords by one position every Wt symbols, wherein Wt comprises a number of tertiary codewords in the page grid, wherein the symbols correspond to erasure code symbols.

23. The method of claim 1, wherein the primary parity symbols have enough strength such that decoding of the primary codewords alone, in the presence of an RBER equal to or less than a predetermined maximum operating BER for the gear, is successful at least 95% of the time.

24. An apparatus comprising:

a first circuit configured to;

receive data to be programmed; and

arrange the received data for distribution among a page stripe such that sequentially received data is to be programmed among the page stripe, wherein the page stripe comprises two or more flash memory pages or two or more integer fractions of flash memory pages;

a second circuit configured to error correction encode data to be stored within a particular page or integer fraction to generate primary parity symbols for primary codewords;

the first circuit further configured to select portions of primary codewords to generate information portions of secondary codewords, wherein secondary codewords are at least partially orthogonal to primary codewords;

the second circuit further configured to error correction encode the information portions of the secondary codewords to generate secondary parity symbols for the secondary codewords;

the first circuit further configured to arrange the secondary parity symbols for distribution among the page stripe such that the secondary parity symbols are spread out across each page of the page stripe when programmed; and

the first circuit further configured to program the page stripe with the arranged received data, the primary parity symbols, and the arranged secondary parity symbols;

wherein the first circuit and the second circuit are configured to error correction encode data, to generate information portions, and to error correction encode the information portions concurrently with write operations for an end user.

25. The apparatus of claim 24, wherein the first circuit is further configured to arrange the sequentially received data such that the sequentially received data is broken up and striped across the pages of the page stripe.

26. The apparatus of claim 24, wherein each page of the page stripe is from a different integrated circuit die or plane.

27. The apparatus of claim 24, wherein the first circuit is further configured to:

determine a gear associated with the page stripe; and

retrieve ECC parameters corresponding to the gear for error correction encoding of primary codewords and secondary codewords.

28. The apparatus of claim 24, wherein:

the second circuit is further configured to error correction encode the secondary parity symbols to be stored within a particular page to generate primary parity on secondary parity; and

the first circuit is further configured to program the page stripe with the primary parity on secondary parity.

29. The apparatus of claim 24, further comprising flash memory devices, wherein the flash memory devices comprise multi-level memory cells, wherein the apparatus comprises a flash drive.

30. The apparatus of claim 24, wherein the first circuit is further configured to scramble the received data with a pseudo-random sequence prior to encoding.

31. The apparatus of claim 24, wherein a number of secondary codewords in the page stripe is prime relative to a total length of a primary codeword.

32. The apparatus of claim 24, wherein the first circuit is further configured to rotate an order of bit assignments to secondary codewords by one position every Cs bits, wherein Cs comprises a number of secondary codewords in the page stripe.

33. The apparatus of claim 24, wherein the first circuit is further configured to rotate an order of n-bit word assignments to secondary codewords by one position every (Cs times n) bits, wherein Cs comprises a number of secondary codewords in the page stripe, and n is one or more.

34. The apparatus of claim 33, wherein n is 8.

35. The apparatus of claim 24, wherein the first circuit is further configured to program each primary codeword within a single page.

36. The apparatus of claim 24, wherein the first circuit is further configured to calculate a fingerprint for a page based at least partly on a physical address of the page, and to store the fingerprint in the page.

37. The apparatus of claim 36, wherein the fingerprint comprises a hash code generated from at least a portion of the physical address of the page.

38. The apparatus of claim 24, wherein the second circuit is configured to generate the first error correction code and the second error correction code by calculation of a Bose, Chaudhuri, and Hocquenghem (BCH) code.

39. The apparatus of claim 24, wherein:

the second circuit is configured to error correction encode, with an erasure code, data stored and/or to be stored within a page grid to generate tertiary parity symbols for tertiary codewords, wherein the erasure code is of sufficient strength to recover a missing page of the page grid; and

the first circuit is configured to arrange the tertiary parity symbols for distribution across a last page stripe of the page grid to be programmed such that the tertiary parity symbols are broken up and spread for programming across the last page stripe;

wherein the first circuit is further configured to program the page stripe for the last page stripe with the arranged tertiary parity symbols.

40. The apparatus of claim 39, wherein the first circuit is further configured to arrange two or more page stripes into a page grid, wherein each page of the page grid is from a different integrated circuit die or plane.

41. The apparatus of claim 40, wherein the page grid comprises Wg page stripes, and wherein each of the Wg page stripes comprises Ws pages or Ws integer fractions of pages, wherein the tertiary parity symbols of the erasure code have sufficient strength to recover the missing page of the page grid and Ws−

1/WsWg of the secondary codewords.

42. The apparatus of claim 40, wherein the page grid comprises 4 page stripes, and wherein page stripe comprises 4 pages or 4 integer fractions of pages, wherein the tertiary parity symbols of the erasure code have sufficient strength to recover the missing page of the page grid and 3/16 of the secondary codewords.

43. The apparatus of claim 39, wherein:

the second circuit is further configured to error correction encode the tertiary parity symbols to be stored within a particular page of the last page stripe to generate primary parity on tertiary parity (PoTP); and

the first circuit is further configured to program the last page stripe with the primary parity on tertiary parity.

44. The apparatus of claim 39, wherein a number of tertiary codewords in the page grid is prime relative to a total length of a primary codeword.

45. The apparatus of claim 39, wherein the first circuit is further configured to rotate an order of bit assignments to tertiary codewords by one position every Wt symbols, wherein Wt comprises a number of tertiary codewords in the page grid, wherein the symbols correspond to erasure code symbols.

46. The apparatus of claim 24, wherein the primary parity symbols have enough strength such that decoding of the primary codewords alone, in the presence of an RBER equal to or less than a predetermined maximum operating BER for the gear, is successful at least 95% of the time.

47. An apparatus for programming data to a plurality of flash memory devices, the apparatus comprising:

a means for receiving data to be programmed;

a means for arranging the received data for distribution among a page stripe such that sequentially received data is to be programmed among the page stripe, wherein the page stripe comprises two or more flash memory pages or two or more integer fractions of flash memory pages;

a means for error correction encoding data to be stored within a particular page or integer fraction to generate primary parity symbols for primary codewords;

a means for generating information portions of secondary codewords by selecting portions of primary codewords, wherein secondary codewords are at least partially orthogonal to primary codewords;

the encoding means further configured to error correction encode the information portions of the secondary codewords to generate secondary parity symbols for the secondary codewords;

the arranging means further configured to arrange the secondary parity symbols for distribution among the page stripe such that the secondary parity symbols are spread out across each page of the page stripe when programmed; and

a means for programming the page stripe with the arranged received data, the primary parity symbols, and the arranged secondary parity symbols;

wherein the arranging means and the error correction means are configured to operate concurrently with write operations for an end user.

48. The apparatus of claim 47, wherein the arranging means is further configured to arrange the sequentially received data such that the sequentially received data is broken up and striped across the pages of the page stripe.

49. The apparatus of claim 47, wherein each page of the page stripe is from a different integrated circuit die or plane.

50. The apparatus of claim 47, further comprising:

a means for determining a gear associated with the page stripe; and

a means for retrieving ECC parameters corresponding to the gear for error correction encoding of primary codewords and secondary codewords.

51. The apparatus of claim 47, wherein:

the error correction encoding means is further configured to error correction encode the secondary parity symbols to be stored within a particular page to generate primary parity on secondary parity, and

the programming means is further configured to program the page stripe with the primary parity on secondary parity.

52. The apparatus of claim 47, wherein the flash memory devices comprise multi-level memory cells.

53. The apparatus of claim 47, further comprising means for scrambling the received data with a pseudo-random sequence prior to encoding.

54. The apparatus of claim 47, wherein a number of secondary codewords in the page stripe is prime relative to a total length of a primary codeword.

55. The apparatus of claim 47, wherein the arranging means is further configured to rotate an order of bit assignments to secondary codewords by one position every Cs bits, wherein Cs comprises a number of secondary codewords in the page stripe.

56. The apparatus of claim 47, wherein the arranging means is further configured to rotate an order of n-bit word assignments to secondary codewords by one position every (Cs times n) bits, wherein Cs comprises a number of secondary codewords in the page stripe, and n is one or more.

57. The apparatus of claim 56, wherein n is 8.

58. The apparatus of claim 47, wherein the programming means is further configured to program each primary codeword within a single page.

59. The apparatus of claim 47, further comprising a means for calculating a fingerprint for a page based at least partly on a physical address of the page, wherein the programming means is further configured to store the fingerprint in the page.

60. The apparatus of claim 59, wherein the fingerprint comprises a hash code generated from at least a portion of the physical address of the page.

61. The apparatus of claim 47, wherein the error correction code encoding means is configured to generate the first error correction code and the second error correction code by calculation of a Bose, Chaudhuri, and Hocquenghem (BCH).

62. The apparatus of claim 47, further comprising:

a second means for error correction encoding, with an erasure code, data stored and/or to be stored within a page grid to generate tertiary parity symbols for tertiary codewords, wherein the erasure code is of sufficient strength to recover a missing page of the page grid;

the arranging means is further configured to arrange the tertiary parity symbols for distribution across a last page stripe of the page grid to be programmed such that the tertiary parity symbols are broken up and spread for programming across the last page stripe;

wherein programming the page stripe for the last page stripe further comprises programming with the arranged tertiary parity symbols.

63. The apparatus of claim 62, wherein the arranging means is further configured to arrange two or more page stripes into a page grid, wherein each page of the page grid is from a different integrated circuit die or plane.

64. The apparatus of claim 63, wherein the page grid comprises Wg page stripes, and wherein each of the Wg page stripes comprises Ws pages or Ws integer fractions of pages, wherein the tertiary parity symbols of the erasure code have sufficient strength to recover the missing page of the page grid and Ws−

1/WsWg of the secondary codewords.

65. The apparatus of claim 63, wherein the page grid comprises 4 page stripes, and wherein page stripe comprises 4 pages or 4 integer fractions of pages, wherein the tertiary parity symbols of the erasure code have sufficient strength to recover the missing page of the page grid and 3/16 of the secondary codewords.

66. The apparatus of claim 62, wherein:

the error correction encoding means is further configured to error correction encode the tertiary parity symbols to be stored within a particular page of the last page stripe to generate primary parity on tertiary parity (PoTP); and

the programming means is further configured to program the last page stripe with the primary parity on tertiary parity.

67. The apparatus of claim 62, wherein a number of tertiary codewords in the page grid is prime relative to a total length of a primary codeword.

68. The apparatus of claim 62, wherein the arranging means is further configured to rotate an order of bit assignments to tertiary codewords by one position every Wt symbols, wherein Wt comprises a number of tertiary codewords in the page grid, wherein the symbols correspond to erasure code symbols.

69. The apparatus of claim 47, wherein the primary parity symbols have enough strength such that decoding of the primary codewords alone, in the presence of an RBER equal to or less than a predetermined maximum operating BER for the gear, is successful at least 95% of the time.