Patent Publication Number: US-8527854-B2

Title: Error detection module, and error correction device including the same

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to an error correction device, more particularly to an error correction device for cyclic codes. 
     2. Description of the Related Art 
     Reed-Solomon (RS) codes are generally used in communication, optical-disc system, high-definition television, etc. When a transmitter transmits an RS code to a receiver, a received signal received by the receiver may have errors and errata due to noise interference during data access and transmission. Therefore, the receiver has to correct the errors and errata of the received signal to thereby obtain original information corresponding to the RS code transmitted by the transmitter. 
     Before correcting the errors and the errata of the received signal, the receiver has to decode the received signal corresponding to the RS code. Nowadays, many algorithms for decoding the RS code have been proposed. For example, in “Decoding of redundant residue polynomial codes using Euclid&#39;s algorithm,”  IEEE Trans. On Inf. Theory , Vol. 34, No. 5, pages 1351-1354, September 1988, A. Shiozaki uses the Chinese remainder theorem together with the Euclidean algorithm so as to develop an algorithm for decoding RS codes. However, in view of the complexity of this algorithm, the rate of decoding is relatively slow. 
     S. V. Fedorenko proposed deriving Gao&#39;s algorithm from the Welch-Berlekamp algorithm and the Euclidean algorithm for decoding RS codes in “A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm,”  IEEE Trans. On Inf. Theory , Vol. 51, No. 3, pages 1196-1198, March 2005. Recently, in “Simplified procedure for decoding nonsystematic Reed-Solomon codes over GF (2 m ) using Euclid&#39;s algorithm and the fast Fourier transform,”  IEEE Trans. On Commun ., May 2009, T. C. Lin et al. proposed that Gao&#39;s algorithm may be extended to correct erasures as well as errors by replacing the initial conditions of the Euclidean algorithm by the erasure-locator polynomial and errata interpolating polynomial. However, use of interpolation substantially increases complexity of the algorithm for decoding RS codes, and thus significantly slows down the rate of decoding. 
     SUMMARY OF THE INVENTION 
     Therefore, an object of the present invention is to provide an error correction device capable of increasing the rate of decoding cyclic codes. 
     Accordingly, an error correction device of the present invention is adapted for correcting an error of a received signal received thereby. Erasure positions of the received signal are represented by an erasure-locator polynomial. The error correction device comprises an error detection module and an error correction module. 
     The error detect ion module includes a known-syndrome computing unit, an unknown-syndrome computing unit, and an error detection unit. 
     The known-syndrome computing unit has a converter adapted to receive the received signal, and an errata-locator polynomial generator operatively coupled to the converter. The converter is operable to convert the received signal into a target signal, and to obtain a plurality of known syndromes based upon the target signal. The errata-locator polynomial generator is operable to generate an errata-locator polynomial based upon the erasure-locator polynomial and the known syndromes. The unknown-syndrome computing unit is operatively coupled to the known-syndrome computing unit, and is operable to compute a plurality of unknown syndromes based upon the errata-locator polynomial and the known syndromes. The error detection unit is operatively coupled to the known-syndrome computing unit and the unknown-syndrome computing unit. The error detection unit is operable to obtain a syndrome set including the known syndromes and the unknown syndromes, and to obtain an error detection signal according to the syndrome set. 
     The error correction module operatively is coupled to the error detection module so as to receive the syndrome set and the error detection signal therefrom. The error correction module is operable to correct the error of the received signal according to the syndrome set and the error detection signal. 
     Another object of the present invention is to provide an error detection module adapted for use in the above-mentioned error correction device according to the present invention. 
     According to another aspect of this invention, an error detection module is adapted to be coupled to an error correction module for providing the error correction module with a syndrome set and an error detection signal for enabling the error correction module to correct an error of a received signal received by the error detection module. Erasure positions of the received signal are represented by an erasure-locator polynomial. The error detection module comprises a known-syndrome computing unit, an unknown-syndrome computing unit, and an error detection unit. 
     The known-syndrome computing unit includes a converter and an errata-locator polynomial generator. The converter is adapted to receive the received signal, and is operable to convert the received signal into a target signal, and to obtain a plurality of known syndromes based upon the target signal. The errata-locator polynomial generator is operatively coupled to the convertor, and is operable to generate an errata-locator polynomial based upon the erasure-locator polynomial and the known syndromes. 
     The unknown-syndrome computing unit is operatively coupled to the known-syndrome computing unit, and is operable to compute a plurality of unknown syndromes based upon the errata-locator polynomial and the known syndromes. The error detection unit is operatively coupled to the known-syndrome computing unit and the unknown-syndrome computing unit. The error detection unit is operable to obtain the syndrome set that includes the known syndromes and the unknown syndromes, to obtain the error detection signal according to the syndrome set, and to provide the error correction module with the syndrome set and the error detection signal obtained thereby. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
       Other features and advantages of the present invention will become apparent in the following detailed description of the preferred embodiment with reference to the accompanying drawing, of which: 
         FIG. 1  is a block diagram illustrating a preferred embodiment of an error correction device according to the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Before transmission, an original message signal is encoded based upon a generator polynomial G(x) to generate a (n, k, d) cyclic codeword (e.g., Reed-Solomon code), wherein n is a length of the cyclic codeword, k is a message length of the original message signal, and d is a Hamming distance of the cyclic codeword. A message polynomial of the cyclic codeword may be defined as 
     
       
         
           
             
               
                 
                   
                     M 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         k 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         m 
                         i 
                       
                       ⁢ 
                       
                         
                           x 
                           i 
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     Further, the cyclic codeword may be written as a codeword vector
 
 c= ( c   0   ,c   1   , . . . ,c   n−1 ).  (2)
 
     Then, components c 0  to c n−1  can be computed based upon
 
 c   j   =M (α j ) for 0≦ j≦n− 1,  (3)
 
where α is an n th  root of unity in a finite field, i.e., Galois Field GF(2 m ).
 
     For instance, a communication system includes a sending end and a receiving end. The sending end is configured to generate a message vector m consisting of information and zeros, that is to say,
 
 m={m   0   ,m   1   ,m   2   , . . . ,m   k−1   ,m   k   ,m   k+1   , . . . ,m   n−1 },  (3)
 
where m 0  to m k−1  are assigned to be information symbols, and m k  to m n−1  are assigned to be syndrome symbols and are assumed to be zero.
 
     Then, the components c j  of the cyclic codeword c can be computed based upon the inverse fast Fourier transform of the message vector m over the finite field GF(2 m ) as follows, 
     
       
         
           
             
               
                 
                   
                     c 
                     j 
                   
                   = 
                   
                     
                       
                         1 
                         n 
                       
                       · 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             n 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             m 
                             i 
                           
                           · 
                           
                             α 
                             
                               - 
                               ij 
                             
                           
                         
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             n 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             m 
                             i 
                           
                           · 
                           
                             α 
                             
                               - 
                               ij 
                             
                           
                         
                       
                       = 
                       
                         
                           M 
                           ⁡ 
                           
                             ( 
                             
                               α 
                               
                                 - 
                                 j 
                               
                             
                             ) 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     Subsequently, the sending end is configured to send the cyclic codeword c via a transmission channel to result in a received signal r received by the receiving end. Since the cyclic codeword c may be corrupted by noise interference during transmission through the transmission channel, the received signal r may consist of an error signal e=(e 0 , e 1 , . . . , e n−1 ), an erasure signal μ=(μ 0 , μ 1 , . . . , μ n−1 ), and the cyclic codeword c. Thus, the received signal r would not be exactly the same as the original message signal. An errata signal is defined as
 
{tilde over (μ)}=μ+ e= ({tilde over (μ)} 0 ,{tilde over (μ)} 1 , . . . ,{tilde over (μ)} n−1 ).  (5)
 
     Accordingly, the received signal may be defined as
 
 r=c +{tilde over (μ)}=( r   0   ,r   1   , . . . ,r   n−1 ).  (6)
 
     Further, an erasure-locator polynomial Λ(x), an error-locator polynomial W(x), and an errata-locator polynomial τ(x) are defined as follows, 
                       Λ   ⁡     (   x   )       =         ∏     j   =   1     s     ⁢           ⁢     (     1   -       Z   j     ⁢   x       )       =       ∑     j   =   0     s     ⁢       Λ   j     ⁢     x   j             ,           (   7   )                   W   ⁡     (   x   )       =         ∏     j   =   1     v     ⁢           ⁢     (     1   -       X   j     ⁢   x       )       =       ∑     j   =   0     v     ⁢       W   j     ⁢     x   j             ,           ⁢   and           (   8   )                   τ   ⁡     (   x   )       =         Λ   ⁡     (   x   )       ·     W   ⁡     (   x   )         =         ∏     j   =   1       v   +   s       ⁢           ⁢     (     1   -         X   ~     j     ⁢   x       )       =       ∑     j   =   0       v   +   s       ⁢       τ   j     ⁢     x   j               ,           (   9   )               
where Λ 0 =W 0 =1, Z j  is an erasure position in the erasure signal μ, X j  is an error position in the error signal e, and {tilde over (X)} j  is either a j th  erasure or a j th  error position.
 
     Referring to  FIG. 1 , a preferred embodiment of an error correction device according to this invention is adapted for correcting errors of a received signal r received thereby, and includes an error detect on module  1  and an error correction module  2 . The error detection module  1  includes a known-syndrome computing unit  11 , an unknown-syndrome computing unit  12 , and an error detection unit  13 . 
     The known-syndrome computing unit  11  is adapted to receive the received signal r, and to obtain a plurality of known syndromes according to the received signal r. In particular, an i th  syndrome S i  associated with a respective index i of the error signal e is defined as e(β i ), where β i  is a primitive root of the generator polynomial G(x). The known-syndrome computing unit  11  consists of a converter  111 , and an errata-locator polynomial generator  112  operatively coupled to the converter  111 . 
     The converter  111  is adapted to receive the received signal r, and is operable to convert the received signal into a target signal a=(a 0 , a 1 , . . . , a n−1 ) based upon the following Equation (10). 
     
       
         
           
             
               
                 
                   
                     a 
                     i 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         
                           n 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           r 
                           j 
                         
                         · 
                         
                           α 
                           
                             i 
                             · 
                             j 
                           
                         
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           
                             j 
                             = 
                             0 
                           
                           
                             n 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   c 
                                   j 
                                 
                                 + 
                                 
                                   
                                     μ 
                                     ~ 
                                   
                                   j 
                                 
                               
                               ) 
                             
                             · 
                             
                               α 
                               
                                 i 
                                 · 
                                 j 
                               
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           for 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           0 
                         
                       
                       ≤ 
                       i 
                       ≤ 
                       
                         n 
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     Hence, based upon the target signal a, the converter  111  is further operable to obtain a number (d−1) of known syndromes as S i =a i , for 1≦i≦d−1. 
     Then, the errata-locator polynomial generator  112  is operable to generate the errata-locator polynomial τ(x) based upon the erasure-locator polynomial Λ(x) and the known syndromes S 1  to S d−1 . In “Implementation of Berlekamp Massey algorithm without inversion,”  Proc. IEE , Vol. 138, No. 3, pages 138-140, January 1991, and “VLSI design of inverse-free Berlekamp-Massey algorithm,”  Proc. Inst. Elect. Eng ., Vol. 138, pages 295-298, September 1991, there is disclosed an inverse-free Berlekamp-Massey (BM) algorithm for computing the errata-locator polynomial τ(x). In the inverse-free BM algorithm, Forney syndromes are defined as follows 
     
       
         
           
             
               
                 
                   
                     T 
                     k 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         s 
                       
                       ⁢ 
                       
                         
                           Λ 
                           j 
                         
                         ⁢ 
                         
                           S 
                           
                             k 
                             + 
                             s 
                             - 
                             j 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         for 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                     ≤ 
                     k 
                     ≤ 
                     
                       d 
                       - 
                       1 
                       - 
                       
                         s 
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     Accordingly, the errata-locator polynomial τ(x) may be directly determined by use of the inverse-free BM algorithm initialized with the erasure-locator polynomial Λ(x). Since methods for determining the errata-locator polynomial τ(x) are disclosed in the foregoing documents, details thereof will be omitted herein for the sake of brevity. 
     The unknown-syndrome computing unit  12  is operatively coupled to the known-syndrome computing unit  11 , and is operable to obtain a plurality of unknown syndromes based upon the errata-locator polynomial τ(x) and the known syndromes S 1  to S d−1 . In particular, the unknown-syndrome computing unit  12  is operable to compute the unknown syndromes based upon
 
 S   i =τ 1   S   i−1 +τ 2   S   i−2 + . . . +τ ν+s   S   i−(ν+s) ,  (12)
 
where S d  to S n  are the unknown syndromes, τ 1  to τ ν+s  are coefficients of the errata-locator polynomial τ(x), ν is a number of errors in the received signal, and s is a number of erasures in the received signal. The coefficients τ 1  to τ ν+s  can be obtained from the errata-locator polynomial τ(x), and then the unknown-syndrome computing unit  12  is operable to compute the unknown syndromes S d  to S n  by means of recursion of Equation (12).
 
     The error detection unit  13  is operatively coupled to the known-syndrome computing unit  11  and the unknown-syndrome computing unit  12 , and is operable to obtain a syndrome set S={S 0 , S 1 , S 2 , . . . , S n−1 }. The syndrome set S includes the known syndromes S 1  to S d−1  and the unknown syndromes S d  to S n =S 0 . The error detection unit  13  is further operable to generate an error detection signal according to the syndrome set S. The error correction module  2  is operatively coupled to the error detection unit  13  so as to receive the syndrome set S and the error detection signal therefrom, and is operable to correct the errors of the received signal r according to the syndrome set S and the error detection signal. 
     In detail, when all of the syndromes S 0  to S n−1  in the syndrome set S are equal to 0, this means that the received signal r does not include the error signal e and the erasure signal μ. Thus, the error detection unit  13  is operable to provide the error correction module  2  with the error detection signal indicating that the received signal r only includes the cyclic codeword c corresponding to the original message signal. That is to say, the cyclic codeword c is not corrupted by interference during transmission, and thus the received signal does not require correction. 
     On the other hand, when any of the syndromes S 0  to S n−1  in the syndrome set S is not equal to 0, this means that the received signal r includes at least one of the error signal e and the erasure signal μ. Accordingly, the error detection unit  13  is operable to provide the error correction module  2  with the error detection signal indicating that the received signal r does not only include the cyclic codeword c and fails to correspond to the original message signal. Further, the error detection unit  13  is operable to send the syndrome set S and the target signal a to the error correction module  2 . 
     In response to the error detection signal indicating that the received signal r fails to correspond to the original message signal, the error correction module  2  is operable to compute the message vector m so as to correct the errors of the received signal r based upon the following Equation (13).
 
 m   i   =a   i   −S   i  for 0 ≦i≦n− 1  (13)
 
     The following example is provided for illustrating the operation of the error correction device of this embodiment. 
     Regarding a (7, 4, 4) cyclic codeword, the length of the cyclic codeword is equal to 7, the message length of the original message signal is equal to 4, and the Hamming distance of the cyclic codeword is equal to 4. It is assumed that the message polynomial of the cyclic codeword is M(x)=α 4 x 3 +αx 4 +α 2 x 5 +α 5 x 6 , and the message vector m=(α 4 , 0, 0, 0, α, α 2 , α 5 ). Therefore, according to Equation (4), the codeword vector corresponding to the cyclic codeword is given by c=(α 5 , α 3 , α 3 , α 6 , α 2 , α 4 , α 4 ). 
     It is assumed that the cyclic codeword is corrupted by interference during transmission, and thus the received signal r received by the known-syndrome computing unit  11  is r=(α 5 , 1, α 3 , α 6 , α 2 , α 6 , α 4 ). The converter  111  is operable to convert the received signal r to the target signal a=(α 5 , α 4 , α 4 , 0, 1, 0, 1) based upon Equation (10). Hence, the known syndromes are S i =a i , for 1≦i≦d−1, i.e., S 1 =a 1 =α 4 , S 2 =a 2 =α 4 , S 3 =a 3 =0. Next, the errata-locator polynomial generator  112  is operable to compute the errata-locator polynomial τ(x)=1+α 6 x+α 6 x 2  according to the inverse-free BM algorithm associated with the initial value μ (0) (x)=Λ(x)=(1+α 5 x). 
     The unknown-syndrome computing unit  12  is operable to obtain the unknown syndromes S i =α 6 S i−1 +α 6 S i−2 , for 4≦i≦7, based upon Equation (12) and the coefficients of the errata-locator polynomial τ(x). Therefore, the unknown syndromes can be obtained as S 4 =α 3 , S 5 =α 2 , S 6 =α 4 , and S 0 =S 7 =1. Finally, the error correction module  2  is operable to compute the information and syndrome symbols, m 0 =α 4 , m 1 =0, m 2 =0, m 3 =0, m 4 =α, m 5 =α 2 , and m 6 =α 5  based upon Equation (13) so as to correct the errors of the received signal r. 
     To sum up, the error correction device according to this invention is operable to correct the errors of the received signal r by a method developed from the inverse-free BM algorithm that avoids use of interpolation. Accordingly, the complexity of decoding the cyclic code is decreased and the rate of computing the syndromes is increased to thereby enhance the rate of correction. 
     While the present invention has been described in connection with what is considered the most practical and preferred embodiment, it is understood that this invention is not limited to the disclosed embodiment 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.