Systems Using Low Density Parity Check Codes For Correcting Errors

• US 20090235142A1
• Filed: 03/11/2008
• Published: 09/17/2009
• Est. Priority Date: 03/11/2008
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Hitachi Global Storage Technologies Netherlands BV (Western Digital Corporation)
• Inventors: Blaum, Mario, Wilson, Bruce Alexander, Djurdjevic, Ivana, Lakovic, Ksenija, Galbraith, Richard Leo, Oenning, Travis Roger
• Granted Patent: US 8,209,578 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: G11B 20/18 Error detection or correction; Testing , e.g. of drop-outs
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms

Abstract

A system corrects errors in a bit stream. The system includes an encoder and a decoder. The encoder encodes the bit stream using a low density parity check code by inserting parity check bits into the bit stream to generate codewords. The decoder decodes the codewords using parity check equations that are based on the low density parity check code. The parity check bits may comprise no more than four percent of the bits in the codewords of the low density parity check code. The low density parity check code can have a minimum separation of at least 7 between any two ones in each row of a parity-check matrix that is based on the low density parity check code. The encoder and the decoder can be defined in hardware using logic circuits that are interconnected to implement a trellis based on the low density parity check code.

Claims

1. A system for correcting errors in a bit stream, the system comprising:

an encoder that encodes the bit stream using a low density parity check code by inserting parity check bits into the bit stream to generate codewords, wherein the parity check bits comprise no more than four percent of the bits in the codewords of the low density parity check code; and

a decoder that decodes the codewords using parity check equations that are based on the low density parity check code.

2. The system defined in claim 1 wherein the system is a hard disk drive, and the bit stream is read from a magnetic disk in the hard disk drive.

3. The system defined in claim 2 wherein the parity check equations do not contain any four cycles.

4. The system defined in claim 2 wherein the low density parity check code has a minimum separation of at least 7 between any two bits in a codeword that are checked by one of the parity check equations to reduce inter-symbol interference between bits checked by the same parity check equation.

5. The system defined in claim 1 wherein the low density parity check code supports a dynamic length for use with multiple sector formats.

6. The system defined in claim 1 wherein the parity check bits are inserted into each of the codewords in pairs, and each of the pairs in a codeword is separated by at least 22 non-parity check bits.

7. A data storage system for correcting errors in a bit stream, the data storage system comprising:

an encoder that encodes the bit stream using a low density parity check code by inserting parity check bits into the bit stream to generate codewords, wherein the bit stream is read from a magnetic data storage medium in the data storage system; and

a decoder that decodes the codewords using a parity-check matrix that is based on the low density parity check code, wherein the low density parity check code has a minimum separation of at least 7 between any two ones in each row of the parity-check matrix to reduce inter-symbol interference between bits checked by each parity check equation that is based on a row of the parity-check matrix.

8. The data storage system defined in claim 7 wherein the data storage system is a hard disk drive, and the magnetic data storage medium is a magnetic disk.

9. The data storage system defined in claim 7 wherein the parity check bits comprise no more than four percent of the bits in the codewords of the low density parity check code.

10. The data storage system defined in claim 7 wherein parity check equations based on the low density parity check code comprise no more than 508 pseudo four cycles.

11. The data storage system defined in claim 7 wherein parity check equations based on the low density parity check code comprise no more than 508 type 1 proximity four cycles.

12. The data storage system defined in claim 7 wherein parity check equations based on the low density parity check code comprise no more than 2370 type 2 proximity four cycles.

13. The data storage system defined in claim 7 wherein the low density parity check code is generated by using number sequence {0, 2, 17, 18, 23, 10, 3, 12, 1, 15, 22, 5, 21, 6, 14, 11, 9, 19, 13, 8, 7, 20, 16, 4, repeat} to form the parity-check matrix.

14. A data storage system for correcting errors in a bit stream generated from a data storage medium, the data storage system comprising:

an encoder that encodes the bit stream using a low density parity check code by inserting parity check bits into the bit stream to generate codewords, wherein the encoder is defined in hardware using first logic circuits that are interconnected to implement a trellis that is based on the low density parity check code; and

a decoder that decodes the codewords using parity check equations that are based on the low density parity check code, wherein the decoder is defined in hardware using second logic circuits that are interconnected to implement a trellis that is based on the low density parity check code.

15. The data storage system defined in claim 14 wherein the first logic circuits comprise first multiplexers and first memory circuits, and the second logic circuits comprise second multiplexers and second memory circuits.

16. The data storage system defined in claim 14 wherein the low density parity check code is generated by using number sequence {0, 2, 17, 18, 23, 10, 3, 12, 1, 15, 22, 5, 21, 6, 14, 11, 9, 19, 13, 8, 7, 20, 16, 4, repeat} to form a matrix.

17. The data storage system defined in claim 16 wherein the low density parity check code equals {β

⁰, β

¹, β

², β

³, β

⁴, β

⁵, β

⁶, β

⁷, β

⁸, β

⁹, β

¹⁰, β

¹¹, β

¹², β

¹³, β

¹⁴, β

¹⁵, β

¹⁶, β

¹⁷, β

¹⁸, β

¹⁹, β

²⁰, β

²¹, β

²², β

²³, β

²⁴, β

²⁵}, and wherein β

is the matrix defined by the number sequence {0, 2, 17, 18, 23, 10, 3, 12, 1, 15, 22, 5, 21, 6, 14, 11, 9, 19, 13, 8, 7, 20, 16, 4, repeat}.

18. The data storage system defined in claim 14 wherein at most four percent of the bits in the codewords of the low density parity check code comprise the parity check bits.

19. A data storage system for correcting errors in a bit stream, the data storage system comprising:

an encoder that encodes the bit stream using a low density parity check code by inserting parity check bits into the bit stream to generate codewords, wherein the bit stream is read from a magnetic data storage medium in the data storage system; and

a decoder that decodes the codewords using parity check equations that are based on the low density parity check code, wherein the parity check equations have a maximum of 508 pseudo four cycles.

20. The data storage system defined in claim 19 wherein the parity check equations have a maximum of 508 type 1 proximity four cycles.

21. The data storage system defined in claim 19 wherein the parity check equations have a maximum of 2370 type 2 proximity four cycles.