Method for calculating syndrome polynomial in decoding error correction codes
The present invention provides a method of calculating the syndrome polynomial in decoding error correction codes. From the relation between the syndromes and the coefficients of the error locator polynomial, the inference that the first t syndromes are zeros, then the next t syndromes are also zeros can be deduced, wherein t is the largest number of correctable errors. For all received codewords, the first t syndromes are calculated. Next, whether the first t syndromes are zeros is judged. If the first t syndromes are zeros, the computation is stopped; otherwise, the next t syndromes are calculated. Therefore, the present invention can judge whether the received codeword is erroneous with only a half of computation, hence effectively reducing the computation in practical operation and achieving the object of low power consumption.
1. A method of calculating the syndrome polynomial in decoding received codewords processed by error correction codes, comprising the steps of:
using all said received codewords processed by error correction codes to calculate the first t syndromes, wherein t is the number of correctable errors;
judging whether said first t syndromes are zeros, determination of whether said first t syndromes are all zero being made simultaneously for all t, stopping the computation if said first t syndromes are zeros;
continually calculating the next t syndromes if said first t syndromes are not all zero.
2. The method of calculating the syndrome polynomial as claimed in claim 1 , wherein said received codewords are the Reed-Solomon codes or BCH (Base-Chaudhuri-Hocquenghem) codes.
3. The method of calculating the syndrome polynomial as claimed in claim 1 , wherein when said first t syndromes are zeros, meaning said next t syndromes are also zeros, the computation is stopped because there is no error in said received codewords.
4. The method of calculating the syndrome polynomial as claimed in claim 3 , wherein the inference that said first t syndromes are zeros, then said next t syndromes are also zeros is deduced from the relation between said 2t syndromes (S 1 ˜S 2t ) and coefficients (σ 1 ˜σ t ) of an error locator polynomial.
5. The method of calculating the syndrome polynomial as claimed in claim 4 , wherein said relation between said 2t syndromes (S 1 ˜S 2t ) and said coefficients (σ 1 ˜σ t ) of said error locator polynomial is
[
S
1
S
2
S
3
⋯
S
t
S
2
S
3
S
4
⋯
S
t
+
1
S
3
S
4
S
5
⋯
S
t
+
2
⋮
⋮
⋮
⋮
S
t
S
t
+
1
S
t
+
2
⋯
S
2
t
]
[
σ
t
σ
t
-
1
σ
t
-
2
⋮
σ
1
]
=
[
-
S
t
+
1
-
S
t
+
2
-
S
t
+
3
⋮
-
S
2
t
]
.
6. The method of calculating the syndrome polynomial as claimed in claim 5 , wherein said relation only holds when the practical number of errors, υ, is smaller than or equal to said largest number of correctable errors, t.
7. A method of calculating the syndrome polynomial in decoding received error-and-erasure codewords, comprising the steps of:
using all said received error-and-erasure codewords processed by error correction codes to calculate the first t syndromes, wherein t is the number of correctable errors;
judging whether said first t syndromes are zeros, determination of whether said first t syndromes are all zero being made simultaneously for all t, stopping the computation if said first t syndromes are zeros;
continually calculating the next t syndromes if said first t syndromes are not all zero.
8. The method of calculating the syndrome polynomial as claimed in claim 7 , wherein said received codewords are the Reed-Solomon codes.
9. The method of calculating the syndrome polynomial as claimed in claim 7 , wherein when said first t syndromes are zeros, meaning said next t syndromes are also zeros, the computation is stopped because there is no error in said received codewords.
10. The method of calculating the syndrome polynomial as claimed in claim 9 , wherein the inference that said first t syndromes are zeros, then said next t syndromes are also zeros is deduced from the relation between said 2t syndromes (S 1 ˜S 2t ) and coefficients (σ 1 ˜σ t ) of an error locator polynomial.
11. The method of calculating the syndrome polynomial as claimed in claim 10 , wherein said relation between said 2t syndromes (S 1 ˜S 2t ) and said coefficients (σ 1 ˜σ t ) of said error locator polynomial is
[
S
1
S
2
S
3
⋯
S
t
S
2
S
3
S
4
⋯
S
t
+
1
S
3
S
4
S
5
⋯
S
t
+
2
⋮
⋮
⋮
⋮
S
t
S
t
+
1
S
t
+
2
⋯
S
2
t
]
[
σ
t
σ
t
-
1
σ
t
-
2
⋮
σ
1
]
=
[
-
S
t
+
1
-
S
t
+
2
-
S
t
+
3
⋮
-
S
2
t
]
.
12. The method of calculating the syndrome polynomial as claimed in claim 11 , wherein said relation only holds when the practical number of errors, υ, is smaller than or equal to said largest number of correctable errors, t.