Data encoder and decoder using memory-specific parity-check matrix

• US 8,954,822 B2
• Filed: 11/16/2012
• Issued: 02/10/2015
• Est. Priority Date: 11/18/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Frayer, Jack Edward, Olbrich, Aaron K.
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US13/679,970
• Publication Number:
  US 20130145231A1
• Time in Patent Office: 816 Days
• Field of Search: 714/763, 714/755, 714/780, 714/758
• US Class Current: 714/763
• 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/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2948 Iterative decoding H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]

Abstract

An error control system uses an error control code that corresponds to an error density location profile of a storage medium. The system includes an encoder configured to produce one or more codewords from data using an error control code generator matrix corresponding to the error density location profile of the storage medium. The system also includes a decoder configured to produce decoded data from one or more codewords using an error control code parity-check matrix corresponding to the error density location profile of the storage medium, where columns of the parity-check matrix are associated with corresponding data bits of the storage medium, rows of the parity-check matrix are associated with check bits, and each matrix element of the parity-check matrix having a predefined value indicates a connection between a particular data bit and a particular check bit.

Claims

1. An error control system based on an error control code corresponding to an error density location profile of a storage medium, the system comprising:

an encoder configured to produce one or more codewords from data using an error control code generator matrix corresponding to the error density location profile of the storage medium; and

a decoder configured to produce decoded data from one or more codewords using an error control code parity-check matrix corresponding to the error density location profile of the storage medium, wherein columns of the parity-check matrix are associated with corresponding data bits of the storage medium, rows of the parity-check matrix are associated with check bits, and each matrix element of the parity-check matrix having a predefined value indicates a connection between a particular data bit and a particular check bit,

wherein

the error density location profile of the storage medium is representative of probabilities of bit errors at corresponding storage locations within the storage medium;

the storage locations of the storage medium include, in accordance with the error density location profile of the storage medium, high-error probability memory locations that meet predefined error probability criteria not satisfied by memory locations of the storage medium other than the high-error probability memory locations; and

the check bits of the parity-check matrix include high-connection check bits and other check bits, and the parity-check matrix has element values indicating that;

the high-connection check bits are connected to more memory locations of the storage medium than the other check bits, on average, and

the other check bits are connected to fewer high-error probability memory locations, on average, than the high-connection check bits.

2. The error control system of claim 1, wherein the error control code utilized by the encoder and decoder is a low density parity check (LDPC) code.

3. The error control system of claim 1, wherein the parity-check matrix is irregular.

4. The error control system of claim 1, wherein the high-connection check bits each have more than a threshold number of connections, and the other check bits have less than the threshold number of connections on average.

5. The error control system of claim 4, wherein the threshold number of connections is associated with a convergence speed value of the decoder in a low defect environment.

6. The error control system of claim 1, wherein the high-connection check bits are associated with storage locations on initial and ending word lines of a storage medium block in the storage medium.

7. The error control system of claim 1, wherein the high-connection check bits are associated with a set of storage locations located farthest from sense amplifiers of the storage medium.

8. An error control system based on an error control code corresponding to an error density location profile of a storage medium, the system comprising:

an encoder configured to produce one or more codewords from data using an error control code generator matrix corresponding to the error density location profile of the storage medium; and

a decoder configured to produce decoded data from one or more codewords using an error control code parity-check matrix corresponding to the error density location profile of the storage medium, wherein columns of the parity-check matrix are associated with corresponding data bits of the storage medium, rows of the parity-check matrix are associated with check bits, and each matrix element of the parity-check matrix having a predefined value indicates a connection between a particular data bit and a particular check bit,

wherein

the error density location profile of the storage medium is representative of probabilities of bit errors at corresponding storage locations within the storage medium;

the storage locations of the storage medium include, in accordance with the error density location profile of the storage medium, high-error probability memory locations that meet predefined error probability criteria not satisfied by memory locations of the storage medium other than the high-error probability memory locations; and

the check bits of the parity-check matrix include low-connection check bits and other check bits, and the parity-check matrix has element values indicating that;

the low-connection check bits are connected to fewer locations of the storage medium than the other check bits, on average, and are connected to more high-error probability memory locations, on average, than the other check bits.

9. The error control system of claim 8, wherein the low-connection check bits each have less than a threshold number of connections, and the other check bits have more than the threshold number of connections on average.

10. The error control system of claim 9, wherein the threshold number of connections is associated with a convergence speed value of the decoder in a high defect environment.

11. The error control system of claim 8, wherein the low-connection check bits are associated with storage locations on initial and ending word lines of a storage medium block in the storage medium.

12. The error control system of claim 8, wherein the low-connection check bits are associated with a set of storage locations located farthest from sense amplifiers of the storage medium.

13. An error control system operable to adaptively encode data into codewords and decode data from codewords, the system comprising:

an encoder configured to produce one or more codewords from data using an adjustable generator matrix;

a decoder configured to produce decoded data from one or more codewords using an adjustable parity-check matrix;

a code adaptation module configured to produce adjustments for the adjustable generator matrix and the adjustable parity-check matrix based on error location statistics; and

an error tracking module configured to produce error location statistics by comparing received codewords with check-words, wherein the decoder decodes the received codewords to produce received data, and the encoder generates the check-words from received data,

wherein

the adjustable generator matrix and the adjustable parity-check matrix each include elements associated with one or more storage locations, and

one or more error-prone storage locations are mapped to check bits of the adjustable parity-check matrix satisfying a threshold number of interconnections, wherein the error-prone locations comprise storage medium locations having error statistics satisfying a threshold error characterization.

14. The error control system of claim 13, wherein the decoder comprises a low density parity check (LDPC) code decoder.

15. The error control system of claim 13, wherein the adjustable parity-check matrix is irregular.

16. The error control system of claim 13, further comprising a storage medium interface operable to retrieve one or more codewords from a storage medium, and wherein the error location statistics are associated with storage medium locations.

17. The error control system of claim 13, wherein the threshold number of interconnections is one of a minimum and a maximum.

18. The error control system of claim 13, wherein one or more non-error-prone storage locations are mapped to check bits of the adjustable parity-check matrix satisfying a threshold number of interconnections, wherein the non-error-prone locations comprise storage medium locations having error statistics satisfying a threshold error characterization.

19. A method for adaptively encoding data into codewords and decoding data from codewords, comprising:

producing one or more codewords from data using an error control code generator matrix corresponding to an error density location profile of a storage medium; and

producing decoded data from one or more codewords using an error control code parity-check matrix corresponding to the error density location profile of the storage medium, wherein columns of the parity-check matrix are associated with corresponding data bits of the storage medium, rows of the parity-check matrix are associated with check bits, and each matrix element of the parity-check matrix having a predefined value indicates a connection between a particular data bit and a particular check bit,

wherein

the error density location profile of the storage medium is representative of probabilities of bit errors at corresponding storage locations within the storage medium;

the storage locations of the storage medium include, in accordance with the error density location profile of the storage medium, high-error probability memory locations that meet predefined error probability criteria not satisfied by memory locations of the storage medium other than the high-error probability memory locations; and

the check bits of the parity-check matrix include high-connection check bits and other check bits, and the parity-check matrix has element values indicating that;

the high-connection check bits are connected to more memory locations of the storage medium than the other check bits, on average, and

the other check bits are connected to fewer high-error probability memory locations, on average, than the high-connection check bits.

20. The method of claim 19, wherein the high-connection check bits each have more than a threshold number of connections, and the other check bits have less than the threshold number of connections on average.

21. The method of claim 20, wherein the threshold number of connections is associated with a convergence speed value of the decoder in a low defect environment.

22. A method for adaptively encoding data into codewords and decoding data from codewords, comprising:

producing one or more codewords from data using an error control code generator matrix corresponding to an error density location profile of a storage medium; and

producing decoded data from one or more codewords using an error control code parity-check matrix corresponding to the error density location profile of the storage medium, wherein columns of the parity-check matrix are associated with corresponding data bits of the storage medium, rows of the parity-check matrix are associated with check bits, and each matrix element of the parity-check matrix having a predefined value indicates a connection between a particular data bit and a particular check bit,

wherein

the error density location profile of the storage medium is representative of probabilities of bit errors at corresponding storage locations within the storage medium;

the storage locations of the storage medium include, in accordance with the error density location profile of the storage medium, high-error probability memory locations that meet predefined error probability criteria not satisfied by memory locations of the storage medium other than the high-error probability memory locations; and

the check bits of the parity-check matrix include low-connection check bits and other check bits, and the parity-check matrix has element values indicating that;

the low-connection check bits are connected to fewer locations of the storage medium than the other check bits, on average, and are connected to more high-error probability memory locations, on average, than the other check bits.

23. The error control system of claim 22, wherein the low-connection check bits each have less than a threshold number of connections, and the other check bits have more than the threshold number of connections on average.

24. The error control system of claim 23, wherein the threshold number of connections is associated with a convergence speed value of the decoder in a high defect environment.

25. A method for adaptively encoding data into codewords and decoding data from codewords, comprising:

producing one or more codewords from data using an adjustable generator matrix;

producing decoded data from one or more codewords using an adjustable parity-check matrix; and

producing adjustments for the adjustable generator matrix and the adjustable parity-check matrix based on error location statistics, wherein the error location statistics are produced by comparing received codewords with check-words, wherein the received codewords are decoded to produce received data, and the check-words are generated from received data, wherein

the adjustable generator matrix and the adjustable parity-check matrix each include elements associated with one or more storage locations, and

one or more error-prone storage locations are mapped to check bits of the adjustable parity-check matrix satisfying a threshold number of interconnections, wherein the error-prone locations comprise storage medium locations having error statistics satisfying a threshold error characterization.