Patent Publication Number: US-2010131807-A1

Title: Decoding algorithm for quadratic residue codes

Description:
BACKGROUND OF THE INVENTION 
     1. Field of Invention 
     This invention relates to a decoding algorithm, more particularly a decoding algorithm for decoding quadratic residue code. 
     2. Related Art 
     In today&#39;s digital era, a wide variety of signals—such as video and audio signals—are digitalized. A few examples of products that use digital signals include digital TV, Bluetooth headphones, DVD players, WAP mobile phone handsets, etc. To ensure that the signals used in digital products can be read properly, enabling the products to present high-definition video and audio even when the signals have been transmitted over long distances, the signals are typically encoded and decoded. 
     Currently, quadratic residue codes are widely used in digital encoding and decoding in many different fields. In most cases, the decoding of quadratic residue codes involves the use of an algebraic decoding method to eliminate unknown syndromes from among the Newton&#39;s identities so as to obtain the error polynomial coefficient, which in turn can be used to obtain the error polynomial. However, as the length of quadratic residue codes increases, it becomes increasingly difficult for the high order equations produced when using an algebraic method to find a solution over a finite field, making it difficult to obtain the error polynomial. 
     To address the problem of the increasing difficulty in obtaining the error polynomial by algebraic methods as quadratic residue codes grow longer, the inverse-free Berlekamp-Massey algorithm is widely used to calculate the error polynomial. However, there are not enough continuous known syndromes for quadratic residue codes to enter into the inverse-free Berlekamp-Massey algorithm to be able to calculate the correct error polynomial, which in turn would make it possible to obtain the correct coding within the error correction capability of quadratic residue code. Thus it is important to find error polynomial. 
     SUMMARY OF THE INVENTION 
     To solve the problems discussed above, the present invention provides a decoding algorithm applicable to all quadratic residue codes. 
     The quadratic residue code decoding algorithm of the present invention uses the digital signal to calculate a plurality of known syndromes, and to set the number of errors if error is encountered and the error correction threshold. The known syndromes are then used to calculate a plurality of unknown syndromes. The known syndromes and unknown syndromes are then treated as known, and the inverse-free Berlekamp-Massey algorithm is used to calculate the error polynomial. 
     A determination is then made as to whether the highest degree of error polynomial matches the number of errors. If it does match the number of errors, then the Chien search algorithm is used to obtain the roots and root number for the error polynomial. If the highest degree does not match the number of errors, then this implies that the error polynomial that has been obtained is incorrect; in this case, a specified value is added to the number of errors and a determination is made as to whether the number of errors exceeds the error-correction threshold. If it is determined that the number of errors does not exceed the error-correction threshold, then a new set of calculations is made to calculate a plurality of unknown syndromes, and the inverse-free Berlekamp-Massey algorithm is again used to determine the error polynomial. If it is determined that the number of errors does exceed the error correction threshold, then the decoding procedure is terminated. 
     After the Chien search algorithm has been used to obtain the roots and root number for the error polynomial, a determination can be made as to whether the error polynomial roots match the number of errors. If it is determined that the error polynomial roots do not match the number of errors, then a specified value is added to the number of errors and a determination is made as to whether the number of errors now exceeds the error-correction threshold. If it is determined that the error polynomial roots do match the number of errors, then the error locations for the error polynomial are found, and adjustments are then made to the digital signal bits corresponding to the error locations so as to obtain the correct code. 
     The quadratic residue code decoding algorithm of the present invention is applicable to all quadratic residue codes, and has been shown by computer verification to provide a level of decoding capability that cannot be achieved with conventional quadratic residue code decoding methods. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a flow chart for decoding (89,45,17) quadratic residue code using the quadratic residue code decoding algorithm of the present invention. 
         FIG. 2  shows a flow chart for decoding (71,36,11) quadratic residue code using the quadratic residue code decoding algorithm of the present invention. 
         FIG. 3  shows a flow chart for decoding (79,40,15) quadratic residue code using the quadratic residue code decoding algorithm of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention will be described in more detail below with reference to the embodiments and drawings. 
     Referring to  FIG. 1  which shows a flow chart for decoding (89,45,17) quadratic residue code using the quadratic residue code decoding algorithm of a first embodiment of the present invention, the decoding process comprises the following steps: 
     A digital signal is provided, and used to calculate a plurality of known syndromes and set the number of errors if error is encountered and the error correction threshold (Step S 100 ). In this step, Equation 1 is used to derive a plurality of known syndromes from the digital signal. It is assumed that the number of errors is v; this value is initially set at 1. The error-correction threshold for the (89,45,17) quadratic residue code is set at 8. 
         S   i   =r (β i )= c (β i )+ e (β i )= e (β i )= e   0   +e   1   β+ . . . +e   88 β 88    (Equation 1) 
     where S i  is a known syndrome, β is the primitive n th  root of unity in the field GF(2 11 ), and n is the code length. 
     The known syndromes are then used to calculate a plurality of unknown syndromes for (89,45,17) quadratic residue code (Step S 110 ). Let Set I={i 1 , i 2 , . . . , i v+1 } and Set J={j 1 , j 2 , . . . , j v+1 } be subsets of {0, 1, . . . , n-1}, and let n be the code length. Matrices X(I) and X(J) of size (v+1)×v are defined as follows: 
     
       
         
           
             
               
                 X 
                  
                 
                   ( 
                   I 
                   ) 
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         Z 
                         1 
                         
                           i 
                           1 
                         
                       
                     
                     
                       
                         Z 
                         2 
                         
                           i 
                           1 
                         
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         
                           i 
                           1 
                         
                       
                     
                   
                   
                     
                       
                         Z 
                         1 
                         
                           i 
                           2 
                         
                       
                     
                     
                       
                         Z 
                         2 
                         
                           i 
                           2 
                         
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         
                           i 
                           2 
                         
                       
                     
                   
                   
                     
                       ⋮ 
                     
                     
                       ⋮ 
                     
                     
                       ⋰ 
                     
                     
                       ⋮ 
                     
                   
                   
                     
                       
                         Z 
                         1 
                         
                           i 
                           v 
                         
                       
                     
                     
                       
                         Z 
                         2 
                         
                           i 
                           v 
                         
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         
                           i 
                           v 
                         
                       
                     
                   
                   
                     
                       
                         Z 
                         1 
                         
                           i 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                     
                       
                         Z 
                         2 
                         
                           i 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         
                           i 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             , 
             
               
 
             
              
             
               
                 X 
                  
                 
                   ( 
                   J 
                   ) 
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         Z 
                         1 
                         
                           j 
                           1 
                         
                       
                     
                     
                       
                         Z 
                         2 
                         j 
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         j 
                       
                     
                   
                   
                     
                       
                         Z 
                         1 
                         
                           j 
                           2 
                         
                       
                     
                     
                       
                         Z 
                         2 
                         
                           j 
                           2 
                         
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         
                           j 
                           2 
                         
                       
                     
                   
                   
                     
                       ⋮ 
                     
                     
                       ⋮ 
                     
                     
                       ⋰ 
                     
                     
                       ⋮ 
                     
                   
                   
                     
                       
                         Z 
                         1 
                         
                           j 
                           v 
                         
                       
                     
                     
                       
                         Z 
                         2 
                         
                           j 
                           v 
                         
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         
                           j 
                           v 
                         
                       
                     
                   
                   
                     
                       
                         Z 
                         1 
                         
                           j 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                     
                       
                         Z 
                         2 
                         
                           j 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                     
                       ⋯ 
                     
                     
                       
                         Z 
                         v 
                         
                           j 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
     One then defines matrix S(I, J)=X(I)X(J) T  and its theorem, where matrix X(J) T  is the transposed matrix of X(J), and S(I, J) is a matrix of size (v+1)×(v+1). 
     Theorem 1: Matrix S(I, J) has the following form: 
     
       
         
           
             
               S 
                
               
                 ( 
                 
                   I 
                   , 
                   J 
                 
                 ) 
               
             
             = 
             
               [ 
               
                 
                   
                     
                       S 
                       
                         
                           i 
                           1 
                         
                         + 
                         
                           j 
                           1 
                         
                       
                     
                   
                   
                     
                       S 
                       
                         
                           i 
                           1 
                         
                         + 
                         
                           j 
                           2 
                         
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       S 
                       
                         
                           i 
                           1 
                         
                         + 
                         
                           j 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       S 
                       
                         
                           i 
                           2 
                         
                         + 
                         
                           j 
                           1 
                         
                       
                     
                   
                   
                     
                       S 
                       
                         
                           i 
                           2 
                         
                         + 
                         
                           j 
                           2 
                         
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       S 
                       
                         
                           i 
                           2 
                         
                         + 
                         
                           j 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋰ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       S 
                       
                         
                           i 
                           v 
                         
                         + 
                         
                           j 
                           1 
                         
                       
                     
                   
                   
                     
                       S 
                       
                         
                           i 
                           v 
                         
                         + 
                         
                           j 
                           2 
                         
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       S 
                       
                         
                           i 
                           v 
                         
                         + 
                         
                           j 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       S 
                       
                         
                           i 
                           
                             v 
                             + 
                             1 
                           
                         
                         + 
                         
                           j 
                           1 
                         
                       
                     
                   
                   
                     
                       S 
                       
                         
                           i 
                           
                             v 
                             + 
                             1 
                           
                         
                         + 
                         
                           j 
                           2 
                         
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       S 
                       
                         
                           i 
                           
                             v 
                             + 
                             1 
                           
                         
                         + 
                         
                           j 
                           
                             v 
                             + 
                             1 
                           
                         
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
     Where the subscript of S is the remainder after dividing by n, and n is the code length. Furthermore, the determinant of matrix S(I, J) is zero, i.e., det(S(I, J))=0. 
     Assuming that matrix S(I, J) contains a plurality of unknown syndromes, then det(S(I, J))=0 can be treated as an unknown syndrome equation, and the coefficient will be composed of the known syndromes. If matrix S(I, J) contains only one unknown syndrome S r   (v) , then S r   (v)  can be derived using the following theorem, where S r   (v)  is an unknown syndrome where the number of errors is assumed to be v. 
     Theorem 2: If matrix S(I, J) contains only one unknown syndrome S r   (v) , then S r   (v)  can be expressed as a fraction. The value of this fraction is determined by successive division after expanding the determinants of two of the matrices contained in matrix S(I, J). If S r   (v)  appears in row i and column j of matrix S(I, J), then 
     
       
         
           
             
               
                 S 
                 r 
                 
                   ( 
                   v 
                   ) 
                 
               
               = 
               
                 
                   det 
                    
                   
                     ( 
                     
                       Δ 
                       0 
                     
                     ) 
                   
                 
                 
                   det 
                    
                   
                     ( 
                     Δ 
                     ) 
                   
                 
               
             
             , 
             , 
           
         
       
     
     where Δ 0  denotes that the location of S r   (v)  at row i and column j within matrix S(I, J) of size (v+1)×(v+1) is replaced by zero, and Δ is the sub-matrix of size v×v formed within S(I, J) by the elimination of row i and column j. 
     With the above theorem, the unknown syndromes for (89,45,17) quadratic residue code can be derived using the following equations:
     Case 0: if no error is encountered, S 3   (0) =0; S 13   (0) =0   Case 1: S 3   (1) =S 1   3 ; S 13   (1) =S 1   13      

     In the following cases, v a) and b) define the sets I and J respectively. Theorems 1 and 2 can then be used to derive the two unknown syndromes S 3  and S 13 . 
     Case 2: 
     a) I 2 ={0, 1, 2}, J 2 ={0, 1, 87} 
     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     2 
                   
                   , 
                   
                     J 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         S 
                         0 
                       
                     
                     
                       
                         S 
                         1 
                       
                     
                     
                       
                         S 
                         2 
                       
                     
                   
                   
                     
                       
                         S 
                         1 
                       
                     
                     
                       
                         S 
                         2 
                       
                     
                     
                       
                         S 
                         3 
                         
                           ( 
                           2 
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         S 
                         87 
                       
                     
                     
                       
                         S 
                         88 
                       
                     
                     
                       
                         S 
                         0 
                       
                     
                   
                 
                 ] 
               
               . 
             
           
         
       
     
         S   3   (2) =( S   1   S   2   S   88   +S   4   S   87 )/( S   1   +S   87 ) 
     b) I 2 ={0, 11, 88}, J 2 ={0, 2, 5} 
     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     2 
                   
                   , 
                   
                     J 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         
                           S 
                           0 
                         
                       
                       
                         
                           S 
                           11 
                         
                       
                       
                         
                           S 
                           88 
                         
                       
                     
                     
                       
                         
                           S 
                           2 
                         
                       
                       
                         
                           S 
                           13 
                           
                             ( 
                             2 
                             ) 
                           
                         
                       
                       
                         
                           S 
                           1 
                         
                       
                     
                     
                       
                         
                           S 
                           5 
                         
                       
                       
                         
                           S 
                           16 
                         
                       
                       
                         
                           S 
                           4 
                         
                       
                     
                   
                   ] 
                 
                 . 
                 
                   
 
                 
                  
                 
                   S 
                   13 
                   
                     ( 
                     2 
                     ) 
                   
                 
               
               = 
               
                 
                   ( 
                   
                     
                       
                         S 
                         2 
                       
                        
                       
                         S 
                         16 
                       
                        
                       
                         S 
                         88 
                       
                     
                     + 
                     
                       
                         S 
                         2 
                       
                        
                       
                         S 
                         4 
                       
                        
                       
                         S 
                         
                           11 
                           + 
                         
                       
                        
                       
                         S 
                         1 
                       
                        
                       
                         S 
                         5 
                       
                        
                       
                         S 
                         11 
                       
                     
                   
                   ) 
                 
                 / 
                 
                   ( 
                   
                     
                       S 
                       5 
                     
                     + 
                     
                       S 
                       88 
                     
                   
                   ) 
                 
               
             
           
         
       
     
     Case 3:  
     a) I 3 ={0, 1, 87, 88}, J 3 ={0, 1, 2, 10} 
     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     3 
                   
                   , 
                   
                     J 
                     3 
                   
                 
                 ) 
               
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         S 
                         0 
                       
                     
                     
                       
                         S 
                         1 
                       
                     
                     
                       
                         S 
                         87 
                       
                     
                     
                       
                         S 
                         88 
                       
                     
                   
                   
                     
                       
                         S 
                         1 
                       
                     
                     
                       
                         S 
                         2 
                       
                     
                     
                       
                         S 
                         88 
                       
                     
                     
                       
                         S 
                         0 
                       
                     
                   
                   
                     
                       
                         S 
                         2 
                       
                     
                     
                       
                         S 
                         3 
                         
                           ( 
                           3 
                           ) 
                         
                       
                     
                     
                       
                         S 
                         0 
                       
                     
                     
                       
                         S 
                         1 
                       
                     
                   
                   
                     
                       
                         S 
                         10 
                       
                     
                     
                       
                         S 
                         11 
                       
                     
                     
                       
                         S 
                         8 
                       
                     
                     
                       
                         S 
                         9 
                       
                     
                   
                 
                 ] 
               
               . 
             
           
         
       
     
     b) I 3 ={8, 9, 10, 13}, J 3 ={0, 8, 59, 71} 
     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     3 
                   
                   , 
                   
                     J 
                     3 
                   
                 
                 ) 
               
             
             = 
             
               [ 
               
                 
                   
                     
                       S 
                       8 
                     
                   
                   
                     
                       S 
                       9 
                     
                   
                   
                     
                       S 
                       10 
                     
                   
                   
                     
                       S 
                       13 
                       
                         ( 
                         3 
                         ) 
                       
                     
                   
                 
                 
                   
                     
                       S 
                       16 
                     
                   
                   
                     
                       S 
                       17 
                     
                   
                   
                     
                       S 
                       18 
                     
                   
                   
                     
                       S 
                       21 
                     
                   
                 
                 
                   
                     
                       S 
                       67 
                     
                   
                   
                     
                       S 
                       68 
                     
                   
                   
                     
                       S 
                       69 
                     
                   
                   
                     
                       S 
                       72 
                     
                   
                 
                 
                   
                     
                       S 
                       79 
                     
                   
                   
                     
                       S 
                       80 
                     
                   
                   
                     
                       S 
                       81 
                     
                   
                   
                     
                       S 
                       84 
                     
                   
                 
               
               ] 
             
           
         
       
     
     Case 4:  
     a) I 4 ={1, 2, 3, 10, 32}, J 4 ={0, 7, 8, 77, 78} 
     b) I 4 ={0, 1, 2, 87, 88}, J 4 ={0, 1, 2, 3, 11} 
     Case 5: 
     a) I 5   1 ={1, 16, 17, 20, 39, 57}, J 5   1 ={0, 33, 52, 68, 71, 72} 
     I 5   2 ={0, 1, 8, 39, 49, 72}, J 5   2 ={0, 1, 8, 39, 49, 84} 
     If there are 5 errors, then 1 set of (I, J) is not sufficient to define the unknown syndromes S 3   (5)  for all situations where the number of errors is 5. Model testing using a computer has shown that 2 sets of (I, J) are needed to define the unknown syndromes S 3   (5)  for all situations where the number of errors is 5. 
     b) I 5 ={0, 1, 2, 3, 4, 5}, J 5 ={0, 1, 2, 8, 87, 88} 
     If the unknown syndromes S 3   (5)  obtained in a) are treated as known syndromes, then Theorems 1 and 2 can be used to calculate the two unknown syndromes S 13   (5) . 
     Case 6:  
     a) I 6   1 ={1, 2, 3, 4, 9, 71, 87}, J 6   1 ={0, 1, 2, 7, 8, 86, 87} 
     I 6   2 ={1, 2, 3, 4, 5, 11, 87}, J 6   2 ={0, 1, 5, 6, 7, 86, 87} 
     I 6   3 ={1, 2, 3, 4, 9, 87, 88}, J 6   3 ={0, 1, 2, 7, 8, 46, 86} 
     If there are 6 errors, then 1 set of (I, J) is not sufficient to define the unknown syndromes S 3   (6)  for all situations where the number of errors is 6. Model testing using a computer has shown that 3 sets of (I, J) are needed to define the unknown syndromes for all situations where the number of errors is 6. For all three sets of (I, J), the determinant expansion takes the form of a non-linear S 3   (6)  polynomial; using Theorem 2, it can be determined that these determinants are equal to zero. In other words, the three polynomials have similar linear factors. Therefore, if the linear factors of these three polynomials can be determined, it will then be possible to define a single value for S 3   (6) . In b), S 3   (6)  can be treated as a known value. 
     b) I 6   1 ={0, 1, 2, 3, 4, 5, 6}, J 6   1 ={0, 1, 2, 3, 7, 87, 88} 
     If the unknown syndromes S 3   (6)  obtained in a) are treated as known syndromes, then Theorems 1 and 2 can be used to calculate the two unknown syndromes S 13   (6) . 
     Case 7: 
     a) I 7   1 ={2, 3, 4, 6, 7, 8, 14, 20}, J 7   1 ={0, 2, 4, 14, 65, 85, 86, 87}, I 7   2 ={1, 2, 3, 4, 6, 8, 14, 87}, J 7   2 ={0, 2, 3, 4, 6, 8, 86, 87}, I 7   3 ={1, 2, 3, 4, 9, 10, 71, 87}, J 7   3={0, 1, 2, 7, 8, 46, 86, 87}   
     The situation here is similar to the situation with 6 errors. Three sets of (I, J) are needed to define the unknown syndromes S 3   (7)  for all situations where the number of errors is 7. Once the unknown syndromes S 3   (7)  have been defined, then the unknown syndromes S 3   (7)  in b) can be treated as a known value. 
     b) I 7   1 ={0, 1, 3, 6, 8, 17, 40, 84}, J 7   1 ={0, 4, 5, 6, 8, 17, 39, 47}, I 7   2 ={0, 1, 3, 6, 8, 17, 40, 88}, J 7   2 ={0, 4, 5, 6, 8, 17, 47, 88}, I 7   3 ={1, 2, 4, 7, 9, 18, 42, 87}, J 7   3 ={0, 4, 5, 7, 38, 46, 83, 87} 
     If, after expansion, the determinants of the three sets of (I, J) are treated as zero, then three linear equations can be derived for S 13   (7) . A single value can be determined for S 13   (7)  using any one of these equations. 
     Case 8: 
     a) I 8   1 ={1, 2, 3, 6, 17, 20, 45, 84, 87}, J 8   1 ={0, 3, 4, 5, 8, 19, 22, 47, 86}, I 8   2 ={1, 3, 5, 6, 7, 11, 17, 39, 84}, J 8   2 ={0, 1, 3, 5, 11, 17, 39, 84, 86}, I 8   3 ={1, 2, 3, 4, 5, 6, 9, 20, 87}, J 8   3 ={0, 1, 2, 3, 5, 19, 44, 86, 87}, I 8   4 ={6, 7, 8, 9, 40, 53, 56, 57, 72}, J 8   4 ={0, 15, 16, 38, 39, 40, 41, 72, 81} 
     The situation here is similar to the situation with 7 errors. Four sets of (I, J) are needed to define the unknown syndromes S 3   (8)  for all situations where the number of errors is 8. Once the unknown syndromes S 3   (8)  have been defined, then the unknown syndromes S 3   (8)  in b) can be treated as a known value. 
     b) I 8   1 ={2, 6, 7, 8, 9, 18, 53, 85, 87}, J 8   1 ={0, 2, 3, 4, 14, 16, 38, 82, 83}, I 8   2 ={0, 1, 2, 3, 4, 5, 6, 20, 87}, J 8   2 ={0, 1, 2, 3, 4, 5, 8, 44, 87}, I 8   3 ={1, 2, 3, 4, 5, 6, 9, 20, 45}J 8   3 ={0, 1, 2, 3, 4, 5, 19, 44, 86} 
     If, after expansion, the determinants of the three sets of (I, J) are treated as zero, then three linear equations can be derived for S 13   (8) . A single value can be determined for S 13   (3)  using any one of these equations. 
     Using a plurality of known syndromes and a plurality of unknown syndromes that are treated as known, the inverse-free Berlekamp-Massey algorithm can be used to calculate the error polynomial (Step S 120 ). In this step, a plurality of known syndromes and a plurality of unknown syndromes are used as known input values, and the inverse-free Berlekamp-Massey algorithm (which is able to derive the cyclic code error polynomial in an efficient manner) is used to calculate the error polynomial. The steps in the inverse-free Berlekamp-Massey algorithm are shown below:
     Step 1) The initial values are set as k=1, r (0) =1, C (0) (x)=1, A (0) (x)=1 and l (0) =1   Step 2) Calculate the difference   

     
       
         
           
             
               Δ 
               
                 ( 
                 k 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   j 
                   = 
                   1 
                 
                 
                   l 
                   
                     ( 
                     
                       k 
                       - 
                       1 
                     
                     ) 
                   
                 
               
                
               
                 
                   c 
                   
                     j 
                     - 
                     1 
                   
                   
                     ( 
                     
                       k 
                       - 
                       1 
                     
                     ) 
                   
                 
                  
                 
                   S 
                   
                     k 
                     - 
                     j 
                     + 
                     1 
                   
                 
               
             
           
         
       
         
         Step 3) Calculate the error polynomial 
       
    
         C   (k) ( x )= r   (k−1)   C   (k−1) ( x )−Δ (k)   A   (k−1) ( x )· x        Step 4) Substitution of auxiliary variables A (k) (x), A (k) , 1 (k)  and r (k)      
     
       
         
           
             
               
                 A 
                 
                   ( 
                   k 
                   ) 
                 
               
                
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                             
                            
                           
                             
                               x 
                               · 
                               
                                 
                                   A 
                                   
                                     ( 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                             , 
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 
                                   Δ 
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                               
                               = 
                               
                                 
                                   0 
                                    
                                   
                                       
                                   
                                    
                                   or 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                    
                                   
                                     l 
                                     
                                       ( 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                 
                                 &gt; 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                             
                            
                           
                             
                               
                                 C 
                                 
                                   ( 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                                
                               
                                 ( 
                                 x 
                                 ) 
                               
                             
                             , 
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 
                                   Δ 
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                               
                               ≠ 
                               
                                 0 
                                  
                                 
                                     
                                 
                                  
                                 or 
                                  
                                 
                                     
                                 
                                  
                                 2 
                                  
                                 
                                   l 
                                   
                                     ( 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                               ≤ 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       l 
                       
                         ( 
                         k 
                         ) 
                       
                     
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                 
                 = 
                 
                   { 
                   
                     
                       
                         
                           
                             
                                 
                                
                               
                                 
                                   l 
                                   
                                     ( 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 , 
                                 
                                   
                                     if 
                                      
                                     
                                         
                                     
                                      
                                     
                                       Δ 
                                       
                                         ( 
                                         k 
                                         ) 
                                       
                                     
                                   
                                   = 
                                   
                                     
                                       0 
                                        
                                       
                                           
                                       
                                        
                                       or 
                                        
                                       
                                           
                                       
                                        
                                       2 
                                        
                                       
                                         l 
                                         
                                           ( 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                           ) 
                                         
                                       
                                     
                                     &gt; 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                                 
                                
                               
                                 
                                   k 
                                   - 
                                   
                                     l 
                                     
                                       ( 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                 
                                 , 
                                 
                                   
                                     if 
                                      
                                     
                                         
                                     
                                      
                                     
                                       Δ 
                                       
                                         ( 
                                         k 
                                         ) 
                                       
                                     
                                   
                                   ≠ 
                                   
                                     0 
                                      
                                     
                                         
                                     
                                      
                                     or 
                                      
                                     
                                         
                                     
                                      
                                     2 
                                      
                                     
                                       l 
                                       
                                         ( 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                         ) 
                                       
                                     
                                   
                                   ≤ 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                         
                       
                        
                       
                         
 
                       
                        
                       
                         
                           r 
                           
                             ( 
                             k 
                             ) 
                           
                         
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                                 
                                
                               
                                 
                                   r 
                                   
                                     ( 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 , 
                                 
                                   
                                     if 
                                      
                                     
                                         
                                     
                                      
                                     
                                       Δ 
                                       
                                         ( 
                                         k 
                                         ) 
                                       
                                     
                                   
                                   = 
                                   
                                     
                                       0 
                                        
                                       
                                           
                                       
                                        
                                       or 
                                        
                                       
                                           
                                       
                                        
                                       2 
                                        
                                       
                                         l 
                                         
                                           ( 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                           ) 
                                         
                                       
                                     
                                     &gt; 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                                 
                                
                               
                                 
                                   Δ 
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                 , 
                                 
                                   
                                     if 
                                      
                                     
                                         
                                     
                                      
                                     
                                       Δ 
                                       
                                         ( 
                                         k 
                                         ) 
                                       
                                     
                                   
                                   ≠ 
                                   
                                     0 
                                      
                                     
                                         
                                     
                                      
                                     or 
                                      
                                     
                                         
                                     
                                      
                                     2 
                                      
                                     
                                       l 
                                       
                                         ( 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                         ) 
                                       
                                     
                                   
                                   ≤ 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
             
           
         
       
         
         Step 5) Move on to the next step: k=k+1. If k≦2t, then go back to Step 2), otherwise the process is completed. 
       
    
     C (k) (x) denotes the error polynomial at the k th  stage, Δ (k)  if the difference calculated from known syndrome S k , and A (k) (x), A (k) , l (k)  and r (k)  are auxiliary variables for determining the error polynomial at the k th  stage. 
     One then moves on to determine whether the highest degree of the error polynomial conforms to the number of errors (Step S 130 ). In this step, the equation deg(σ(x))=v is used to determine whether the highest degree of the polynomial is the same as the number of errors; deg(σ(x)) is the highest degree of the error polynomial, and, as noted above, v is the number of errors. 
     If it is determined that the highest degree of the error polynomial is the same as the number of errors, then one moves on to calculate the root and root number of the error polynomial (Step S 140 ). In this step, the error polynomial root and root number are calculated using the error polynomial and the Chien search algorithm (the Chien search algorithm is used for finding roots of polynomials over finite fields; it produces better results than other algorithms when finding roots of error polynomials). 
     If it is determined that the highest degree of the error polynomial is not the same as the number of errors, then a specified value is added to the number of errors and a determination is made as to whether the number of errors now exceeds the error-correction threshold (Step S 150 ). In this step, the specified value is set at 1, and the error-correction threshold for the (89,45,17) quadratic residue code is set at 8. When the number of errors exceeds the error-correction threshold, this implies that no further adjustment of the digital signal can be performed, and the algorithm is terminated. If the number of errors has not yet exceeded the error-correction threshold, then one goes back to using a plurality of known syndromes to calculate a plurality of unknown syndromes for the (89,45,17) quadratic residue code (Step S 110 ). 
     The next step is to determine whether the root number obtained for the error polynomial matches the number of errors (Step S 160 ). First, the root number is calculated; then, a determination is made as to whether the number that has been obtained matches the number of errors. The formula used in this stage is u=v, where u is the root number, and v is the number of errors. 
     If it is determined that the root number matches the number of errors, then the next step is to identify the error locations for the error polynomial, and to adjust the values of the error locations (Step S 170 ). In this step, the error polynomial is used to determine the locations where errors have occurred in the digital (input) signal; the values at these locations are then adjusted to obtain correct values. 
     If, on the other hand, it is determined that the root number does not match the number of errors, then one goes back to adding a specified value to the number of errors and determining whether the number of errors now exceeds the error-correction threshold (Step S 150 ). 
     A second embodiment of the quadratic residue code decoding algorithm of the present invention, in the decoding of the (71,36,11) quadratic residue code, is illustrated in  FIG. 2 . The decoding process comprises the following steps: 
     A digital signal is provided, and used to calculate a plurality of known syndromes and set the number of errors if error is encountered and the error correction threshold (Step S 200 ). During this step, Equation 2 is used to derive a plurality of known syndromes from the digital signal. It is assumed that the number of errors is v; this value is initially set at 1. The error-correction threshold for the (71,36,11) quadratic residue code is set at 5. 
         S   i   =r (β i )= e (β i )= e   0   +e   1 β 1   + . . . +e   n−1 β n−1    (Equation 2) 
     where S i  is a known syndrome, and β is the primitive n th  root of unity in the field GF(2 35 ) 
     The known syndromes are then used to calculate a plurality of unknown syndromes for the (71,36,11) quadratic residue code (Step S 210 ). The method used to calculate the unknown syndromes S 7  for the (71,36,11) quadratic residue code is described below.
     Case 0: S 7   (0) =0   Case 1: S 7   (1) =S 1   7      Case 2: I 2 ={0, 1, 2}, J 2 ={0, 1, 5}   

     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     2 
                   
                   , 
                   
                     J 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         
                           S 
                           0 
                         
                       
                       
                         
                           S 
                           1 
                         
                       
                       
                         
                           S 
                           2 
                         
                       
                     
                     
                       
                         
                           S 
                           1 
                         
                       
                       
                         
                           S 
                           2 
                         
                       
                       
                         
                           S 
                           3 
                         
                       
                     
                     
                       
                         
                           S 
                           5 
                         
                       
                       
                         
                           S 
                           6 
                         
                       
                       
                         
                           S 
                           7 
                           
                             ( 
                             2 
                             ) 
                           
                         
                       
                     
                   
                   ] 
                 
                 . 
                 
                   
 
                 
                  
                 
                   S 
                   7 
                   
                     ( 
                     2 
                     ) 
                   
                 
               
               = 
               
                 
                   ( 
                   
                     
                       
                         S 
                         1 
                       
                        
                       
                         S 
                         6 
                       
                     
                     + 
                     
                       
                         S 
                         2 
                       
                        
                       
                         S 
                         5 
                       
                     
                   
                   ) 
                 
                 + 
                 
                   ( 
                   
                     
                       S 
                       3 
                     
                      
                     
                       
                         S 
                         5 
                       
                       / 
                       
                         S 
                         1 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
         
         Case 3: I 3 ={0, 1, 2, 3}, J 3 ={0, 1, 2, 4} 
       
    
     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     3 
                   
                   , 
                   
                     J 
                     3 
                   
                 
                 ) 
               
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         S 
                         0 
                       
                     
                     
                       
                         S 
                         1 
                       
                     
                     
                       
                         S 
                         2 
                       
                     
                     
                       
                         S 
                         3 
                       
                     
                   
                   
                     
                       
                         S 
                         1 
                       
                     
                     
                       
                         S 
                         2 
                       
                     
                     
                       
                         S 
                         3 
                       
                     
                     
                       
                         S 
                         4 
                       
                     
                   
                   
                     
                       
                         S 
                         2 
                       
                     
                     
                       
                         S 
                         3 
                       
                     
                     
                       
                         S 
                         4 
                       
                     
                     
                       
                         S 
                         5 
                       
                     
                   
                   
                     
                       
                         S 
                         4 
                       
                     
                     
                       
                         S 
                         5 
                       
                     
                     
                       
                         S 
                         7 
                         
                           ( 
                           3 
                           ) 
                         
                       
                     
                     
                       
                         S 
                         8 
                       
                     
                   
                 
                 ] 
               
               . 
             
           
         
       
         
         Case 4: I 4 ={0, 1, 2, 4, 7}, J 4 ={0, 1, 2, 8, 36} 
         Case 5: I 5   1 ={0, 1, 2, 4, 7, 24 }, J 5   1 ={0, 1, 3, 5, 8, 36} 
       
    
     I 5   2 ={3, 4, 5, 12, 15, 45}, J 5   2 ={0, 3, 4, 15,33, 45} 
     If there are 5 errors, then 1 set of (I, J) is not sufficient to define the unknown syndromes for S 7   (5)  for all situations where the number of errors is 5. If, after expansion, the determinants of the two matrices S(I 5   1 , J 5   1 ) and S(I 5   2 , J 5   2 ) are zero, then the following cubic equations can be derived for the two unknown syndromes S 7   (5) : f 1 (S 7   (5) )=0, and g 1 (S 7   (5) )=0, where the coefficient is formed from known syndromes. Let F 1 (S 7   (5) )=gcd(f 1 (S 7   (5) ),g 1 (S 7   (5) )), then F 1 (S 7   (5) ) is a quadratic polynomial in all cases where the number of errors is 5, and F 1 (S 7   (5) )=0 can be used to derive the unknown syndromes S 7   (5) . 
     Using a plurality of known syndromes and a plurality of unknown syndromes that are treated as known, the inverse-free Berlekamp-Massey algorithm can be used to calculate the error polynomial (Step S 220 ). In this step, a plurality of known syndromes and a plurality of unknown syndromes are used as known input values, and the inverse-free Berlekamp-Massey algorithm (which is able to derive the cyclic code error polynomial in an efficient manner) is used to calculate the error polynomial. The steps in the inverse-free Berlekamp-Massey algorithm are the same as those outlined in Step S 120  of the (89,45,17) quadratic residue code embodiment. 
     One then moves on to determine whether the highest degree of the error polynomial matches the number of errors (Step S 230 ). In this step, the equation deg(σ(x))=v is used to determine whether the highest degree of the polynomial matches the number of errors; deg(σ(x)) is the highest degree of the error polynomial, and, as noted above, v is the number of errors. 
     If it is determined that the highest degree of the error polynomial is the same as the number of errors, then one moves on to calculate the root and root number of the error polynomial (Step S 240 ). In this step, the error polynomial root and root number are calculated using the error polynomial and the Chien search algorithm (the Chien search algorithm is used for finding roots of polynomials over finite fields; it produces better results than other algorithms when finding roots of error polynomials). 
     If it is determined that the highest degree of the error polynomial is not the same as the number of errors, then a specified value is added to the number of errors and a determination is made as to whether the number of errors now exceeds the error-correction threshold (Step S 250 ). In this step, the specified value is set at 1, and the error-correction threshold for the (71,36,11) quadratic residue code is set at 5. When the number of errors exceeds the error-correction threshold, this implies that no further adjustment of the digital signal can be performed, and the algorithm is terminated. If the number of errors has not yet exceeded the error-correction threshold, then one goes back to using a plurality of known syndromes to calculate a plurality of unknown syndromes for the (71,36,11) quadratic residue code (Step S 210 ). 
     The next step is to determine whether the root number obtained for the error polynomial matches the number of errors (Step S 260 ). First, the root number is calculated; then, a determination is made as to whether the number that has been obtained matches the number of errors. The formula used in this stage is u=v, where u is the root number, and v is the number of errors. 
     If it is determined that the root number matches the number of errors, then the next step is to identify the error locations for the error polynomial, and to adjust the values of the error locations (Step S 270 ). In this step, the error polynomial is used to determine the locations where errors have occurred in the digital (input) signal; the values at these locations are then adjusted to obtain correct values. 
     If, on the other hand, it is determined that the root number does not match the number of errors, then one goes back to adding a specified value to the number of errors and determining whether the number of errors now exceeds the error-correction threshold (Step S 250 ). 
     A third embodiment of the quadratic residue code decoding algorithm of the present invention, in the decoding of the (79,40,15) quadratic residue code, is illustrated in  FIG. 3 . The decoding process comprises the following steps: 
     A digital signal is provided, and used to calculate a plurality of known syndromes and set the number of errors if error is encountered and the error correction threshold (Step S 300 ). During this step, Equation 3 is used to derive a plurality of known syndromes from the digital signal. It is assumed that the number of errors is v; this value is initially set at 1. The error-correction threshold for the (79,40,15) quadratic residue code is set at 7. 
         S   i   =r (β i )= e (β i )= e   0   +e   1 β 1   + . . . +e   n−1 β n−1    (Equation 3) 
     where S i  is a known syndrome, and β is the primitive n th  root of unity in the field GF(2 39 ). 
     The known syndromes are then used to calculate a plurality of unknown syndromes for the (79,40,15) quadratic residue code (Step  310 ). The method used to calculate the unknown syndromes S 3  for the (79,40,15) quadratic residue code is described below.
     Case 0: S 3   (0) =0   Case 1: S 3   (1) =S 1   3      Case 2: I 2 ={0, 1, 2}, J 2 ={0, 1, 8}   

     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     2 
                   
                   , 
                   
                     J 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         
                           S 
                           0 
                         
                       
                       
                         
                           S 
                           1 
                         
                       
                       
                         
                           S 
                           2 
                         
                       
                     
                     
                       
                         
                           S 
                           1 
                         
                       
                       
                         
                           S 
                           2 
                         
                       
                       
                         
                           S 
                           3 
                           
                             ( 
                             2 
                             ) 
                           
                         
                       
                     
                     
                       
                         
                           S 
                           8 
                         
                       
                       
                         
                           S 
                           9 
                         
                       
                       
                         
                           S 
                           10 
                         
                       
                     
                   
                   ] 
                 
                 . 
                 
                   
 
                 
                  
                 
                   S 
                   3 
                   
                     ( 
                     2 
                     ) 
                   
                 
               
               = 
               
                 
                   
                     S 
                     1 
                   
                    
                   
                     S 
                     2 
                   
                 
                 + 
                 
                   ( 
                   
                     
                       
                         S 
                         1 
                       
                        
                       
                         S 
                         10 
                       
                     
                     + 
                     
                       
                         S 
                         2 
                       
                        
                       
                         
                           S 
                           9 
                         
                         / 
                         
                           S 
                           8 
                         
                       
                     
                   
                   ) 
                 
               
             
           
         
       
         
         Case 3: I 3 ={0, 1, 2, 3}, J 3 ={0, 8, 18, 19} 
       
    
     
       
         
           
             
               S 
                
               
                 ( 
                 
                   
                     I 
                     3 
                   
                   , 
                   
                     J 
                     3 
                   
                 
                 ) 
               
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         S 
                         0 
                       
                     
                     
                       
                         S 
                         1 
                       
                     
                     
                       
                         S 
                         2 
                       
                     
                     
                       
                         S 
                         3 
                         
                           ( 
                           3 
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         S 
                         8 
                       
                     
                     
                       
                         S 
                         9 
                       
                     
                     
                       
                         S 
                         10 
                       
                     
                     
                       
                         S 
                         11 
                       
                     
                   
                   
                     
                       
                         S 
                         18 
                       
                     
                     
                       
                         S 
                         19 
                       
                     
                     
                       
                         S 
                         20 
                       
                     
                     
                       
                         S 
                         21 
                       
                     
                   
                   
                     
                       
                         S 
                         19 
                       
                     
                     
                       
                         S 
                         20 
                       
                     
                     
                       
                         S 
                         21 
                       
                     
                     
                       
                         S 
                         22 
                       
                     
                   
                 
                 ] 
               
               . 
             
           
         
       
         
         Case 4: I 4 ={0,1, 2, 3, 13}, J 4 ={0, 8, 18, 19, 49} 
         Case 5: I 5   1 ={2, 3, 4, 19, 25, 73}, J 5   1 ={0, 6, 7, 17, 19, 48} 
         Case 6: I 6   1 ={1, 2, 3, 4, 5, 64, 72}, J 6   1 ={0, 1, 8, 17, 18, 19, 20} 
       
    
     I 6   2 ={0, 1, 2, 3, 16, 22, 42}, J 6   2 ={0, 2, 3, 9, 10, 20, 22} 
     If there are 6 errors, then 1 set of (I, J) is not sufficient to define the unknown syndromes S 3   (6)  for all situations where the number of errors is 6. For two sets of (I, J), the determinant expansion takes the form of a non-linear S 3   (6)  polynomial; using Theorem 2, as described in the (89,45,17) quadratic residue code embodiment, it can be determined that these determinants are equal to zero. In other words, the two polynomials have linear factors that are at least similar. Euclid&#39;s algorithm can then be used to find the highest common factor of the two polynomials. Computer modeling has shown that the two sets can be used to derive a linear factor which can be used to define a single value for S 3   (6)  for all cases where there are 6 errors.
     Case 7: I 7   1 ={0, 1, 2, 3, 4, 5, 64, 72}, J 7   1 ={0, 1, 8, 16, 17, 18, 19, 20}, I 7   2 ={0 1, 2, 3, 4, 16, 18, 24}, J 7   2 ={0, 1, 2, 8, 16, 18, 20, 22}   

     The situation here is similar to the situation with 6 errors. Once the determinants of S(I 7   1 , J 7   1 ) and S(I 7   2 , J 7   2 ) have been expanded, one obtains the following polynomials for S 3   (7) : f 2 (S 3   (7) ), an 83-dimensional polynomial, and g 2 (S 3   (7) ), a 153-dimensional polynomial. Euclid&#39;s algorithm can then be used to find the highest common factor of the two polynomials: F 2 (S 3   (7) )=gcd(f 2 (S 3   (7) ), g 2 (S 3   (7) )). The code obtained from computer modeling shows that the F 2 (S 3   (7) ) polynomials are all linear polynomials. Using Theorem 1 from the (89,45,17) quadratic residue code embodiment, one can determine that f 2 (S 3   (7) )=0 and g 2 (S 3   (7) )=0, so F 2 (S 3   (7) ) is also 0. It is therefore also possible to derive a single definition for all primitive unknown syndromes S 3   (7)  where the number of errors is 7. 
     Using a plurality of known syndromes and a plurality of unknown syndromes that are treated as known, the inverse-free Berlekamp-Massey algorithm can be used to calculate the error polynomial (Step S 320 ). In this step, a plurality of known syndromes and a plurality of unknown syndromes are used as known input values, and the inverse-free Berlekamp-Massey algorithm (which is able to derive the cyclic code error polynomial in an efficient manner) is used to calculate the error polynomial. The steps in the inverse-free Berlekamp-Massey algorithm are the same as those outlined in Step S 120  of the (89,45,17) quadratic residue code embodiment. 
     One then moves on to determine whether the highest degree of the error polynomial matches the number of errors (Step S 330 ). In this step, the equation deg(σ(x))=v is used to determine whether the highest degree of the polynomial matches the number of errors; deg(σ(x)) is the highest degree of the error polynomial, and, as noted above, v is the number of errors. 
     If it is determined that the highest degree of the error polynomial is the same as the number of errors, then one moves on to calculate the root and root number of the error polynomial (Step S 340 ). In this step, the error polynomial root and root number are calculated using the error polynomial and the Chien search algorithm (the Chien search algorithm is used for finding roots of polynomials over finite fields; it produces better results than other algorithms when finding roots of error polynomials). 
     If it is determined that the highest degree of the error polynomial is not the same as the number of errors, then a specified value is added to the number of errors and a determination is made as to whether the number of errors now exceeds the error-correction threshold (Step S 350 ). In this step, the specified value is set at 1, and the error-correction threshold for the (79,40,15) quadratic residue code is set at 7. When the number of errors exceeds the error-correction threshold, this implies that no further adjustment of the digital signal can be performed, and the algorithm is terminated. If the number of errors has not yet exceeded the error-correction threshold, then one goes back to using a plurality of known syndromes to calculate a plurality of unknown syndromes for the (79,40,15) quadratic residue code (Step S 310 ). 
     The next step is to determine whether the root number obtained for the error polynomial is in conformity with the number of errors (Step S 360 ). First, the root number is calculated; then, a determination is made as to whether the number that has been obtained matches the number of errors. The formula used in this stage is u=v, where u is the root number, and v is the number of errors. 
     If it is determined that the root number matches the number of errors, then the next step is to identify the error locations for the error polynomial, and to adjust the values of the error locations (Step S 370 ). In this step, the error polynomial is used to determine the locations where errors have occurred in the digital (input) signal; the values at these locations are then adjusted to obtain correct values. 
     If, on the other hand, it is determined that the root number does not match the number of errors, then one goes back to adding a specified value to the number of errors and determining whether the number of errors now exceeds the error-correction threshold (Step S 350 ). 
     The preferred embodiments of the present invention have been disclosed in the examples. However the examples should not be construed as a limitation on the actual applicable scope of the invention, and as such, all modifications and alterations without departing from the spirits of the invention and appended claims shall remain within the protected scope and claims of the invention.