ERROR CORRECTION CIRCUIT AND METHOD THEREOF

• US 20090276680A1
• Filed: 01/12/2009
• Published: 11/05/2009
• Est. Priority Date: 04/30/2008
• Status: Abandoned Application

• Current Assignee: Ali SPA (Bessemer Group Incorporated)
• Original Assignee: Ali SPA (Bessemer Group Incorporated)
• Inventors: CHIU, Yen-Lung
• Application Number:
  US12/351,989
• Publication Number:
  US 20090276680A1
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• 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 2020/1836 using a Reed Solomon [RS] code
• CPC Class Codes: G11B 2220/61 wherein solid state memory is used for storing A/V content
• CPC Class Codes: G11C 2029/0411 Online error correction
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• CPC Class Codes: H03M 13/3707 Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code
• CPC Class Codes: H03M 13/3715 Adaptation to the number of estimated errors or to the channel state

Abstract

An error correction method is applicable for accessing a data in a storage medium. The method includes the steps of: encoding a portion of the data and the whole data to produce a partial data parity for that portion of the data and a whole data parity for the whole data; using the partial data parity to decode the corresponding portion of the data and the corresponding partial data parity in order to correct error bits from the corresponding portion of the data and from the partial data parity according to the decoded result; using the whole data parity to decode the whole data and the whole data parity in order to correct the error bit from the whole data and the whole data parity according to the decoded result; and outputting the corrected data.

Claims

1. An error correction method, applied in an electronic system having a storage medium for accessing a data stream, wherein the data stream being divided into a plurality of data segments with an equal length, the improvement comprising each the data segment having a first portion of the data segment at least;

encoding the data segment and the corresponding first portion of the data segment to produce a whole data parity and a first partial data parity respectively when performing an encoding procedure; and

performing a decoding procedure comprising the steps of;

using the first partial data parity to decode the first portion of the data segment and the first partial data parity for correcting error bits in the first portion of the data segment and the first partial data parity; and

using the whole data parity to decode the corresponding data segment and the whole data parity for correcting error bits of the data segment and the whole data parity.

2. The error correction method of claim 1, wherein each of the first portion of the data segment further has a second portion of data segment which is encoded to produce a second partial data parity when performing the encoding procedure and while performing the decoding procedure using the second partial data parity to decode the second portion of the data segment and the second partial data parity for correcting error bits in the second portion of the data segment and the second partial data parity.

3. The error correction method of claim 2, wherein the decoding procedure further comprises the steps of:

using the second partial data parity to decode the second portion of the data segment and the second partial data parity for correcting error bits in the second portion of the data segment and the second partial data parity;

using the first partial data parity to decode the first portion of the data segment including the corrected second portion of the data segment and the first partial data parity for correcting error bits in the first portion of the data segment and the first partial data parity; and

using the whole data parity to decode the corresponding data segment including the corrected the first portion of the data segment and the whole data parity for correcting error bits of the data segment and the whole data parity.

4. The error correction method of claim 1, wherein an error correction capability for the data segment is directly proportional to the number of the partial data parities contained in the data segment.

5. The error correction method of claim 1, wherein the partial data parities can be stored in different page from the corresponding data segment.

6. The error correction method of claim 1, wherein the step of using the first partial data parity to decode the first portion of the data segment and the first partial data parity includes the following steps:

providing another storage space with the same format and space allocation as the data segment;

storing first portion of the data segment within the storage space;

filling the remaining the storage space with a plurality of zeros; and

using the corresponding first partial data parity to decode the content within the storage space.

7. The error correction method of claim 6, wherein the plurality of zeros in the storage space fills the front half of the storage space, and the first portion of the data segment is stored in the latter half of the storage space.

8. The error correction method of claim 3, wherein the step of using the second partial data parity to decode the second portion of the data segment and the second partial data parity includes the following steps:

providing another storage space with the same format and space allocation as the data segment, storing second portion of the data segment within the storage space, filling the remaining the storage space with a plurality of zeros, and using the corresponding second partial data parity to decode the content within the storage space; and

the step of using the first partial data parity to decode the first portion of the data segment and the first partial data parity includes the following steps;

providing another storage space with the same format and space allocation as the data segment, storing first portion of the data segment within the storage space, filling the remaining the storage space with a plurality of zeros, and using the corresponding first partial data parity to decode the content within the storage space.

9. An error correction method, applied in a storage medium for accessing a data stream, and the data stream being divided into a plurality of data segments with an equal length, and the method comprising the steps of:

performing an encoding procedure on each the data segment having a first portion of the data segment at least, comprising the steps of;

encoding the first portion of the data segments to produce a first partial data parity; and

encoding the data segments to produce a whole data parity; and

performing a decoding procedure on each the data segment, comprising the steps of;

determining whether number of error bits exceeds the bit number of an error correction capability of the whole data parity;

correcting error bits of the data segment and the whole data parity when the number of error bits not exceeds the error correction capability; and

using the first partial data parity to decode the corresponding first portion of the data segment and the first partial data parity when the number of error bits exceeds the error correction capability;

correcting error bits of the first portion of the data segment and the first partial data parity;

using the whole data parity to decode the corresponding data segment including the corrected first portion of the data segment and the whole data parity; and

correcting error bits of the data segment and the whole partial data parity.

10. The error correction method of claim 9, wherein the step of using the first partial data parity to decode the corresponding first portion of the data segment and the first partial data parity includes the following steps:

providing another storage space with the same format and space allocation as the data segment;

storing the first portion of the data segment within the storage space;

filling the remaining the storage space with a plurality of zeros; and

using the first partial data parity to decode the content within the storage space.

11. The error correction method of claim 10, wherein the plurality of zeros in the storage space fills the front half of the storage space, and the first portion of the data segment is stored in the latter half of the storage space.

12. The error correction method of claim 9, wherein each of the first portion of the data segment further has a second portion of data segment which is encoded to produce a second partial data parity when performing the encoding procedure and performing the decoding procedure using the second partial data parity to decode the second portion of the data segment and the second partial data parity for correcting error bits in the second portion of the data segment and the second partial data parity.

13. The error correction method of claim 12, wherein before the step of using the first partial data parity to decode the corresponding first portion of the data segment and the first partial data parity further comprises the steps of:

determining whether number of error bits exceeds the bit number of an error correction capability of the first data parity;

executing the step of using the first partial data parity to decode the corresponding first portion of the data segment and the first partial data parity when the number of error bits not exceeds the error correction capability; and

using the second partial data parity to decode the corresponding second portion of the data segment and the second partial data parity when the number of error bits exceeds the error correction capability;

correcting error bits of the second portion of the data segment and the second partial data parity;

using the first partial data parity to decode the corresponding first portion of the data segment including the corrected second portion of the data segment and the first partial data parity;

correcting error bits of the first portion of the data segment and the first partial data parity;

using the whole data parity to decode the corresponding data segment including the corrected first portion of the data segment and the whole data parity; and

correcting error bits of the data segment and the whole partial data parity.

14. The error correction method of claim 13, wherein the step of using the second partial data parity to decode the second portion of the data segment and the second partial data parity includes the following steps:

providing another storage space with the same format and space allocation as the data segment, storing second portion of the data segment within the storage space, filling the remaining the storage space with a plurality of zeros, and using the corresponding second partial data parity to decode the content within the storage space; and

the step of using the first partial data parity to decode the first portion of the data segment and the first partial data parity includes the following steps;

providing another storage space with the same format and space allocation as the data segment, storing first portion of the data segment within the storage space, filling the remaining the storage space with a plurality of zeros, and using the corresponding first partial data parity to decode the content within the storage space.

15. The error correction method of claim 9, wherein the partial data parities can be stored in different page from the corresponding data segment.

16. The error correction method of claim 9, wherein the error correction capability for the data segment is directly proportional to the number of the partial data parities contained in the data segment.

17. The error correction method of claim 9, wherein the partial data parity can be stored in the same page with the corresponding data segment and the whole data parity.

18. An error correction circuit, applicable in a storage medium for accessing a data stream, and the error correction circuit comprising:

a plurality of shift registers, for receiving the data stream to produce a whole data parity; and

a plurality of auxiliary shift registers, for receiving a portion of the data stream to produce a partial data parity,

whereby the storage medium uses the whole data parity and the partial data parity to correct the data stream and the portion of the data stream respectively.

19. An error correction circuit of claim 18, further comprising:

a plurality of XOR gates, and the XOR gates are installed alternately with the shift registers.

20. An error correction circuit of claim 18, further comprising:

a plurality of switches, coupled between the shift registers and the auxiliary shift registers,

wherein when the switches are closed, the auxiliary shift registers receives the portion of the data stream and produce the partial data parity; and

when the switches are open, the shift registers receives the data stream and produce the whole data parity.