Statistical distribution based variable-bit error correction coding

• US 8,862,967 B2
• Filed: 04/19/2012
• Issued: 10/14/2014
• Est. Priority Date: 03/15/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Pancholi, Deepak, D'Abreu, Manuel Antonio, Skala, Stephen, Nair, Radhakrishnan
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US13/450,963
• Publication Number:
  US 20130246878A1
• Time in Patent Office: 908 Days
• Field of Search: 714/779, 714/752, 714/758, 714/760, 714/763, 714/768, 714/773, 714/774, 714/782, 714/784, 714/794, 714/799, 714/803, 714/718
• US Class Current: 714/779
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/21 Non-linear codes, e.g. m-bit data word to n-bit code word [mBnB] conversion with error detection or error correction
• CPC Class Codes: H03M 13/25 Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] modulation codes H03M13/31
• CPC Class Codes: H03M 13/255 with Low Density Parity Check [LDPC] codes
• CPC Class Codes: H03M 13/258 with turbo codes, e.g. Turbo Trellis Coded Modulation [TTCM]
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• CPC Class Codes: H03M 13/6318 using variable length codes
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4031 Fixed length to variable length coding
• CPC Class Codes: H03M 7/405 Tree adaptation
• CPC Class Codes: H03M 7/4093 Variable length to variable length coding
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A method may be performed at a data storage device that includes a memory and a controller. The method includes providing user data to a variable-bit error correction coding (ECC) encoder. The ECC encoder generates a first set of parity bits. A first number of parity bits in the first set of parity bits is determined based on stored counts of read errors. The method also includes storing the user data and the first set of parity bits to a memory of the data storage device.

Claims

1. A method comprising:

in a data storage device that includes a memory, wherein the memory has a three-dimensional (3D) memory configuration, performing;

providing user data to a variable-bit error correction coding (ECC) encoder that generates a first set of parity bits, wherein a first number of parity bits in the first set of parity bits is determined based on stored counts of read errors;

storing the user data, the first set of parity bits, and a second set of parity bits to the memory;

reading the user data and the first set of parity bits from the memory;

initiating a first decode operation using the user data and the first set of parity bits; and

in response to the first decode operation failing, accessing the second set of parity bits to initiate a second decode operation that uses the user data and the second set of parity bits.

2. The method of claim 1, wherein the first number of parity bits is selected to correspond to a first threshold probability of error correction based on the stored counts of read errors, and wherein a second number of parity bits in the second set of parity bits is selected to correspond to a second threshold probability of error correction that is different than the first threshold probability of error correction.

3. The method of claim 2, wherein the first threshold probability corresponds to an approximately 95 percent probability of successful error correction using the first number of parity bits, and wherein the second threshold probability corresponds to between a 99 percent probability and a 100 percent probability of successful error correction using the second number of parity bits.

4. The method of claim 1, wherein a second number of parity bits in the second set is greater than the first number of parity bits.

5. The method of claim 4, wherein the second set of parity bits is generated by the variable-bit ECC encoder, and further comprising:

receiving a first indication of the first number of parity bits at the variable-bit ECC encoder, wherein the first set of parity bits is generated based on the first indication of the first number of parity bits; and

receiving a second indication of the second number of parity bits at the variable-bit ECC encoder, wherein the second set of parity bits is generated based on the second indication of the second number of parity bits.

6. The method of claim 4, wherein the second set of parity bits is generated by a second ECC encoder that is configured to encode data at a non-variable encoding rate, and wherein the variable-bit ECC encoder generates the first set of parity bits in parallel with the second ECC encoder generating the second set of parity bits.

7. The method of claim 4, wherein the second set of parity bits corresponds to a larger correction capacity than the first set of parity bits.

8. The method of claim 1, wherein the second set of parity bits is stored to the memory while the memory stores the user data and the first set of parity bits.

9. The method of claim 1, further comprising updating the stored counts of read errors each time data is read from the memory and a corresponding error count is determined.

10. The method of claim 1, wherein the stored counts of read errors are initialized by retrieving preloaded data written to the memory prior to a first storage of user-provided data to the memory.

11. The method of claim 1, wherein the stored counts of read errors are initialized by:

encoding data to be stored to the memory using a largest number of parity bits of the variable-bit ECC encoder;

upon reading the data from the memory, storing counts of read errors detected during ECC decoding using the largest number of parity bits; and

in response to storing a first predetermined number of the counts of read errors, determining the first number of parity bits.

12. The method of claim 11, wherein the encoded data includes test data generated by a controller of the data storage device.

13. The method of claim 11, wherein the encoded data includes user-provided data.

14. A data storage device comprising:

a memory, wherein the memory has a three-dimensional (3D) memory configuration; and

a controller coupled to the memory, wherein the controller is configured to provide user data to a variable-bit error correction coding (ECC) encoder to generate a first set of parity bits, wherein the controller is further configured to store the user data, the first set of parity bits, and a second set of parity bits to the memory, wherein a first number of parity bits in the first set of parity bits is determined based on stored counts of read errors, and wherein the controller is further configured to read the user data and the first set of parity bits from the memory, to initiate a first decode operation using the user data and the first set of parity bits, and to access, in response to the first decode operation failing, the second set of parity bits to initiate a second decode operation that uses the user data and the second set of parity bits.

15. The data storage device of claim 14, wherein the first number of parity bits is selected in response to determining that the first number of parity bits corresponds to a fewest number of parity bits that enables a threshold probability of error correction based on the stored counts of read errors.

16. The data storage device of claim 14, wherein a second number of parity bits in the second set is greater than the first number of parity bits.

17. The data storage device of claim 14, wherein the controller is further configured to initiate an encoding operation at the variable-bit ECC encoder to generate the second set of parity bits.

18. The data storage device of claim 14, further comprising a second ECC encoder, wherein the controller is further configured to initiate an encoding operation at the second ECC encoder to generate the second set of parity bits.

19. The data storage device of claim 14, wherein the controller is further configured to determine a particular count of read errors associated with decoding the user data during the second decode operation and to add the particular count of read errors to the counts of read errors to generate updated counts of read errors.

20. The data storage device of claim 14, wherein the second set of parity bits corresponds to a larger correction capacity than the first set of parity bits.

21. The data storage device of claim 14, wherein the controller is further configured to update the stored counts of read errors each time data is read from the memory and a corresponding error count is determined.

22. The data storage device of claim 14, wherein the stored counts of read errors are initialized by retrieving preloaded data written to the memory prior to a first storage of user-provided data to the memory.

23. The data storage device of claim 14, wherein the controller is further configured to receive a single request for read access to the user data from a host device that is operationally coupled to the controller, and wherein the first decode operation and the second decode operation are initiated by the controller in response to receiving the single request from the host device.