Decoding method and error correction method of a cyclic code decoder

1. A cyclic code decoding method having an error correcting capability associated with an error correcting capability value, comprising the machine-implemented steps of:

establishing a lookup table including at least one syndrome pattern and one error pattern corresponding to said syndrome pattern;

receiving a codeword;

initializing a counter value to an initial value;

computing a syndrome of said codeword and a first Hamming weight corresponding to said syndrome;

if said first Hamming weight has a non-zero value that is not greater than said error correcting capability value, performing a first error correcting operation upon said codeword with reference to said syndrome;

if said first Hamming weight has a non-zero value that is greater than said error correcting capability value, and if said syndrome has a matching syndrome pattern in said lookup table, performing a second error correcting operation upon said codeword with reference to the error pattern that corresponds to the matching syndrome pattern;

if said first Hamming weight has a non-zero value that is greater than said error correcting capability value, and if said syndrome does not have a matching syndrome pattern in said lookup table:

(g1) choosing a syndrome pattern from said lookup table;

(g2) obtaining a syndrome difference by subtracting said syndrome pattern chosen in sub-step (g1) from said syndrome;

(g3) computing a second Hamming weight corresponding to said syndrome difference;

(g4) if said second Hamming weight is not greater than a predetermined check value, performing a third error correcting operation upon said codeword with reference to said syndrome difference and the error pattern corresponding to said syndrome pattern chosen in sub-step (g1); and

(g5) if said second Hamming weight is greater than the predetermined check value, performing a fourth error correcting operation upon said codeword with reference to a predetermined codeword bit length and a predetermined codeword message bit length to result in a new codeword, incrementing the counter value, and going back to step (d);

if the counter value is not larger than the initial value after determining that said first hamming weight has a zero value or after any one of the first, second and third error correcting operations, performing decoding of the corrected codeword; and

if the counter value is larger than the initial value after determining that said first hamming weight has a zero value or after any one of the first, second and third error correcting operations, performing a fifth error correcting operation upon the corrected codeword with reference to the counter value, the predetermined codeword bit length and the predetermined codeword message bit length to obtain a further corrected codeword, followed by decoding the further corrected codeword.

2. The cyclic code decoding method of claim 1 , wherein said lookup table includes

∑

i

=

1

⌈

T

/

2

⌉

⁢

⁢

C

i

k

syndromes patterns and corresponding error patterns, where:

C

i

k

=

k

⁡

(

k

-

1

)

⁢

⁢

…

⁢

⁢

(

k

-

i

+

1

)

i

⁡

(

i

-

1

)

⁢

⁢

…

⁢

⁢

(

2

)

⁢

(

1

)

t is said error correcting capability value of said cyclic code decoding method,

T is the highest value of t,

┌T/2┐ is T divided by 2 and rounded up to the next integer, and

k is said codeword message bit length;

said lookup table being established by obtaining the C i k error patterns that correspond to the error correcting capability value t=i and the codeword message bit length k, for i from 1 to ┌T/2┐.

3. The cyclic code decoding method of claim 1 , wherein said lookup table is stored in a non-volatile memory.

4. The cyclic code decoding method of claim 1 , wherein said first error correcting operation includes

cyclically shifting said syndrome by said codeword message bit length to obtain a first correction factor; and

subtracting the first correction factor from said codeword.

5. The cyclic code decoding method of claim 1 , wherein said second error correcting operation includes subtracting the error pattern that corresponds to the matching syndrome pattern from said codeword.

6. The cyclic code decoding method of claim 1 , wherein said third error correcting operation includes

cyclically shifting said syndrome difference by said codeword message bit length to obtain a correction factor; and

subtracting the correction factor and the error pattern corresponding to said syndrome pattern selected in sub-step (g1) from said codeword.

7. The cyclic code decoding method of claim 1 , wherein said fourth error correcting operation includes cyclically shifting said codeword by a difference between the predetermined codeword bit length and the predetermined codeword message bit length.

8. The cyclic code decoding method of claim 1 , wherein said fifth error correcting operation includes cyclically shifting the corrected codeword by a product of the counter value and a difference between the predetermined codeword bit length and the predetermined codeword message bit length.

9. The cyclic code decoding method of claim 1 , wherein said check value is C s =min[w(s i )]−t−1, where s i is said syndrome pattern chosen in sub-step (g1), t is said error correcting capability value of said cyclic code decoding method, and w(s i ) is a second Hamming weight corresponding to said syndrome pattern s i .

10. The cyclic code decoding method of claim 1 , wherein said initial value in step (c) is zero.

11. The cyclic code decoding method of claim 1 , wherein the counter value is incremented by one in sub-step (g-5).

12. An error correction method for a cyclic code decoding process having an error correcting capability associated with an error correcting capability value, comprising the steps of:

receiving a codeword;

computing, by one or more processors, a syndrome of said codeword and a Hamming weight corresponding to said syndrome; and

if said Hamming weight has a non-zero value that is not greater than said error correcting capability value, cyclically shifting, by the one or more processors, said syndrome by a predetermined codeword message bit length to obtain a correction factor, and subtracting the correction factor from said codeword.

13. An error correction method for a cyclic code decoding process having an error correcting capability associated with an error correcting capability value, comprising the machine-implemented steps of:

establishing a lookup table including at least one syndrome pattern and one error pattern corresponding to said syndrome pattern;

receiving a codeword;

computing, by one or more processors, a syndrome of said codeword and a first Hamming weight corresponding to said syndrome; and

if said first Hamming weight has a non-zero value that is greater than said error correcting capability value, and if said syndrome does not have a matching syndrome pattern in said lookup table, causing the one or more processors to:

(d1) choose a syndrome pattern from said lookup table;

(d2) obtain a syndrome pattern difference by subtracting said syndrome pattern chosen in sub-step (d1) from said syndrome;

(d3) compute a second Hamming weight corresponding to said syndrome difference; and

(d4) if said second Hamming weight is not greater than a predetermined check value, perform an error correcting operation upon said codeword with reference to said syndrome difference and the error pattern corresponding to said syndrome pattern chosen in sub-step (d1).

14. The error correction method of claim 13 , wherein said error correcting operation includes

cyclically shifting said syndrome difference by a predetermined codeword message bit length to obtain a correction factor; and

subtracting the correction factor and the error pattern corresponding to said syndrome pattern selected in sub-step (d1) from said codeword.