Method and error correction system for correcting an error at a unit position of a received signal

Abstract

A method for correcting an error of a received signal is provided. The method includes: determining a target degree based upon a length of the received signal; obtaining plural primitive polynomials each having a degree equal to the target degree; selecting one of the primitive polynomials as a target polynomial; defining plural syndromes according to the received signal; generating a group of product values based on the syndromes; obtaining plural coefficient polynomials based on the product values; obtaining monomial trace coefficients based on the coefficient polynomials; generating an error correction value based on the monomial trace coefficients; and correcting the error based on the error correction value.

Claims

1. A method for correcting an error at a unit position of a received signal, the received signal being generated based upon a generator polynomial having a plurality of roots, said method comprising steps of: determining a target degree based upon a length of the received signal; obtaining a plurality of primitive polynomials each having a degree equal to the target degree; selecting one of the plurality of primitive polynomials as a target polynomial, roots of the target polynomial belonging to a Galois extension field of degree m, where the Galois extension field is an extension of Galois field, and m is the target degree; defining a plurality of syndromes according to the received signal, each of the syndromes being associated with a respective index; generating a group of product values based on the syndromes and the roots of the generator polynomial, each of the product values being represented by S.sub.iβ.sup.n-ij, where S.sub.i represents one of the syndromes associated with the index i, β.sub.i represents an i.sup.th one of the roots of the generator polynomial, n is the length of the received signal, and j represents the unit position of the received signal; for each of the product values, obtaining a coefficient polynomial $a_j^i\left(\alpha \right)=\underset{l=0}{\overset{m-1}{.Math.}}{a}_{\mathrm{jl}}^i{\alpha }^l$ based on the product value, where α.sup.0 to α.sup.m-1 form a basis set of the Galois extension field, and α.sub.j0.sup.i to α.sub.j(m-1).sup.i belong to the Galois field; for each of the coefficient polynomials obtained respectively from the product values, obtaining a monomial trace coefficient based on the coefficient polynomial according to the target polynomial and a trace mapping equation $\mathrm{Tr}\left(\gamma \right)=\underset{k=0}{\overset{m-1}{.Math.}}{\gamma }^{2^k},$ wherein the monomial trace coefficient is calculated according to Tr(α.sub.j.sup.i(α))=c.sub.ij, and c.sub.ij represents the monomial trace coefficient; generating an error correction value based on the monomial trace coefficients calculated respectively from the coefficient polynomials; and correcting the error at the unit position of the received signal based on the error correction value.

2. The method as claimed in claim 1, wherein the step of determining the target degree is to select a smallest value that satisfies an equation of (2.sup.m−1)mod n=0 as the target degree.

3. The method as claimed in claim 1, wherein the step of selecting one of the primitive polynomials as the target polynomial includes sub-steps of, for each of at least one of the primitive polynomials: determining whether the degree of the primitive polynomial is an odd number; when it is determined that the degree of the primitive polynomial is an odd number, determining whether for each term of the primitive polynomial except a constant term, a degree thereof is an odd number; and when it is determined that for each term of the primitive polynomial except the constant term, the degree is an odd number, selecting the primitive polynomial as the target polynomial.

4. The method as claimed in claim 1, wherein the step of selecting one of the primitive polynomials as the target polynomial includes sub-steps of, for each of at least one of the primitive polynomials: determining whether the degree of the primitive polynomial is an odd number; when it is determined that the degree of the primitive polynomial is not an odd number, calculating a difference value by subtracting a highest odd degree of terms of the primitive polynomial from the target degree; determining whether a first criterion that the difference value is greater than or equal to one half of the target degree, a second criterion that a number of those terms of the primitive polynomial, the degree of each of which is an even number and is greater than the difference value, is equal to a number of those terms of the primitive polynomial that have odd degrees, and a third criterion that, for each term of the primitive polynomial that has an odd degree, the primitive polynomial has a non-zero term having a degree that is equal to a sum of the odd degree and the difference value are all satisfied; and when the first, second and third criterions are all satisfied, selecting the primitive polynomial as the target polynomial.

5. The method as claimed in claim 1, wherein the step of generating the error correction value is to calculate the error correction value based on $e_j=S_0+\underset{i\in R}{.Math.}{c}_{\mathrm{ij}},$ where e.sub.j represents the error correction value.

6. An error correction system configured to correct an error at a unit position of a received signal, the received signal being generated based upon a generator polynomial having a plurality of roots, said error correction system comprising: an error correction decoder including a target polynomial generator configured to determine a target degree based upon a length of the received signal, to obtain a plurality of primitive polynomials each having a degree equal to the target degree, and to select one of the plurality of primitive polynomials as a target polynomial, roots of the target polynomial belonging to a Galois extension field of degree m, where the Galois extension field is an extension of Galois field, and m is the target degree, a syndrome generator configured to define a plurality of syndromes according to the received signal, each of the syndromes being associated with a respective index, a monomial trace coefficient generator coupled to said target polynomial generator and said syndrome generator, and configured to generate a group of product values based on the syndromes and the roots of the generator polynomial, each of the product values being represented by S.sub.iβ.sup.n-ij, where S.sub.i represents one of the syndromes associated with the index i, β.sub.i represents an i.sup.th one of the roots of the generator polynomial, n is the length of the received signal, and j represents the unit position of the received signal, for each of the product values, obtain a coefficient polynomial $a_j^i\left(\alpha \right)=\underset{l=0}{\overset{m-1}{.Math.}}{a}_{\mathrm{jl}}^i{\alpha }^l$ based on the product value, where α.sup.0 to α.sup.m-1 form a basis set of the Galois extension field, and α.sub.j0.sup.i to α.sub.j(m-1).sup.i belong to the Galois field, and  for each of the coefficient polynomials obtained respectively from the product values, obtain a monomial trace coefficient based on the coefficient polynomial according to the target polynomial and a trace mapping equation $\mathrm{Tr}\left(\gamma \right)=\underset{k=0}{\overset{m-1}{.Math.}}{\gamma }^{2^k},$ wherein the monomial trace coefficient is calculated according to Tr(α.sub.j.sup.i(α))=c.sub.ij, and c.sub.ij represents the monomial trace coefficient, and  an error correction value generator coupled to said monomial trace coefficient generator, and configured to generate an error correction value based on the monomial trace coefficients calculated respectively from the coefficient polynomials; and an error correcting device coupled to said error correction value generator, and configured to correct the error at the unit position of the received signal based on the error correction value.

7. The error correction system as claimed in claim 6, wherein said target polynomial generator is configured to select a smallest value that satisfies an equation of (2.sup.m−1)mod n=0 as the target degree.

8. The error correction system as claimed in claim 6, wherein said target polynomial generator is configured to select one of the primitive polynomials as the target polynomial by, for each of the primitive polynomials: determining whether the degree of the primitive polynomial is an odd number; when it is determined that the degree of the primitive polynomial is an odd number, determining whether for each term of the primitive polynomial except a constant term, a degree thereof is an odd number; and when it is determined that for each term of the primitive polynomial except the constant term, the degree thereof is an odd number, selecting the primitive polynomial as the target polynomial.

9. The error correction system as claimed in claim 6, wherein said target polynomial generator is configured to select one of the primitive polynomials as the target polynomial by, for each of the primitive polynomials: determining whether the degree of the primitive polynomial is an odd number; when it is determined that the degree of the primitive polynomial is not an odd number, calculating a difference value by subtracting a highest odd degree of terms of the primitive polynomial by the target degree; determining whether a first criterion that the difference value is greater than or equal to one half of the target degree, a second criterion that a number of those terms of the primitive polynomial, the degree of each of which is an even number and is greater than the difference value, is equal to a number of those terms of the primitive polynomial that have odd degrees, and a third criterion that, for each term of the primitive polynomial that has an odd degree, the primitive polynomial has a non-zero term having a degree that is equal to a sum of the odd degree and the difference value are all satisfied; and when the first, second and third criterions are all satisfied, selecting the primitive polynomial as the target polynomial.

10. The error correction system as claimed in claim 6, wherein said error correction value generator is configured to calculate the error correction value based on $e_j=S_0+\underset{i\in R}{.Math.}{c}_{\mathrm{ij}},$ where e.sub.j represents the error correction value.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other features and advantages of the disclosure will become apparent in the following detailed description of the embodiment (s) with reference to the accompanying drawings, of which:

(2) FIG. 1 is a block diagram illustrating an embodiment of an error correction system according to the disclosure;

(3) FIG. 2 is a flow diagram illustrating an embodiment of a method for correcting an error at a unit position of a received signal according to the disclosure; and

(4) FIG. 3 is a flow diagram illustrating sub-steps of a step of selecting a target polynomial of the method illustrated in FIG. 2.

DETAILED DESCRIPTION

(5) Before the disclosure is described in greater detail, it should be noted that where considered appropriate, reference numerals or terminal portions of reference numerals have been repeated among the figures to indicate corresponding or analogous elements, which may optionally have similar characteristics.

(6) Referring to FIG. 1, an embodiment of an error correction system 100 according to this disclosure is configured to correct an error of a received signal. The error correction system 100 includes an error correction decoder 101 and an error correcting device 102 coupled to the error correction decoder 101.

(7) A source signal is encoded based upon a generator polynomial g(x) to generate a cyclic codeword. Then, the cyclic codeword is transmitted to the error correction system 100 via a transmission channel, where interference might occurred, to result in a signal with a length n received by the error correction system 100 (hereinafter referred to as the “received signal”). The cyclic codeword can be expressed as a codeword polynomial

(8) $c\left(x\right)=\underset{j=0}{\overset{m-1}{.Math.}}{c}_j{x}^j,$
where j is a variable representing a unit position of the received signal, j∈{0,1, . . . ,n−1}, and (c.sub.0,c.sub.1, . . . ,c.sub.n-1) denotes an associated code vector. Errors of the received signal attributed to the interference can be expressed as an error polynomial

(9) $e\left(x\right)=\underset{j=0}{\overset{n-1}{.Math.}}{e}_j{x}^j.$
Therefore, the received signal can be expressed as

(10) $\begin{array}{cc}r\left(x\right)=\underset{j=0}{\overset{n-1}{.Math.}}{r}_j{x}^j=c\left(x\right)+e\left(x\right).& \left(1\right)\end{array}$

(11) The error correction decoder 101 includes a target polynomial generator 11, a syndrome generator 12, a monomial trace coefficient generator 13 coupled to the target polynomial generator 11 and the syndrome generator 12, and an error correction value generator 14 coupled to the monomial trace coefficient generator 13.

(12) Further referring to FIG. 2, a method for correcting an error at a unit position of a received signal is implemented by the error correction system 100 according to an embodiment of this disclosure. It should be noted that, for the received signal, there could be more than one unit position with an error to be corrected, but the following description is, for the sake of simplicity, illustrated with examples of correcting one error at one specific unit position of the received signal r(x). In the following description, the symbol j is a constant representing the specific unit position.

(13) In step 20, the target polynomial generator 11 determines a target degree m based upon the length n of the received signal. Specifically, the target degree m is determined by selecting a smallest value that satisfies an equation of (2.sup.m−1)mod n=0.

(14) In step 21, the target polynomial generator 11 obtains a plurality of primitive polynomials m(x) based on the target degree m. Each of the primitive polynomials m(x) is irreducible and has a degree equal to the target degree m. For example, the following table lists the primitive polynomials m(x) for when the target degree m is 3, 4, or 5.

(15) TABLE-US-00001 TABLE 1 m primitive polynomials m(x) 3 (x.sup.3 + x.sup.2 + 1), (x.sup.3 + x + 1) 4 (x.sup.4 + x.sup.3 + x.sup.2 + x + 1), (x.sup.4 + x.sup.3 + 1), (x.sup.4 + x + 1) 5 (x.sup.5 + x.sup.4 + x.sup.3 + x.sup.2 + 1), (x.sup.5 + x.sup.4 + x.sup.3 + x + 1), (x.sup.5 + x.sup.4 + x.sup.2 + x + 1), (x.sup.5 + x.sup.3 + x.sup.2 + x + 1), (x.sup.5 + x.sup.3 + 1), (x.sup.5 + x.sup.2 + 1)

(16) In step 22, the target polynomial generator 11 further selects one of the plurality of primitive polynomials m(x) as a target polynomial p(x), where roots of the target polynomial p(x) belong to a Galois extension field GF(2.sup.m) of degree m, and the Galois extension field GF(2.sup.m) is an extension of Galois field GF(2).

(17) In detail, step 22 includes sub-steps 221-225 to be iteratively performed for one or more of the primitive polynomials m(x) until the target polynomial p(x) is found, as shown in FIG. 3.

(18) First, the target polynomial generator 11 determines whether the degree of the primitive polynomial m(x) is an odd number (sub-step 221).

(19) When it is determined that the degree of the primitive polynomial m(x) is an odd number, the target polynomial generator 11 determines whether for each term of the primitive polynomial m(x) except a constant term, a degree thereof is an odd number (sub-step 222).

(20) When it is determined that all terms other than the constant term have an odd-number degree, the target polynomial generator 11 selects the primitive polynomial m(x) as the target polynomial p(x) (sub-step 225).

(21) For example, when the target degree m is determined to be “3” in step 20, the primitive polynomials m(x) are found to be (x.sup.3+x.sup.2+1) and (x.sup.3+x+1) in step 21, accordingly. Then, in step 221, it is determined that for each of the primitive polynomials (x.sup.3+x.sup.2+1) and (x.sup.3+x+1), the degree of the primitive polynomial (i.e., three) is an odd number. The terms of the primitive polynomial (x.sup.3+x.sup.2+1) other than the constant term have degrees of 3 and 2, while the terms of the primitive polynomials (x.sup.3+x+1) other than the constant term have degrees of 3 and 1. Therefore, only the primitive polynomial (x.sup.3+x+1) is determined, in sub-step 222, to have odd-degree terms only, except a constant term. Therefore, the primitive polynomial (x.sup.3+x+1) is selected as the target polynomial p(x) in sub-step 225.

(22) On the other hand, when it is determined, in sub-step 221, that the degree of the primitive polynomial m(x) is not an odd number, the target polynomial generator 11 calculates a difference value u by subtracting a highest odd degree of terms of the primitive polynomial m(x) from the target degree m (sub-step 223). Then, the target polynomial generator 11 determines whether the following first to third criterions are all satisfied (sub-step 224).

(23) The first criterion is that the difference value u is greater than or equal to one half of the target degree m. The second criterion is that a number of those terms of the primitive polynomial m(x), the degree of each of which is an even number and is greater than the difference value u, is equal to a number of those terms of the primitive polynomial m(x) that have odd degrees. The third criterion is that, for each term of the primitive polynomial m(x) that has an odd degree, the primitive polynomial m(x) has a non-zero term having a degree that is equal to a sum of the odd degree and the difference value u.

(24) When the first, second and third criterions are all satisfied, the target polynomial generator 11 selects the primitive polynomial m(x) as the target polynomial p(x) (sub-step 225).

(25) For example, when the target degree m is determined to be “4” in step 20, the primitive polynomials m(x) are found, in step 21, to be (x.sup.4+x.sup.3+x.sup.2+x+1), (x.sup.4+x.sup.3+1) and (x.sup.4+x+1), accordingly. For each of these three primitive polynomials, the degree thereof is determined to be not an odd number in sub-step 221, and the corresponding difference value u thereof is calculated in sub-step 223. Specifically, the difference value is equal to one (i.e., u=1) for the primitive polynomial (x.sup.4+x.sup.3+x.sup.2+x+1) or (x.sup.4+x.sup.3+1), and is equal to three (i.e., u=3) for the primitive polynomial (x.sup.4+x+1). In sub-step 224, it is found that only the primitive polynomial (x.sup.4+x+1) satisfies all the first, second and third criterions.

(26) In detail, the difference value u corresponding to the primitive polynomial (x.sup.4+x+1) is greater than one half of the target degree (that is u=3, m=4, and u>m/2). That is to say, the primitive polynomial (x.sup.4+x+1) satisfies the first criterion.

(27) As for the second criterion, the primitive polynomial (x.sup.4+x+1) has only one term x.sup.4 having an even degree that is greater than the difference value u, and only one term x having an odd degree. That is to say, the number of those terms of the primitive polynomial (x.sup.4+x+1), the degree of each of which is an even number and is greater than the difference value u is one, and is equal to the number of those terms of the primitive polynomial (x.sup.4+x+1) that have odd degrees. Accordingly, the primitive polynomial (x.sup.4+x+1) satisfies the second criterion.

(28) Regarding the third criterion, for each term of the primitive polynomial (x.sup.4+x+1) that has an odd degree (term x with degree of one), the primitive polynomial (x.sup.4+x+1) has a non-zero term x.sup.4 having a degree of four that is equal to a sum of the degree of the term x (one) and the difference value u (three). That is to say, the primitive polynomial (x.sup.4+x+1) satisfies the third criterion.

(29) Thus, the primitive polynomial (x.sup.4+x+1) is selected as the target polynomial p(x) in sub-step 225.

(30) Back to FIGS. 1 and 2, in step 23, the syndrome generator 12 defines a plurality of syndromes according to the received signal, where the syndrome S.sub.i is associated with an i.sup.th index. Specifically, the index i corresponding to each of multiple representative elements belongs to a set R of all representative elements of a cyclotomic coset C.sub.i of i modulo n, i.e., i∈R. Particularly, the cyclotomic coset C.sub.i is defined by C.sub.i={i.Math.2.sup.k|k=0,1, . . . ,d−1}, where d is a minimum positive integer satisfying i.Math.2.sup.d≡i(mod n). Since methods for generating the syndromes are known to those skilled in the art (see, for example, “Algebraic Decoding of (71, 36, 11), (79, 40, 15) and (97, 49, 15) Quadratic Residue Codes,” IEEE Transactions on Communications, Vol. 51, No. 9, pages 1463-1473, September 2003, and “Algebraic Decoding of (103, 52, 19) and (113, 57, 15) Quadratic Residue Codes,” IEEE Transactions on Communications, Vol. 53, No. 5, pages 749-754, May 2005), details thereof will be omitted herein for the sake of brevity.

(31) In step 24, the monomial trace coefficient generator 13 generates a group of product values based on the syndromes and the roots of the generator polynomial g(x), wherein each of the product values is represented by S.sub.iβ.sup.n-ij, where S.sub.i represents the syndrome associated with the index i, and β.sup.i represents an i.sup.th roots of the generator polynomial g(x).

(32) In step 25, for each of the product values, the monomial trace coefficient generator 13 obtains a coefficient polynomial

(33) $a_j^i\left(\alpha \right)=\underset{l=0}{\overset{m-1}{.Math.}}{a}_{\mathrm{jl}}^i{\alpha }^l$
based on the product value S.sub.iβ.sup.n-ij, that is

(34) $\begin{array}{cc}{a}_j^i\left(\alpha \right)=S_i{\beta }^{n-\mathrm{ij}}=\underset{l=0}{\overset{m-1}{.Math.}}{a}_{\mathrm{jl}}^i{\alpha }^l,& \left(2\right)\end{array}$
where α.sup.0 to α.sup.m-1 form a basis set of the Galois extension field GF(2.sup.m), and α.sub.j0.sup.i to α.sub.j(m-1).sup.i belong to the Galois field GF(2).

(35) In step 26, for each of the coefficient polynomials, the monomial trace coefficient generator 13 obtains a monomial trace coefficient c.sub.ij based on the coefficient polynomial according to a trace mapping equation

(36) 0$\begin{array}{cc}\mathrm{Tr}\left(\gamma \right)=\underset{k=0}{\overset{m-1}{.Math.}}{\gamma }^{2^k},& \left(3\right)\end{array}$
wherein the monomial trace coefficient c.sub.ij is calculated according to
Tr(α.sub.j.sup.i(α))=c.sub.ij,  (4)

(37) i.e. let γ=α.sub.j.sup.i(α), i∈R.

(38) In step 27, the error correction value generator 14 generates an error correction value e.sub.j based on the monomial trace coefficients. Specifically, the error correction value e.sub.j is calculated based on

(39) $\begin{array}{cc}{e}_j=S_0+\underset{i\in R}{.Math.}{c}_{\mathrm{ij}},& \left(5\right)\end{array}$
where S.sub.0 represents the syndrome with the index i=0.

(40) In step 28, the error correcting device 102 corrects the error at the specific unit position j of the received signal based on the error correction value.

(41) For example, in the case of m=3, the primitive polynomial (x.sup.3+x+1) would be selected as the target polynomial p(x) as previously described.

(42) According to Equation (3) and γ=α.sub.j.sup.i(α), each monomial trace coefficient can be obtained as

(43) $\begin{array}{cc}{c}_{\mathrm{ij}}=\mathrm{Tr}\left(\gamma \right)=\underset{k=0}{\overset{3-1}{.Math.}}{\gamma }^{2^k}=\gamma +{\gamma }^2+{\gamma }^4=\left(a_j^i\left(\alpha \right)\right)+{\left(a_j^i\left(\alpha \right)\right)}^2+{\left(a_j^i\left(\alpha \right)\right)}^4,\mathrm{where}{a}_j^i\left(\alpha \right)=\underset{l=0}{\overset{m-1}{.Math.}}{a}_{\mathrm{jl}}^i{\alpha }^l=a_{j0}^i+a_{j1}^i\alpha +a_{j2}^i{\alpha }^2.& \left(6\right)\end{array}$

(44) By using XOR operators (not shown) to perform addition operations, three equations x.sup.3=x+1, x.sup.4=x+x.sup.2 and x.sup.8=x can be obtained from the target polynomial p(x)=x.sup.3+x+1=0. Then, Equation (6) is simplified by substituting α.sup.3=α+1, α.sup.4=α+α.sup.2 and α.sup.8=α into Equation (6). As a result, the monomial trace coefficients c.sub.ij=α.sub.j0.sup.i are obtained, i∈R. The error correction value can be calculated accordingly, and is expressed by

(45) $e_j=S_0+\underset{i\in R}{.Math.}{c}_{\mathrm{ij}}=S_0+a_{j0}^1+a_{j0}^3.$

(46) It should be noted that, without selecting the target polynomial p(x) according to this disclosure, there would be no guarantee that a monomial trace coefficient c.sub.ij would be obtained. For example, in the case of m=3, if the primitive polynomial (x.sup.3+x.sup.2+1), rather than the primitive polynomial (x.sup.3+x+1), is selected for the subsequent calculation, we will get α.sup.3=α.sup.2+1, α.sup.4=1+α+α.sup.2, and α.sup.8=α for substituting into the equation of c.sub.ij. Then, we can get the monomial trace coefficient c.sub.ij=α.sub.j0.sup.i+α.sub.j1.sup.i+α.sub.j2.sup.i. Accordingly, the error correction value is calculated as

(47) $e_j=S_0+\underset{i\in R}{.Math.}{c}_{\mathrm{ij}}=S_0+a_{j0}^1+a_{j1}^1+a_{j2}^1+a_{j0}^3+a_{j1}^3+a_{j2}^3.$
There will therefore be the need to provide four additional adders, and the hardware of the error correction decoder 101 would be relatively more complicated.

(48) From the above, hardware of the error correction decoder 101 can be simplified because the target polynomial is selected properly according to this disclosure.

(49) In the description above, for the purposes of explanation, numerous specific details have been set forth in order to provide a thorough understanding of the embodiment(s). It will be apparent, however, to one skilled in the art, that one or more other embodiments may be practiced without some of these specific details. It should also be appreciated that reference throughout this specification to “one embodiment,” “an embodiment,” an embodiment with an indication of an ordinal number and so forth means that a particular feature, structure, or characteristic may be included in the practice of the disclosure. It should be further appreciated that in the description, various features are sometimes grouped together in a single embodiment, figure, or description thereof for the purpose of streamlining the disclosure and aiding in the understanding of various inventive aspects, and that one or more features or specific details from one embodiment may be practiced together with one or more features or specific details from another embodiment, where appropriate, in the practice of the disclosure.

(50) While the disclosure has been described in connection with what is (are) considered the exemplary embodiment(s), it is understood that this disclosure is not limited to the disclosed embodiment(s) but is intended to cover various arrangements included within the spirit and scope of the broadest interpretation so as to encompass all such modifications and equivalent arrangements.