ENCODING DEVICE, DECODING DEVICE, ENCODING/DECODING DEVICE, AND RECORDING/REPRODUCING DEVICE

• US 20090199073A1
• Filed: 11/24/2008
• Published: 08/06/2009
• Est. Priority Date: 01/31/2008
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Kanaoka, Toshikazu, Ito, Toshio
• Granted Patent: US 8,151,162 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11B 20/1866 by interleaving G11B20/1809 takes precedence
• CPC Class Codes: G11B 2020/1836 using a Reed Solomon [RS] code
• CPC Class Codes: G11B 2020/1843 using a cyclic redundancy check [CRC]
• CPC Class Codes: G11B 2020/185 using an low density parity check [LDPC] code
• CPC Class Codes: G11B 2220/2516 Hard disks
• CPC Class Codes: G11B 2220/2537 Optical discs
• CPC Class Codes: H03M 13/098 using single parity bit
• 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/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/271 Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
• CPC Class Codes: H03M 13/2721 the interleaver involves a diagonal direction, e.g. by using an interleaving matrix with read-out in a diagonal direction
• CPC Class Codes: H03M 13/2778 Interleaver using block-wise interleaving, e.g. the interleaving matrix is sub-divided into sub-matrices and the permutation is performed in blocks of sub-matrices
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/2927 Decoding strategies
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding

Abstract

An error correction device error corrects without increasing in circuit scale. An encoder, includes: a first ECC encoder which interleaves a data string into n (n≧2) blocks of data strings at every m (m≧2) bits, and adds the error correction code parity; a parity encoder which creates a parity bit at every plurality of bits of the error correction code word, and adds the parity bit to said error correction code word; and a second ECC encoder, which generates a second error correction encoding, which is a linear encoding using iterative decoding. Concatenated type encoded data, where a parity bit is added to every plurality of bits, is created, so an increase of circuit scale can be prevented even if a data string is interleaved into a plurality of blocks and error correction code parity is generated.

Claims

1. An encoder, comprising:

an ECC encoder which interleaves a data string into n (n≧

2) blocks of data strings at every m (m≧

2) bits, generates a first error correction code parity from the data string of each of said interleaved blocks, and adds said first error correction code parity of each block to said data string to create an error correction code word;

a parity encoder which creates a parity bit at every plurality of bits of said error correction code word, and adds the parity bit to said error correction code word; and

a second ECC encoder which divides a second error correction code word in which a parity generated by said parity encoder is added to said error correction code word, into L (L≧

2) number of blocks of data strings at every K (K≧

2) bits, generates a second error correction code parity, which is a linear code, in said block units, from the data string of each block, and adds said second error correction code parity of each block to said second error correction code word to create a third error correction code word.

2. The encoder according to claim 1, wherein said second ECC encoder creates a third error correction code word, which satisfies a requirement of a low density parity check (LDPC) code, in which a number of “

1s”

in a parity check matrix is low (low density) and the code is a linear code, and generates a parity using a generation matrix corresponding to said parity check matrix.

3. The encoder according to claim 1, wherein said parity encoder divides said error correction code word into L (L≧

2) number of blocks, extracts q (q≧

2) number of data strings in p (p≧

1) bit units from each of said divided blocks, and generates parities for p×

q number of data strings.

4. The encoder according to claim 3, wherein said parity encoder adds said parities generated for said p×

q number of data strings to blocks other than said blocks that include the data strings used for the generation of said parities.

5. The encoder according to claim 1, wherein said ECC encoder comprises:

an interleave unit which interleaves said data string into n (n≧

2) blocks of data strings at every m (m≧

2) bits;

an ECC encoding unit which generates an error correction code parity from the data string of each of the interleaved blocks; and

a de-interleave unit which de-interleaves the data string of each of said blocks at every said m bits, restores the de-interleaved data string back to said data string, and adds a parity of said error correction code to said restored data string.

6. The encoder according to claim 1, wherein said ECC encoder generates a Reed Solomon code as said error correction code.

7. A decoder for decoding the encoded data encoded into the third error correction code word according to claim 1, comprising:

an iterative decoder which iteratively decodes the received encoded data string using the second ECC code parity, decodes said encoded data string into a bit string, and outputs likelihood of each bit; and

an ECC decoding circuit which iteratively performs error correction decoding based on the first error correction code of the encoded data string of said iterative decoder, and said encoded bit string correction decoding based on said likelihood according to error detection based on said parity bit.

8. The decoder according to claim 7, wherein said iterative decoder performs said iterative decoding using said parity of said second error correction code word, from said third error correction code word which satisfies a requirement of a low density parity check (LDPC) code, in which a number of “

1s”

in said parity check matrix is low (low density) and the code is a linear code, performs hard decision on said encoded data string to be said second error correction code word, and outputs the likelihood of each bit.

9. The decoder according to claim 8, wherein said iterative decoder stops said iterative decoding, and sets the likelihood of each bit in the block of said second error correction code word to a maximum likelihood value, when the block of said second error correction code word satisfies the parity check condition and an error is not detected in the error detection of said second error correction code word based on the parity bit string.

10. The decoder according to claim 7, wherein said ECC decoding circuit comprises:

an ECC decoder which performs error correction based on said first error correction code of the code bit string from said iterative decoder; and

a parity/likelihood correction unit which performs error detection based on said parity bit when the decoding by said ECC decoder fails, and corrects said code bit string to be input to said ECC decoder based on said likelihood using the result of said error detection.

11. The decoder according to claim 10, further comprises:

a separation unit which separates said parity bit from the code bit string from said iterative decoder, and outputs said parity bit to said parity/likelihood correction unit;

an interleave unit which interleaves said code bit string from which said parity bit has been separated into n (n≧

2) blocks of data strings at every said m (m≧

2) bits; and

a data storage unit which stores the data string of each of said interleaved blocks,

wherein said ECC decoder performs error correction on the data string of each block of said data storage unit based on said error correction code,

and said parity/likelihood correction unit corrects the data string of said data storage unit.

12. The decoder according to claim 10, wherein when said decoding fails, said parity/likelihood correction unit extracts q (q≧

2) number of data strings in p (p≧

1) bit units from said L number of blocks including said failed block, regenerates parities for p×

q number of data strings, and compares the parities with said added parity bits to detect errors.

13. The decoder according to claim 10, wherein said parity/likelihood correction unit extracts parities added to blocks other than said blocks that include the data stings used for the generation of said parities, and compares the parities with said regenerated parities.

14. The decoder according to claim 7, wherein said error correction code of said encoded data string is a Reed Solomon code.

15. An encoding/decoding device, comprising:

an ECC encoder which interleaves a data string into n (n≧

2) blocks of data strings at every m (m≧

2) bits, generates a first error correction code parity from the data string of each of said interleaved blocks, and adds said first error correction code parity of each block to said data string to create an error correction code word;

a parity encoder which creates a parity bit at every plurality of bits of said error correction code word, and adds the parity bit to said error correction code word;

a second ECC encoder which divides a second error correction code word in which a parity generated by said parity encoder is added to said error correction code word, into L (L≧

2) number of blocks of data strings at every K (K≧

2) bits, generates a second error correction code parity, which is a linear code, in said block units, from the data string of each block, and adds said second error correction code parity of each block to said second error correction code word to create a third error correction code word;

an iterative decoder which iteratively decodes the received encoded data string using the second ECC code parity, decodes said encoded data string into a bit string, and outputs likelihood of each bit; and

an ECC decoding circuit which iteratively performs error correction decoding based on the first error correction code of the encoded data string of said iterative decoder, and said encoded bit string correction decoding based on said likelihood according to error detection based on said parity bit.

16. The encoding/decoding device according to claim 15, wherein

said second ECC encoder creates a third error correction code word, which satisfies a requirement of a low density parity check (LDPC) code, in which a number of “

1s”

in a parity check matrix is low (low density) and the code is a linear code, and generates a parity using a generation matrix corresponding to said parity check matrix, and

said iterative decoder performs said iterative decoding using said parity of said second error correction code word, from said third error correction code word which satisfies the requirement of the low density parity check (LDPC) code, in which a number of “

1s”

in said parity check matrix is low (low density) and the code is a linear code, performs hard decision on said encoded data string to be said second error correction code word, and outputs the likelihood of each bit.

17. The encoding/decoding device according to claim 15, wherein

said parity encoder divides said error correction code word into L (L≧

2) number of blocks, extracts q (q≧

2) number of data strings in p (p≧

1) bit units from each of said divided blocks, and generates parities for p×

q number of data strings, and when said decoding fails, said ECC decoding circuit extracts q (q≧

2) number of data strings in p (p≧

1) bit units from said L number of blocks including said failed block, regenerates parities for the p×

q number of data strings, and compares the parities with said added parity bits to detect errors.

18. A recording/reproducing device, comprising:

a head which writes and reads data to/from a storage medium;

an ECC encoder which interleaves a data string to be written to the storage medium into n (n≧

2) blocks of data strings at every m (m≧

2) bits, generates a first error correction code parity from the data string of each of said interleaved blocks, and adds said first error correction code parity of each block to said data string to create an error correction code word;

a parity encoder which creates a parity bit at every plurality of bits of said error correction code word, and adds the parity bit to said error correction code word;

a second ECC encoder which divides a second error correction code word in which a parity generated by said parity encoder is added to said error correction code word, into L (L≧

2) number of blocks of data strings at every K (K≧

2) bits, generates a second error correction code parity, which is a linear code, in said block units, from the data string of each block, and adds said second error correction code parity of each block to said second error correction code word to create a third error correction code word, and outputs the third error correction code word to said head;

an iterative decoder which iteratively decodes said encoded data string read by said head, using the second ECC code parity, decodes said encoded data string into a bit string, and outputs likelihood of each bit; and

an ECC decoding circuit which iteratively performs error correction decoding based on the first error correction code of the encoded data string of said iterative decoder, and said encoded bit string correction decoding based on said likelihood according to error detection based on said parity bit.

19. The recording/reproducing device according to claim 18, wherein

said second ECC encoder creates a third error correction code word, which satisfies a requirement of a low density parity check (LDPC) code, in which a number of “

1s”

in a parity check matrix is low (low density) and the code is a linear code, and generates a parity using a generation matrix corresponding to said parity check matrix, and

said iterative decoder performs said iterative decoding using said parity of said second error correction code word, from said third error correction code word which satisfies the requirement of the low density parity check (LDPC) code, in which a number of “

1s”

in said parity check matrix is low (low density) and the code is a linear code, performs hard decision on said encoded data string to be said second error correction code word, and outputs the likelihood of each bit.

20. The recording/reproducing device according to claim 18, wherein

said parity encoder divides said error correction code word into L (L≧

2) number of blocks, extracts q (q≧

2) number of data strings in p (p≧

1) bit units from each of said divided blocks, and generates parities for p×

q number of data strings, and when said decoding fails,

said ECC decoding circuit extracts q (q≧

2) number of data strings in p (p≧

1) bit units from said L number of blocks including said failed block, regenerates parities for the p×

q number of data strings, and compares the parities with said added parity bits to detect errors.