PATENT ABSTRACT
The invention relates to a Reed-Solomon decoder and to a method of soft decision decoding of Reed-Solomon codes, wherein a syndrome polynomial, an erasure polynomial, and a modified syndrome polynomial are computed on-the-fly in parallel by iteratively updating coefficients of these polynomials.

PATENT DESCRIPTION
FIELD OF THE INVENTION 
     This application claims the benefit, under 35 U.S.C. § 365 of International Application PCT/EP03/04689, filed May 6, 2003, which was published in accordance with PCT Article 21(2) on Nov. 20, 2003 in English and which claims the benefit of European patent application No. 02010430.3, filed May 8, 2002. 
     The present invention pertains generally to error detection/correction and more particularly to systems and methods used in Reed-Solomon decoders. 
     BACKGROUND AND PRIOR ART 
     A commonly used error correcting technique is the Reed-Solomon error correcting code. For an overview and for applications of Reed-Solomon codes reference is made to “Reed-Solomon Codes and Their Applications”, Stephen B. Wicker, Vijay R. Bhargava, IEEE Press, 1994 and “Digital Communications, Fundamentals and Applications”, Second Edition, Bernard Sklar, Prentice Hall PTR, 2001. 
     U.S. Pat. No. 5,517,509 shows a Reed-Solomon decoder in the form of a Euclid&#39;s algorithm operation circuit in which division polynomials are repeatedly divided by residues resulting from the division process of dividend polynomials and division polynomials until the degree of residues of the division process satisfies a prescribed condition. 
     The Euclid&#39;s algorithm operation circuit comprises register groups for storing dividend polynomials and division polynomials, respectively, a feedback loop for storing residues resulting from the division process of the dividend polynomials by the division polynomials, a shifter for shifting contents of registers, and an exchanger for exchanging coefficients of the dividend polynomials with coefficients of the division polynomials. 
     The decoder comprises a syndrome operator for calculating syndromes from received code-words, an erasure locator generator for generating erasure locator data from erasure locator flags synchronous with received code-words, a modified syndrome generator for generating modified syndromes, an erasure locator polynomial generator for generating erasure locator polynomials from the erasure locator data, a Euclid&#39;s algorithm operation circuit for obtaining error locator polynomials and error value polynomials, a Chien searcher for obtaining error locations and error values and a correction processor for correcting errors of the received code-word. The modified syndrome generator and the erasure locator polynomial generator are used jointly with the Euclid&#39;s algorithm operation circuit. 
     Other approaches for implementing a Reed-Solomon decoder are know from U.S. Pat. Nos. 5,991,911, 6,032,283, 6,304,994 B1, 5,537,426 and EP 0 821 493 A1 and EP 0 942 421 A1. 
     Usually the computation of the modified syndrome polynomial is performed by computation of the product of the syndrome and erasure polynomials. This computation requires additional cycles and computation time to obtain the modified syndrome polynomial. 
     It is therefore an object of the present invention to provide for a method of soft-decision decoding of Reed-Solomon codes where the calculation of the modified syndrome polynomial does not require additional cycles. 
     SUMMARY OF THE INVENTION 
     The object of the invention is solved basically by applying the features laid down in the independent claims. Preferred embodiments of the invention are given in the dependent claims. 
     The present invention enables to minimize the computation time for soft-decision decoding of Reed-Solomon codes by parallel on-the-fly computation of the syndrome and erasure polynomials as well as the modified syndrome polynomial. In other words, the invention enables to perform the calculation of the modified syndrome polynomial before the computation of the syndrome and erasure polynomials has been completed. 
     The present invention is particularly advantageous in that it enables to compute the modified syndrome polynomials on-the-fly with the incoming symbols. Therefore a separate computation step usually referred to as polynomial expansion can be omitted. 
     It is a further advantage that after correction a direct update of the modified syndromes can be performed without computation of the product of the syndrome and erasure polynomials. This results in a reduction of the overall computation time and hardware requirements. 
     The general idea of the invention is to reduce the number of cycles needed to compute the modified syndrome. To obtain the modified syndrome polynomial a multiplication of the erasure and syndrome polynomial has to be done. The complexity of the conventional serial algorithm for that is
 
 c=r ( l+ 1)− l ( l +1)/2,
 
where r is the number of parity symbols in a RS code word and l is the number of erasures in a code word.
 
     The complexity of the conventional serial-parallel algorithm is
 
 c=l+ 1.
 
     The general idea of the invention is to compute the modified syndrome on-the-fly. Therefore the present method does not need any additional cycles for computation of the modified syndrome, which saves computation power and time. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a block diagram of a hardware implementation of a known on-the-fly syndrome computation, 
         FIG. 2  shows a block diagram of a hardware implementation of a known on-the-fly computation of the erasure polynomial, 
         FIG. 3  is illustrative of a flowchart of an embodiment for on-the-fly computation of the modified syndrome polynomial, 
         FIG. 4  is a block diagram of a hardware implementation for on-the-fly computation of the modified syndrome polynomials, 
         FIG. 5  is a timing diagram, which is related to the flowchart of  FIG. 3 , 
         FIG. 6  is illustrative of an alternative method for on-the-fly computation of the modified syndrome polynomials, 
         FIG. 7  is a block diagram of a hardware implementation of the method of  FIG. 6 , 
         FIG. 8  is a timing diagram relating to the method of  FIG. 6 . 
     
    
    
     DETAILED DESCRIPTION 
     In soft-decision decoding it is known that a receiver can correct as long as
 
2 e+f&lt;d   min .  (1)
 
where e is the number of errors, f is the number of erasures, and d min  is the Hamming distance.
 
     For Computing the errors the following steps have to be done:
         1. Compute the syndrome polynomial       

     
       
         
           
             
               
                 
                   
                     S 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         v 
                         i 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           v 
                           i 
                         
                         ⁢ 
                         
                           α 
                           i 
                         
                         ⁢ 
                         x 
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           v 
                           i 
                         
                         ⁢ 
                         
                           α 
                           
                             2 
                             ⁢ 
                             i 
                           
                         
                         ⁢ 
                         
                           x 
                           2 
                         
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           v 
                           i 
                         
                         ⁢ 
                         
                           α 
                           
                             
                               ( 
                               
                                 M 
                                 - 
                                 1 
                               
                               ) 
                             
                             ⁢ 
                             i 
                           
                         
                         ⁢ 
                         
                           x 
                           
                             M 
                             - 
                             1 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
         
         
           
             2. Compute the erasure polynomial, where α j     i    is the power of the positions j 0 , j 1 , . . . , j p−1  of the erasures 
           
         
       
    
     
       
         
           
             
               
                 
                   
                     Γ 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         0 
                       
                       
                         p 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         1 
                         - 
                         
                           
                             α 
                             
                               j 
                               i 
                             
                           
                           ⁢ 
                           x 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
         
         
           
             3. Construct the modified syndrome polynomial by
 
 T ( x )=Γ( x ) S ( x )mod x   M   (4)
 
             4. Solve the key equation
 
Λ( x ) T ( x )=Ω( x )mod x   M   (5)
 
             with Berlekamp-Massey or Euclid&#39;s algorithm. 
             5. Compute the Forney polynomial
 
Ψ( x )=Λ( x )Γ( x )  (6)
 
             6. Compute the magnitude of the errors and erasures using the Forney equation. 
           
         
       
    
     As apparent from Equations (2) and (3), they can be computed on-the-fly with the incoming data symbols ν N−1 , . . . ν 1 , ν 0 . 
     In the following a more detailed explanation of an implementation of above step 1, i.e. Equation (2), is given. 
     Let the error vector be {right arrow over (e)}=[e 0 , e 1 , . . . , e N−1 ] with polynomial representation
 
 e ( x )= e   0   +e   1   x+ . . . +e   N−1   x   N−1  with  e   i   ∈GF (2 8 ).  (7)
 
     The received polynomial at the input of the decoder is then
 
ν( x )= c ( x )+ e ( x )=ν 0 +ν 1   x+ . . . +ν   N−1   x   N−1  with ν i   ∈GF (2 8 ),  (8)
 
where the polynomial coefficients are components of the received vector {right arrow over (ν)}. Since the code word polynomial c(x) is divisible by the generator polynomial g(x), and g(=α i )=0 for i=0,1, . . . , M−1, evaluating the polynomial v(x) at the roots of the generator polynomial, which are α 0 , α 1 , . . . α M−1  yields to
 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           v 
                           ⁡ 
                           
                             ( 
                             
                               α 
                               j 
                             
                             ) 
                           
                         
                         = 
                         
                           
                             c 
                             ⁡ 
                             
                               ( 
                               
                                 α 
                                 j 
                               
                               ) 
                             
                           
                           + 
                           
                             e 
                             ⁡ 
                             
                               ( 
                               
                                 α 
                                 j 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           e 
                           ⁡ 
                           
                             ( 
                             
                               α 
                               j 
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 0 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 e 
                                 i 
                               
                               ⁢ 
                               
                                 α 
                                 ij 
                               
                             
                           
                         
                         , 
                         
                           j 
                           = 
                           0 
                         
                         , 
                         1 
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           M 
                           - 
                           1. 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     That signifies that the final equation set involves only components of the error pattern not those of the code word. They are called as syndromes S j , j=0,1, . . . , M−1, where 
     
       
         
           
             
               
                 
                   
                     
                       S 
                       j 
                     
                     = 
                     
                       
                         v 
                         ⁡ 
                         
                           ( 
                           
                             α 
                             j 
                           
                           ) 
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             v 
                             i 
                           
                           ⁢ 
                           
                             α 
                             ij 
                           
                         
                       
                     
                   
                   , 
                   
                     j 
                     = 
                     0 
                   
                   , 
                   1 
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   
                     M 
                     - 
                     1. 
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     These syndromes are used to form a syndrome polynomial in the form 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           S 
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 0 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               v 
                               i 
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 0 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 v 
                                 i 
                               
                               ⁢ 
                               
                                 α 
                                 i 
                               
                               ⁢ 
                               x 
                             
                           
                           + 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 0 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 v 
                                 i 
                               
                               ⁢ 
                               
                                 α 
                                 
                                   2 
                                   ⁢ 
                                   i 
                                 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                           
                           + 
                           … 
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             
                               N 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               v 
                               i 
                             
                             ⁢ 
                             
                               α 
                               
                                 
                                   ( 
                                   
                                     M 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                                 ⁢ 
                                 i 
                               
                             
                             ⁢ 
                             
                               x 
                               
                                 M 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             S 
                             0 
                           
                           + 
                           
                             
                               S 
                               1 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               S 
                               2 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                           
                             
                               S 
                               
                                 M 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 x 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     An on-the-fly computation of Equation (11) can be achieved is by iteratively updating the coefficients S i , i=0,1, . . . , M−1. At each symbol clock j, a new symbol ν n  is arriving, the power α n  of the position n is computed and the coefficients are updated in the following way:
 
 S   i,j   =S   i,j−1 +ν n α in   ,i= 0,1, . . . , M−1 where  S   i,−1 =0.  (12)
 
     A hardware implementation of an on-the-fly syndrome computation is shown in  FIG. 1 . At the beginning of a new code sequence, register  1  is initialised with the power of the position of the first symbol. The registers  2  are initialised with zero. Each time a new symbol arrives, register  1  and registers  2  are clocked, the syndromes are updated according to Equation (12) and the power of the root term in register  1  is decreased by one. 
     In the following a more detailed explanation of above step 2, i.e. Equation (3), is given. 
     Assuming p erasures at positions j 0 , j 1 , . . . , j p−1 , the erasure polynomial is computed in the following manner 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           Γ 
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                         
                           
                             ∏ 
                             
                               i 
                               = 
                               0 
                             
                             
                               p 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             ( 
                             
                               1 
                               - 
                               
                                 
                                   α 
                                   
                                     j 
                                     i 
                                   
                                 
                                 ⁢ 
                                 x 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             Γ 
                             0 
                           
                           + 
                           
                             
                               Γ 
                               1 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               Γ 
                               2 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                           
                             
                               Γ 
                               p 
                             
                             ⁢ 
                             
                               x 
                               p 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     An on-the-fly computation of that equation can be achieved by iteratively updating the polynomial. Each time j, when a new erasure ν n  occurs, the power α n  of the erasure position n is computed and the polynomial is updated in the following way
 
Γ j ( x )=Γ j−1 ( x )·(1−α n   x )=(Γ 0,j−1 +Γ 1,j−1   x+ . . . +Γ   p,j−   x   p )(1−α n   x )  (14)
 
     Examining the final polynomial of Equation (14), the coefficients can be written as 
     
       
         
           
             
               
                 
                   
                     Γ 
                     
                       i 
                       , 
                       j 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                                 
                               ⁢ 
                               
                                 
                                   
                                     Γ 
                                     
                                       i 
                                       , 
                                       
                                         j 
                                         - 
                                         1 
                                       
                                     
                                   
                                   + 
                                   
                                     
                                       α 
                                       n 
                                     
                                     ⁢ 
                                     
                                       Γ 
                                       
                                         
                                           i 
                                           - 
                                           1 
                                         
                                         , 
                                         
                                           j 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                                 , 
                               
                             
                           
                           
                             
                                 
                               ⁢ 
                               
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 , 
                                 2 
                                 , 
                                 … 
                                 ⁢ 
                                 
                                     
                                 
                                 , 
                                 p 
                               
                             
                           
                         
                         
                           
                             
                                 
                               ⁢ 
                               
                                 1 
                                 , 
                               
                             
                           
                           
                             
                                 
                               ⁢ 
                               
                                 i 
                                 = 
                                 0 
                               
                             
                           
                         
                       
                       , 
                       
                         
                           where 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             Γ 
                             
                               i 
                               , 
                               
                                 - 
                                 1 
                               
                             
                           
                         
                         = 
                         0. 
                       
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     A hardware implementation of an on-the-fly erasure polynomial computation, achieved by Equation (15) is depicted in  FIG. 2 . If the incoming symbol is an erasure, the depicted switches are toggled and the circuit realizes the computation according Equation (15). 
     The switches remain in their depicted position if the symbol is not an erasure. The switches are realized as combinatorial logic; hence they do not cause any extra clock delay. They are directly connected to the erasure signal provided with the symbol information. At the beginning of a new code sequence register  1  is initialised with the power of the position of the first symbol, for example with α 181  for the inner code of DVD. 
     The registers  2  are initialised with zero. Each time, when a new symbol arrives, register  1  and registers  2  are clocked, the syndromes are then updated according to Equation (15) and the power of the root term in register  1  is decreased by one. 
     The modified syndrome polynomial is obtained by multiplying the syndrome polynomial of Equation (2) with the erasure polynomial of Equation (3), according to 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           T 
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             S 
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           ⁢ 
                           
                             Γ 
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           ⁢ 
                           mod 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             x 
                             M 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           ( 
                           
                             
                               S 
                               0 
                             
                             + 
                             
                               
                                 S 
                                 1 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 S 
                                 2 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                             
                               
                                 S 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                               ⁢ 
                               
                                 x 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 Γ 
                                 0 
                               
                               + 
                               
                                 
                                   Γ 
                                   1 
                                 
                                 ⁢ 
                                 x 
                               
                               + 
                               
                                 
                                   Γ 
                                   2 
                                 
                                 ⁢ 
                                 
                                   x 
                                   2 
                                 
                               
                               + 
                               … 
                               + 
                               
                                 
                                   Γ 
                                   p 
                                 
                                 ⁢ 
                                 
                                   x 
                                   p 
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           mod 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             x 
                             M 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     The result is a cyclic convolution between the two polynomials 
     
       
         
           
             
               
                 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         S 
                         0 
                       
                       ⁢ 
                       
                         Γ 
                         0 
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             
                               S 
                               1 
                             
                             ⁢ 
                             
                               Γ 
                               0 
                             
                           
                           + 
                           
                             
                               S 
                               0 
                             
                             ⁢ 
                             
                               Γ 
                               1 
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       x 
                     
                     + 
                     
                       
                         ( 
                         
                           
                             
                               S 
                               2 
                             
                             ⁢ 
                             
                               Γ 
                               0 
                             
                           
                           + 
                           
                             
                               S 
                               1 
                             
                             ⁢ 
                             
                               Γ 
                               1 
                             
                           
                           + 
                           
                             
                               S 
                               0 
                             
                             ⁢ 
                             
                               Γ 
                               2 
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         x 
                         2 
                       
                     
                     + 
                     … 
                     + 
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         
                           M 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           S 
                           j 
                         
                         ⁢ 
                         
                           Γ 
                           
                             M 
                             - 
                             1 
                             - 
                             j 
                           
                         
                         ⁢ 
                         
                           x 
                           
                             M 
                             - 
                             1 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     According to the present invention, we start by substituting Equation (2) into (17), which yields 
     
       
         
           
             
               
                 
                   
                     
                       
                         T 
                         ⁡ 
                         
                           ( 
                           x 
                           ) 
                         
                       
                       = 
                       
                         
                           
                             ∑ 
                             
                               i 
                               = 
                               0 
                             
                             
                               N 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             v 
                             i 
                           
                         
                         + 
                         
                           
                             ( 
                             
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     v 
                                     i 
                                   
                                   ⁢ 
                                   
                                     α 
                                     i 
                                   
                                 
                               
                               + 
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     v 
                                     i 
                                   
                                   ⁢ 
                                   
                                     Γ 
                                     i 
                                   
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           x 
                         
                         + 
                         
                           
                             ( 
                             
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     v 
                                     i 
                                   
                                   ⁢ 
                                   
                                     α 
                                     
                                       2 
                                       ⁢ 
                                       i 
                                     
                                   
                                 
                               
                               + 
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     v 
                                     i 
                                   
                                   ⁢ 
                                   
                                     α 
                                     i 
                                   
                                   ⁢ 
                                   
                                     Γ 
                                     1 
                                   
                                 
                               
                               + 
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     v 
                                     i 
                                   
                                   ⁢ 
                                   
                                     Γ 
                                     2 
                                   
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             2 
                           
                         
                         + 
                         … 
                         + 
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             
                               M 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 0 
                               
                               
                                 N 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 v 
                                 i 
                               
                               ⁢ 
                               
                                 α 
                                 ij 
                               
                               ⁢ 
                               
                                 Γ 
                                 
                                   M 
                                   - 
                                   1 
                                   - 
                                   j 
                                 
                               
                               ⁢ 
                               
                                 x 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       or 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       better 
                     
                   
                   ⁢ 
                   
                       
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
             
               
                 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         
                           v 
                           i 
                         
                         ⁡ 
                         
                           ( 
                           
                             1 
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     α 
                                     i 
                                   
                                   + 
                                   
                                     Γ 
                                     1 
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     α 
                                     
                                       2 
                                       ⁢ 
                                       i 
                                     
                                   
                                   + 
                                   
                                     
                                       α 
                                       i 
                                     
                                     ⁢ 
                                     
                                       Γ 
                                       1 
                                     
                                   
                                   + 
                                   
                                     Γ 
                                     2 
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   0 
                                 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                               ⁢ 
                               
                                 
                                   α 
                                   ij 
                                 
                                 ⁢ 
                                 
                                   Γ 
                                   
                                     M 
                                     - 
                                     1 
                                     - 
                                     j 
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   
                                     M 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     This equation can now be interpreted in a way that indicates how to update the polynomial coefficients taking previous erasures into account. Assuming that at the time step j−1 the registers T i , i=0,1, . . . M−1 hold the correct modified syndromes and that we receive at time step j a further data symbol, we simply update the modified syndrome polynomial according to Equation (19). 
     With that information we can write down an algorithm A for an on-the-fly computation of the modified syndromes. Depending on whether the incoming symbol is or is not signaled as an erasure, Algorithm A needs two or one consecutive computations, respectively. But it is also possible to write down an alternative algorithm B for an on-the-fly computation of the modified syndromes. Algorithm B consists of two alternative branches, one of which is selected and performed depending on whether the incoming symbol is or is not signaled as an erasure, and where each of the branches needs just one system clock for performing all the computations necessary for the case in question. 
     Algorithm A 
     With Equation (19) it is possible to compute the modified syndrome directly without the computation of the syndromes. The flowchart in  FIG. 3  shows the first embodiment of an on-the-fly computation. The flowchart comprises Equation (20) to calculate two auxiliary terms T * (x), Γ * (x) and Equation (21) to calculate an iteration result T j (x), Γ j (x) from the auxiliary terms in case the incoming symbol ν n  is an erasure. At each symbol clock, when a new symbol is obtained, the modified syndromes are updated according to Equation (20). At every step of the calculation, the resulting modified syndromes are correct up to the latest received symbol. 
     For this algorithm the system clock rate has to be at least twice the symbol clock rate. The algorithm ends after the computation for the last symbol, then the correct modified syndrome is obtained. 
     In case of an erasure two system clocks are needed, one for the updating according to Equation (20) and one for multiplying the polynomial with the root as described by Equation (21). In case of an erasure, the order of computing Equation (20) and (21) can be interchanged. If so, it must be taken care, that if the first symbol of the stream is an erasure, the register T 0  must be preloaded with one, otherwise the first part of Equation (21) would yield zero. 
     The calculation of Equation (20) directly results from the cyclic convolution described in Equation (19). Therefore we describe in the following the algorithm of getting an erasure symbol. 
     Assume that up to time step n−1 we have in memory the following modified syndrome, which is the linear convolution of Equation (19) 
                             T     n   -   1       ⁡     (   x   )       =       ⁢       ∑     i   =   0       n   -   1       ⁢           ⁢       v   i     [     1   +       (       a   i     +     Γ     1   ,     n   -   1           )     ⁢   x     +                         ⁢         (       a     2   ⁢   i       +       a   i     ⁢     Γ     1   ,     n   -   1           +     Γ     2   ,     n   -   1           )     ⁢     x   2       +   …   +                     ⁢       ∑     j   =   0       M   -   1       ⁢           ⁢       a   ij     ⁢     Γ       M   -   1   -   j     ,     n   -   1         ⁢     x     M   -   1           ]                 (   22   )               
and the erasure polynomial
 Γ n−1 ( x )=1+Γ 1,n−1   x+Γ   2,n−1   x   2 + . . . . +Γ p,n−1   x   p .  (23) 
     Next we assume that at time step n an erasure symbol ν n , is coming, therefore computation of Equation (20) yields 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             * 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 0 
                               
                               
                                 n 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 v 
                                 i 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   1 
                                   + 
                                   
                                     
                                       ( 
                                       
                                         
                                           a 
                                           i 
                                         
                                         + 
                                         
                                           Γ 
                                           
                                             1 
                                             , 
                                             
                                               n 
                                               - 
                                               1 
                                             
                                           
                                         
                                       
                                       ) 
                                     
                                     ⁢ 
                                     x 
                                   
                                   + 
                                   
                                     
                                       ( 
                                       
                                         
                                           a 
                                           
                                             2 
                                             ⁢ 
                                             i 
                                           
                                         
                                         + 
                                         
                                           
                                             a 
                                             i 
                                           
                                           ⁢ 
                                           
                                             Γ 
                                             
                                               1 
                                               , 
                                               
                                                 n 
                                                 - 
                                                 1 
                                               
                                             
                                           
                                         
                                         + 
                                         
                                           Γ 
                                           
                                             2 
                                             , 
                                             
                                               n 
                                               - 
                                               1 
                                             
                                           
                                         
                                       
                                       ) 
                                     
                                     ⁢ 
                                     
                                       x 
                                       2 
                                     
                                   
                                   + 
                                   … 
                                   + 
                                   
                                     
                                       ∑ 
                                       
                                         j 
                                         = 
                                         0 
                                       
                                       
                                         M 
                                         - 
                                         1 
                                       
                                     
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       
                                         a 
                                         ij 
                                       
                                       ⁢ 
                                       
                                         Γ 
                                         
                                           
                                             M 
                                             - 
                                             1 
                                             - 
                                             j 
                                           
                                           , 
                                           
                                             n 
                                             - 
                                             1 
                                           
                                         
                                       
                                       ⁢ 
                                       
                                         x 
                                         
                                           M 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             v 
                             n 
                           
                           ⁡ 
                           
                             ( 
                             
                               1 
                               + 
                               
                                 
                                   ( 
                                   
                                     
                                       a 
                                       n 
                                     
                                     + 
                                     
                                       Γ 
                                       
                                         1 
                                         , 
                                         
                                           n 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 x 
                               
                               + 
                               
                                 
                                   ( 
                                   
                                     
                                       a 
                                       
                                         2 
                                         ⁢ 
                                         n 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         n 
                                       
                                       ⁢ 
                                       
                                         Γ 
                                         
                                           1 
                                           , 
                                           
                                             n 
                                             - 
                                             1 
                                           
                                         
                                       
                                     
                                     + 
                                     
                                       Γ 
                                       
                                         2 
                                         , 
                                         
                                           n 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   x 
                                   2 
                                 
                               
                               + 
                               … 
                               + 
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     = 
                                     0 
                                   
                                   
                                     M 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     a 
                                     ni 
                                   
                                   ⁢ 
                                   
                                     Γ 
                                     
                                       
                                         M 
                                         - 
                                         1 
                                         - 
                                         i 
                                       
                                       , 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                   ⁢ 
                                   
                                     x 
                                     
                                       M 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       T 
                       * 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       n 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         v 
                         i 
                       
                       ⁡ 
                       
                         ( 
                         
                           1 
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   i 
                                 
                                 + 
                                 
                                   Γ 
                                   
                                     1 
                                     , 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   
                                     2 
                                     ⁢ 
                                     i 
                                   
                                 
                                 + 
                                 
                                   
                                     a 
                                     i 
                                   
                                   ⁢ 
                                   
                                     Γ 
                                     
                                       1 
                                       , 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 + 
                                 
                                   Γ 
                                   
                                     2 
                                     , 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                           
                             
                               ∑ 
                               
                                 j 
                                 = 
                                 0 
                               
                               
                                 M 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 a 
                                 ij 
                               
                               ⁢ 
                               
                                 Γ 
                                 
                                   
                                     M 
                                     - 
                                     1 
                                     - 
                                     j 
                                   
                                   , 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                               ⁢ 
                               
                                 x 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
           
         
       
     
     Now Equation (21) is computed 
     
       
         
           
             
               
                 T 
                 n 
               
               ⁡ 
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               
                 ( 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       0 
                     
                     n 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       v 
                       i 
                     
                     ⁡ 
                     
                       ( 
                       
                         1 
                         + 
                         
                           
                             ( 
                             
                               
                                 a 
                                 i 
                               
                               + 
                               
                                 Γ 
                                 
                                   1 
                                   , 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           x 
                         
                         + 
                         
                           
                             ( 
                             
                               
                                 a 
                                 
                                   2 
                                   ⁢ 
                                   i 
                                 
                               
                               + 
                               
                                 
                                   a 
                                   i 
                                 
                                 ⁢ 
                                 
                                   Γ 
                                   
                                     1 
                                     , 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               + 
                               
                                 Γ 
                                 
                                   2 
                                   , 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             2 
                           
                         
                         + 
                         … 
                         + 
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             
                               M 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               a 
                               ij 
                             
                             ⁢ 
                             
                               Γ 
                               
                                 
                                   M 
                                   - 
                                   1 
                                   - 
                                   j 
                                 
                                 , 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                             
                             ⁢ 
                             
                               x 
                               
                                 M 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
                 ) 
               
               ⁢ 
               
                 ( 
                 
                   1 
                   - 
                   
                     
                       a 
                       n 
                     
                     ⁢ 
                     x 
                   
                 
                 ) 
               
             
           
         
       
     
     Using cyclic convolution again yields 
                             T   n     ⁡     (   x   )       =       ⁢           ∑               i   =   0     N     ⁢           ⁢       V   I     (     1   +     a   i     +         a   n     +     Γ     1   ,     n   -   1             ︸     Γ     1   ,   n             )     ⁢   x     +                     ⁢         (       a     2   ⁢   i       +       a   i     ⁢       (       a   n     +     Γ     1   ,     n   -   1           )       ︸     Γ     1   ,   n             +           a   n     ⁢     Γ     1   ,     n   -   1           +     Γ     2   ,     n   -   1             ︸     Γ     2   ,   n             )     ⁢     x   2       +   …   +                     ⁢         ∑               j   =   0       M   -   1       ⁢           ⁢       a   ij     ⁢       (         a   n     ⁢     Γ       M   -     1   ⁢   j       ,     n   -   1           +     Γ       M   -   1   -   j     ,     n   -   1           )       ︸     Γ       M   -   1   -   j     ,   n           ⁢     x     M   -   1           )                 (   26   )               
which can be rewritten as
 
     
       
         
           
             
               
                 
                   
                     
                       T 
                       n 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       n 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           v 
                           i 
                         
                         ⁡ 
                         
                           ( 
                           
                             1 
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     i 
                                   
                                   + 
                                   
                                     Γ 
                                     
                                       1 
                                       , 
                                       n 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     
                                       2 
                                       ⁢ 
                                       i 
                                     
                                   
                                   + 
                                   
                                     
                                       a 
                                       i 
                                     
                                     ⁢ 
                                     
                                       Γ 
                                       
                                         1 
                                         , 
                                         n 
                                       
                                     
                                   
                                   + 
                                   
                                     Γ 
                                     
                                       2 
                                       , 
                                       n 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   0 
                                 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   a 
                                   ij 
                                 
                                 ⁢ 
                                 
                                   Γ 
                                   
                                     
                                       M 
                                       - 
                                       1 
                                       - 
                                       j 
                                     
                                     , 
                                     n 
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   
                                     M 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
     This is in fact again the linear convolution of the syndrome and erasure polynomial, according to Equation (19). 
     An embodiment of algorithm A for on-the-fly computation of the modified syndrome can be seen in  FIG. 4 . If the switches are in their depicted position, the architecture realizes the computation according to Equation (20). If the switches are toggled, the architecture realizes the computation according to Equation (21). 
     The switches are realized as combinatorial logic; hence they do not cause any extra clock delay. By comparison with the embodiments of  FIG. 1  and  FIG. 2  it can easily be seen that there is only an additional adder per cell or register necessary. That means there is a reduction in hardware, because no additional polynomial multiplier is necessary. 
     At the beginning of a new code sequence, register  1  in  FIG. 4  is initialised with the power of the position of the first symbol, for example with α 181  for the example of the inner code of DVD. The registers  2  and  3  are initialised with zeros. At every rising edge of the symbol clock a new symbol arrives and register  1  is clocked, decreasing the root power by one. Afterwards registers  2  are clocked with the next falling edge of the symbol clock, which updates the syndromes according to Equation (20). 
     If the arrived symbol was signaled as an erasure, the switches are toggled and registers  2  and  3  are clocked again, computing Equation (21). At the end of the last symbol in the sequence, after the last computation, registers  2  hold the modified syndromes of the whole code sequence and registers  3  hold the erasure polynomial. 
     In the following reference is made to  FIG. 5 , which shows an example for the timing behavior of the method of  FIG. 3 . 
     Assuming M=10 and order goes downward, as it is the case for the inner code of DVD. The symbol order starts with 181 and goes down to 0. The registers are preloaded with T(x)=0 and Γ −1 (x)=1. Let us assume we receive the following data stream:
 
ν 181 =α 6 ,ν 180 *=α 9 ,ν 179 *=α 10 ,ν 178 =α 12 ,ν 177 =α 15 ,ν 176 = . . . , . . . , ν 0 =α . . . ,
 
where the ν i * shall indicate those symbols which are signaled as erasures. At every rising edge of the symbol clock we get a new symbol ν n  together with its erasure information as shown in  FIG. 5 , and the register  1  of the circuit in  FIG. 4  is clocked and contains the right power term α n  of that symbol. At the first system clock after the rising edge of the symbol clock, denoted as  1  in  FIG. 5 , registers  2  of the circuit in  FIG. 4  are clocked in their depicted position and Equation (20) is computed.
 
     If the erasure signal is true the switches in  FIG. 4  are toggled and registers  2  and  3  of the circuit are clocked again at the next rising edge of the system clock, denoted  2  in  FIG. 5 , which leads to the computation of Equation (21). After the last computation of the 182nd symbol, the correct modified syndrome of the whole codeword is obtained. For the present example, the intermediate results up to after the fifth incoming symbol shall now be explained in detail. 
     Conventional Way 
     At first the intermediate modified syndrome is calculated in a conventional way as a reference to be able to verify the result of the inventive algorithm explained below. Equation (2) gives the syndrome of the data stream as 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           S 
                           ⁢ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         == 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 6 
                               
                               + 
                               
                                 a 
                                 9 
                               
                               + 
                               
                                 a 
                                 10 
                               
                               + 
                               
                                 a 
                                 12 
                               
                               + 
                               
                                 a 
                                 15 
                               
                             
                             ) 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     a 
                                     6 
                                   
                                   ⁢ 
                                   
                                     a 
                                     181 
                                   
                                 
                                 + 
                                 
                                   
                                     a 
                                     9 
                                   
                                   ⁢ 
                                   
                                     a 
                                     180 
                                   
                                 
                                 + 
                                 
                                   
                                     a 
                                     10 
                                   
                                   ⁢ 
                                   
                                     a 
                                     179 
                                   
                                 
                                 + 
                                 
                                   
                                     a 
                                     12 
                                   
                                   ⁢ 
                                   
                                     a 
                                     178 
                                   
                                 
                                 + 
                                 
                                   
                                     a 
                                     15 
                                   
                                   ⁢ 
                                   
                                     a 
                                     177 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                           … 
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 
                                   a 
                                   6 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     9 
                                     - 
                                     181 
                                   
                                 
                               
                               + 
                               
                                 
                                   a 
                                   9 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     9 
                                     - 
                                     180 
                                   
                                 
                               
                               + 
                               
                                 
                                   a 
                                   10 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     9 
                                     - 
                                     179 
                                   
                                 
                               
                               + 
                               
                                 
                                   a 
                                   12 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     9 
                                     - 
                                     178 
                                   
                                 
                               
                               + 
                               
                                 
                                   a 
                                   15 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     9 
                                     - 
                                     177 
                                   
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             9 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             169 
                           
                           + 
                           
                             
                               a 
                               79 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               113 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               a 
                               37 
                             
                             ⁢ 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               194 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               112 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                           
                             
                               a 
                               239 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               168 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               174 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               240 
                             
                             ⁢ 
                             
                               
                                 x 
                                 9 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Γ 
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           ( 
                           
                             1 
                             - 
                             
                               
                                 a 
                                 180 
                               
                               ⁢ 
                               x 
                             
                           
                           ) 
                         
                         ⁢ 
                         
                           ( 
                           
                             1 
                             - 
                             
                               
                                 a 
                                 178 
                               
                               ⁢ 
                               x 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         1 
                         + 
                         
                           
                             a 
                             228 
                           
                           ⁢ 
                           x 
                         
                         + 
                         
                           
                             a 
                             103 
                           
                           ⁢ 
                           
                             
                               x 
                               2 
                             
                             . 
                           
                         
                       
                     
                   
                   ⁢ 
                   
                       
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
           
         
       
     
     By multiplying the two polynomials, the modified syndrome polynomial up to that symbol is obtained as 
                           T   ⁡     (   x   )       =       ⁢         S   ⁡     (   x   )       ⁢     Γ   ⁡     (   x   )       ⁢   mod   ⁢           ⁢     x   M       =       a   69     +       (       a   79     +       a   169     ⁢     a   228         )     ⁢   x     +                       ⁢         +     (       a   113     +       a   79     ⁢     a   228       +       a   169     ⁢     a   103         )       ⁢     x   2       +   …                     ⁢     …   +       (       a   240     +       a   174     ⁢     a   228       +       a   168     ⁢     a   103         )     ⁢     x   9                     =       ⁢       a   169     +       a   134     ⁢   x     +       a   119     ⁢     x   2       +       a   68     ⁢     x   3       +       a   128     ⁢     x   4       +       a   172     ⁢     x   5       +                     ⁢         +     a   21       ⁢     x   6       +       a   40     ⁢     x   7       +       a   217     ⁢     x   8       +       a   152     ⁢     x   9                       (   30   )               
On-the-Fly Algorithm
 
     Computation is done in order of the incoming symbol; after each step, the resulting modified syndromes are correct up to the latest received symbol.
     1. Getting data symbol ν 181 =α 6 ; first system clock  1 ; computing Equation (20):   

     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             0 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         ⁢ 
                           
                         = 
                         
                           
                             a 
                             6 
                           
                           ⁡ 
                           
                             ( 
                             
                               1 
                               + 
                               
                                 
                                   a 
                                   181 
                                 
                                 ⁢ 
                                 x 
                               
                               + 
                               
                                 
                                   a 
                                   
                                     2 
                                     - 
                                     180 
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   2 
                                 
                               
                               + 
                               … 
                               + 
                               
                                 
                                   a 
                                   
                                     9 
                                     - 
                                     180 
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   9 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           = 
                           
                             
                               a 
                               6 
                             
                             + 
                             
                               
                                 a 
                                 187 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 a 
                                 113 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             
                               
                                 a 
                                 39 
                               
                               ⁢ 
                               
                                 x 
                                 3 
                               
                             
                             + 
                             
                               
                                 a 
                                 220 
                               
                               ⁢ 
                               
                                 x 
                                 4 
                               
                             
                             + 
                           
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               + 
                               
                                 a 
                                 146 
                               
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                           
                             
                               a 
                               72 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               253 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               179 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               105 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
             
               
                 
                   
                     Γ 
                     0 
                   
                   = 
                   1 
                 
               
               
                 
                   ( 
                   32 
                   ) 
                 
               
             
           
         
       
         
         2. Getting erasure symbol ν 180 *=α 9 ; first system clock  1 ; computing Equation (20): 
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             * 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 6 
                               
                               + 
                               
                                 a 
                                 9 
                               
                             
                             ) 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   187 
                                 
                                 + 
                                 
                                   
                                     a 
                                     9 
                                   
                                   ⁢ 
                                   
                                     a 
                                     180 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   a 
                                   113 
                                 
                                 + 
                                 
                                   
                                     a 
                                     9 
                                   
                                   ⁢ 
                                   
                                     a 
                                     
                                       2 
                                       - 
                                       180 
                                     
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           …… 
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   105 
                                 
                                 + 
                                 
                                   
                                     a 
                                     9 
                                   
                                   ⁢ 
                                   
                                     a 
                                     
                                       9 
                                       - 
                                       180 
                                     
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             229 
                           
                           + 
                           
                             
                               a 
                               237 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               138 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             0 
                             · 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               244 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                           
                             
                               a 
                               194 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               37 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               94 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               57 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               35 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   33 
                   ) 
                 
               
             
           
         
       
     
     Second system clock  2 , computing Equation (21): 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               T 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               229 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     237 
                                   
                                   + 
                                   
                                     
                                       a 
                                       180 
                                     
                                     ⁢ 
                                     
                                       a 
                                       229 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               x 
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     138 
                                   
                                   + 
                                   
                                     
                                       a 
                                       180 
                                     
                                     ⁢ 
                                     
                                       a 
                                       237 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     35 
                                   
                                   + 
                                   
                                     
                                       a 
                                       180 
                                     
                                     ⁢ 
                                     
                                       a 
                                       57 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               229 
                             
                             + 
                             
                               
                                 a 
                                 211 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 a 
                                 137 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             
                               
                                 a 
                                 63 
                               
                               ⁢ 
                               
                                 x 
                                 3 
                               
                             
                             + 
                             
                               
                                 a 
                                 244 
                               
                               ⁢ 
                               
                                 x 
                                 4 
                               
                             
                             + 
                             
                               
                                 a 
                                 170 
                               
                               ⁢ 
                               
                                 x 
                                 5 
                               
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 a 
                                 96 
                               
                               ⁢ 
                               
                                 x 
                                 6 
                               
                             
                             + 
                             
                               
                                 a 
                                 22 
                               
                               ⁢ 
                               
                                 x 
                                 7 
                               
                             
                             + 
                             
                               
                                 a 
                                 203 
                               
                               ⁢ 
                               
                                 x 
                                 8 
                               
                             
                             + 
                             
                               
                                 a 
                                 129 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   34 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Γ 
                       1 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     1 
                     + 
                     
                       
                         a 
                         180 
                       
                       ⁢ 
                       x 
                     
                   
                 
               
               
                 
                   ( 
                   35 
                   ) 
                 
               
             
           
         
       
         
         3. Getting data symbol ν 179 =α 10 ; first system clock  1 , computing Equation (20): 
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             2 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 229 
                               
                               + 
                               
                                 a 
                                 10 
                               
                             
                             ) 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   211 
                                 
                                 + 
                                 
                                   
                                     a 
                                     10 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         179 
                                       
                                       + 
                                       
                                         a 
                                         180 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   a 
                                   137 
                                 
                                 + 
                                 
                                   
                                     a 
                                     10 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         
                                           2 
                                           - 
                                           179 
                                         
                                       
                                       + 
                                       
                                         
                                           a 
                                           179 
                                         
                                         ⁢ 
                                         
                                           a 
                                           180 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 129 
                               
                               + 
                               
                                 
                                   a 
                                   10 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       a 
                                       
                                         9 
                                         - 
                                         179 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         
                                           8 
                                           - 
                                           179 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         180 
                                       
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             9 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             199 
                           
                           + 
                           
                             
                               a 
                               179 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               162 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               a 
                               87 
                             
                             ⁢ 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               209 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                           
                             
                               a 
                               48 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               201 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               133 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               182 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               215 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   36 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Γ 
                       2 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     1 
                     + 
                     
                       
                         a 
                         180 
                       
                       ⁢ 
                       x 
                     
                   
                 
               
               
                 
                   ( 
                   37 
                   ) 
                 
               
             
           
         
       
         
         4. Getting erasure symbol ν 178 *=α 12 ; first system clock  1 , computing Equation (20): 
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             * 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 199 
                               
                               + 
                               
                                 a 
                                 12 
                               
                             
                             ) 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   179 
                                 
                                 + 
                                 
                                   
                                     a 
                                     12 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         178 
                                       
                                       + 
                                       
                                         a 
                                         180 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   a 
                                   162 
                                 
                                 + 
                                 
                                   
                                     a 
                                     12 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         
                                           2 
                                           - 
                                           178 
                                         
                                       
                                       + 
                                       
                                         
                                           a 
                                           178 
                                         
                                         ⁢ 
                                         
                                           a 
                                           180 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 215 
                               
                               + 
                               
                                 
                                   a 
                                   12 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       a 
                                       
                                         9 
                                         - 
                                         178 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         
                                           8 
                                           - 
                                           178 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         180 
                                       
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             9 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             216 
                           
                           + 
                           
                             
                               a 
                               110 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               187 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               a 
                               111 
                             
                             ⁢ 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               17 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                           
                             
                               a 
                               146 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               64 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               37 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               108 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               39 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   38 
                   ) 
                 
               
             
           
         
       
     
     Second system clock  2 , computing Equation (21): 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               T 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               216 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     110 
                                   
                                   + 
                                   
                                     
                                       a 
                                       178 
                                     
                                     ⁢ 
                                     
                                       a 
                                       216 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               x 
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     187 
                                   
                                   + 
                                   
                                     
                                       a 
                                       178 
                                     
                                     ⁢ 
                                     
                                       a 
                                       110 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     39 
                                   
                                   + 
                                   
                                     
                                       a 
                                       178 
                                     
                                     ⁢ 
                                     
                                       a 
                                       108 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               216 
                             
                             + 
                             
                               
                                 a 
                                 36 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 a 
                                 234 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             
                               
                                 a 
                                 135 
                               
                               ⁢ 
                               
                                 x 
                                 3 
                               
                             
                             + 
                             
                               
                                 a 
                                 85 
                               
                               ⁢ 
                               
                                 x 
                                 4 
                               
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 a 
                                 88 
                               
                               ⁢ 
                               
                                 x 
                                 5 
                               
                             
                             + 
                             
                               
                                 a 
                                 202 
                               
                               ⁢ 
                               
                                 x 
                                 6 
                               
                             
                             + 
                             
                               
                                 a 
                                 244 
                               
                               ⁢ 
                               
                                 x 
                                 7 
                               
                             
                             + 
                             
                               
                                 a 
                                 166 
                               
                               ⁢ 
                               
                                 x 
                                 8 
                               
                             
                             + 
                             
                               
                                 a 
                                 231 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   39 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           
                             Γ 
                             3 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   180 
                                 
                                 + 
                                 
                                   a 
                                   178 
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               180 
                             
                             ⁢ 
                             
                               a 
                               178 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               a 
                               228 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               103 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   40 
                   ) 
                 
               
             
           
         
       
         
         5. Getting data symbol ν 177 =α 15 ; first system clock  1 ; computing Equation (20): 
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             4 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 216 
                               
                               + 
                               
                                 a 
                                 15 
                               
                             
                             ) 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   36 
                                 
                                 + 
                                 
                                   
                                     a 
                                     15 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         177 
                                       
                                       + 
                                       
                                         a 
                                         228 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   a 
                                   234 
                                 
                                 + 
                                 
                                   
                                     a 
                                     15 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         
                                           2 
                                           - 
                                           177 
                                         
                                       
                                       + 
                                       
                                         
                                           a 
                                           177 
                                         
                                         ⁢ 
                                         
                                           a 
                                           228 
                                         
                                       
                                       + 
                                       
                                         a 
                                         103 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 231 
                               
                               + 
                               
                                 
                                   a 
                                   15 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       a 
                                       
                                         9 
                                         - 
                                         177 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         
                                           8 
                                           - 
                                           177 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         228 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         
                                           7 
                                           - 
                                           177 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         103 
                                       
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             9 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             169 
                           
                           + 
                           
                             
                               a 
                               134 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               119 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               a 
                               68 
                             
                             ⁢ 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               128 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                           
                             
                               a 
                               172 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               21 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               40 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               217 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               152 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   41 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           
                             Γ 
                             4 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   180 
                                 
                                 + 
                                 
                                   a 
                                   178 
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               180 
                             
                             ⁢ 
                             
                               a 
                               178 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               a 
                               228 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               103 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   42 
                   ) 
                 
               
             
           
         
       
     
     Comparison of Equation (42) with (29) and (41) with (30) verifies the algorithm. This result is an intermediate result, it is not the final modified syndrome but merely the modified syndrome up to the fifth received symbol. The modified syndrome of the whole code sequence is obtained after the 182nd computation. 
     Algorithm B 
     In the following, the alternative algorithm B for the computation of the modified syndrome polynomials will be explained in more detail: 
     The second system clock at the computation of an erasure symbol can be avoided by inserting Equation (20) in Equation (21), which yields 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             n 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             
                               
                                 T 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 x 
                                 ) 
                               
                             
                             ⁢ 
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   
                                     a 
                                     n 
                                   
                                   ⁢ 
                                   x 
                                 
                               
                               ) 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             v 
                             n 
                           
                           ( 
                           
                             1 
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     n 
                                   
                                   + 
                                   
                                     Γ 
                                     
                                       1 
                                       , 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     
                                       2 
                                       ⁢ 
                                       n 
                                     
                                   
                                   + 
                                   
                                     
                                       a 
                                       n 
                                     
                                     ⁢ 
                                     
                                       Γ 
                                       
                                         1 
                                         , 
                                         
                                           n 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                   + 
                                   
                                     Γ 
                                     
                                       2 
                                       , 
                                       
                                         n 
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                               
                             ⁢ 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   0 
                                 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   a 
                                   nj 
                                 
                                 ⁢ 
                                 
                                   Γ 
                                   
                                     
                                       M 
                                       - 
                                       1 
                                       - 
                                       j 
                                     
                                     , 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   
                                     M 
                                     - 
                                     1 
                                   
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             ( 
                             
                               1 
                               - 
                               
                                 
                                   a 
                                   n 
                                 
                                 ⁢ 
                                 x 
                               
                             
                             ) 
                           
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   43 
                   ) 
                 
               
             
           
         
       
       
         
           
             or 
             ⁢ 
             
                 
             
             ⁢ 
             better 
             ⁢ 
             
               
                 
                   
                     
                       
                         
                           
                             
                               T 
                               n 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                             
                           ⁢ 
                           
                             
                               
                                 
                                   T 
                                   
                                     n 
                                     - 
                                     1 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   1 
                                   - 
                                   
                                     
                                       a 
                                       n 
                                     
                                     ⁢ 
                                     x 
                                   
                                 
                                 ) 
                               
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               v 
                               n 
                             
                             ( 
                             
                               1 
                               + 
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         n 
                                       
                                       + 
                                       
                                         
                                           
                                             a 
                                             n 
                                           
                                           + 
                                           
                                             Γ 
                                             
                                               1 
                                               , 
                                               
                                                 n 
                                                 - 
                                                 1 
                                               
                                             
                                           
                                         
                                         
                                           ︸ 
                                           
                                             Γ 
                                             
                                               1 
                                               , 
                                               n 
                                             
                                           
                                         
                                       
                                     
                                     ) 
                                   
                                   
                                     ︸ 
                                     
                                       Γ 
                                       
                                         1 
                                         , 
                                         
                                           n 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                                 ⁢ 
                                 x 
                               
                               + 
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         
                                           2 
                                           ⁢ 
                                           n 
                                         
                                       
                                       + 
                                       
                                         
                                           a 
                                           n 
                                         
                                         ⁢ 
                                         
                                           
                                             ( 
                                             
                                               
                                                 a 
                                                 n 
                                               
                                               + 
                                               
                                                 Γ 
                                                 
                                                   1 
                                                   , 
                                                   
                                                     n 
                                                     - 
                                                     1 
                                                   
                                                 
                                               
                                             
                                             ) 
                                           
                                           
                                             ︸ 
                                             
                                               Γ 
                                               
                                                 1 
                                                 , 
                                                 n 
                                               
                                             
                                           
                                         
                                       
                                       + 
                                       
                                         
                                           
                                             
                                               a 
                                               n 
                                             
                                             ⁢ 
                                             
                                               Γ 
                                               
                                                 1 
                                                 , 
                                                 
                                                   n 
                                                   - 
                                                   1 
                                                 
                                               
                                             
                                           
                                           + 
                                           
                                             Γ 
                                             
                                               2 
                                               , 
                                               
                                                 n 
                                                 - 
                                                 1 
                                               
                                             
                                           
                                         
                                         
                                           ︸ 
                                           
                                             Γ 
                                             
                                               2 
                                               , 
                                               n 
                                             
                                           
                                         
                                       
                                     
                                     ) 
                                   
                                   
                                     ︸ 
                                     
                                       Γ 
                                       
                                         2 
                                         , 
                                         
                                           n 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   2 
                                 
                               
                               + 
                               … 
                               + 
                             
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 
                                   ∑ 
                                   
                                     j 
                                     = 
                                     0 
                                   
                                   
                                     M 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     a 
                                     nj 
                                   
                                   ⁢ 
                                   
                                     
                                       ( 
                                       
                                         
                                           
                                             a 
                                             n 
                                           
                                           ⁢ 
                                           
                                             Γ 
                                             
                                               
                                                 M 
                                                 - 
                                                 j 
                                               
                                               , 
                                               
                                                 n 
                                                 - 
                                                 1 
                                               
                                             
                                           
                                         
                                         + 
                                         
                                           Γ 
                                           
                                             
                                               M 
                                               - 
                                               1 
                                               - 
                                               j 
                                             
                                             , 
                                             
                                               n 
                                               - 
                                               1 
                                             
                                           
                                         
                                       
                                       ) 
                                     
                                     
                                       ︸ 
                                       
                                         Γ 
                                         
                                           
                                             M 
                                             - 
                                             1 
                                             - 
                                             j 
                                           
                                           , 
                                           n 
                                         
                                       
                                     
                                   
                                 
                               
                               
                                 ︸ 
                                 
                                   Γ 
                                   
                                     
                                       M 
                                       - 
                                       1 
                                     
                                     , 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                             ⁢ 
                             
                               
                                 x 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     ( 
                     44 
                     ) 
                   
                 
               
             
           
         
       
     
     Therefore the equation can be written as
 
 T   n ( x )= T   n−1 ( x )(1−α n   x )+ν n Γ n−1 ( x ), where Γ −1 ( x )=1  (45)
 
     Now it is possible to write down the second algorithm B, which needs only one system clock for every incoming symbol type. 
     The flowchart in  FIG. 6  shows the second embodiment of an on-the-fly computation. For calculating one iteration result T j (x), Γ j (x), the flowchart comprises Equation (46) used in case the incoming symbol ν n  is an erasure, and Equation (47) used otherwise. 
     At each symbol clock, when a new symbol is obtained, the modified syndromes are updated. At every step of the calculation, the resulting modified syndromes are correct up to the latest received symbol. For that algorithm B the system clock rate can be the same as the symbol clock rate, which yields to a very fast computation. The algorithm ends after the last symbol, then the correct modified syndrome is obtained. 
     A second embodiment of an on-the-fly computation of the modified syndrome is depicted in  FIG. 7 . If the switches are in their depicted position, the architecture realizes the computation according to Equation (47). If the switches are toggled, the architecture realizes the computation according to Equation (46). 
     The switches are realized as combinatorial logic; hence they do not cause any extra clock delay. Comparing the depicted architecture with the one in  FIG. 4 , an additional multiplier and adder per cell or register is necessary. Increasing the hardware structure and therefore increasing the latency time can achieve reduction of computation time. 
     At the beginning of a new code sequence, register  1  in  FIG. 7  is initialised with the power of the position of the first symbol, for example with α 181  for the example of the inner code of DVD. The registers  2  and  3  are initialised with zeros. The switches are directly connected to the erasure signal. All registers  1 ,  2  and  3  are clocked with the rising edge of the symbol clock, which updates the syndromes according to Equation (46) or (47), depending on the erasure signal. 
     The clocking of register  1  decreases the power of the root term by one, in preparation for the next symbol. At the end of the last symbol in the sequence, after the last computation, registers  2  hold the modified syndromes of the whole code sequence and registers  3  hold the erasure polynomial. 
     The timing behavior and the algorithm are now explained by way of example. Assuming M=10 and order goes downward, as it is the case for the inner code of DVD. The symbol order starts with 181 and goes down to 0. The registers are preloaded with T(x)=0 and Γ −1 (x)=1. Let us assume we receive the following data stream:
 
ν 181 =α 6 ,ν 180 *=α 9 ,ν 179 *=α 10 ,ν 178 =α 12 ,ν 177 =α 15 ,ν 176 = . . . , . . . , ν 0 =α  . . .  ,
 
where the ν i * shall indicate those symbols-which are signaled as erasures. At every rising edge of the system clock a new symbol ν n  and an erasure information as shown in  FIG. 8  is obtained.
 
     The erasure signal feeds the switches of the circuit in  FIG. 7 . If the erasure signal is false the switches remain in their depicted position, if the erasure signal is true the switches are toggled. At the rising edge of the system clock, denoted as  1  in  FIG. 6 , the circuit in  FIG. 7  is clocked and Equation (46) or (47) is computed. After the last, i.e. 182nd symbol clock, the correct modified syndrome of the whole codeword is obtained. For the present example, the intermediate results up to after the fifth incoming symbol shall now be explained in detail. 
     Computation is done in order of the incoming symbols; after each step, the resulting modified syndromes are correct up to the latest received symbol.
         1. Getting data symbol ν 181 =α 6 ; computing Equation (46):       

     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             0 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             6 
                           
                           ⁡ 
                           
                             ( 
                             
                               1 
                               + 
                               
                                 
                                   a 
                                   181 
                                 
                                 ⁢ 
                                 x 
                               
                               + 
                               
                                 
                                   a 
                                   
                                     2 
                                     - 
                                     180 
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   2 
                                 
                               
                               + 
                               … 
                               + 
                               
                                 
                                   a 
                                   
                                     9 
                                     - 
                                     180 
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   9 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             6 
                           
                           + 
                           
                             
                               a 
                               187 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               113 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               a 
                               39 
                             
                             ⁢ 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               220 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               146 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                           
                             
                               a 
                               72 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               253 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               179 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               105 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   48 
                   ) 
                 
               
             
             
               
                 
                   
                     Γ 
                     0 
                   
                   = 
                   1 
                 
               
               
                 
                   ( 
                   49 
                   ) 
                 
               
             
           
         
       
         
         
           
             2. Getting erasure symbol ν 180 *=α 9  computing Equation (47): 
           
         
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               T 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               6 
                             
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 + 
                                 
                                   
                                     a 
                                     181 
                                   
                                   ⁢ 
                                   x 
                                 
                                 + 
                                 
                                   
                                     a 
                                     
                                       2 
                                       - 
                                       180 
                                     
                                   
                                   ⁢ 
                                   
                                     x 
                                     2 
                                   
                                 
                                 + 
                                 … 
                                 + 
                                 
                                   
                                     a 
                                     
                                       9 
                                       - 
                                       180 
                                     
                                   
                                   ⁢ 
                                   
                                     x 
                                     9 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               6 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     187 
                                   
                                   + 
                                   
                                     
                                       a 
                                       180 
                                     
                                     ⁢ 
                                     
                                       a 
                                       6 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     113 
                                   
                                   + 
                                   
                                     
                                       a 
                                       180 
                                     
                                     ⁢ 
                                     
                                       a 
                                       187 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     105 
                                   
                                   + 
                                   
                                     
                                       a 
                                       180 
                                     
                                     ⁢ 
                                     
                                       a 
                                       179 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                             + 
                             
                               a 
                               9 
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               229 
                             
                             + 
                             
                               
                                 a 
                                 211 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 a 
                                 137 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             
                               
                                 a 
                                 63 
                               
                               ⁢ 
                               
                                 x 
                                 3 
                               
                             
                             + 
                             
                               
                                 a 
                                 244 
                               
                               ⁢ 
                               
                                 x 
                                 4 
                               
                             
                             + 
                             
                               
                                 a 
                                 170 
                               
                               ⁢ 
                               
                                 x 
                                 5 
                               
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 a 
                                 96 
                               
                               ⁢ 
                               
                                 x 
                                 6 
                               
                             
                             + 
                             
                               
                                 a 
                                 22 
                               
                               ⁢ 
                               
                                 x 
                                 7 
                               
                             
                             + 
                             
                               
                                 a 
                                 203 
                               
                               ⁢ 
                               
                                 x 
                                 8 
                               
                             
                             + 
                             
                               
                                 a 
                                 129 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   50 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Γ 
                       1 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     1 
                     + 
                     
                       
                         a 
                         180 
                       
                       ⁢ 
                       x 
                     
                   
                 
               
               
                 
                   ( 
                   51 
                   ) 
                 
               
             
           
         
       
         
         
           
             3. Getting data symbol ν 179 =α 10 ; computing Equation (46): 
           
         
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             2 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 229 
                               
                               + 
                               
                                 a 
                                 10 
                               
                             
                             ) 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   211 
                                 
                                 + 
                                 
                                   
                                     a 
                                     10 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         179 
                                       
                                       + 
                                       
                                         a 
                                         180 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   a 
                                   137 
                                 
                                 + 
                                 
                                   
                                     a 
                                     10 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         
                                           2 
                                           - 
                                           179 
                                         
                                       
                                       + 
                                       
                                         
                                           a 
                                           179 
                                         
                                         ⁢ 
                                         
                                           a 
                                           180 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           … 
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 129 
                               
                               + 
                               
                                 
                                   a 
                                   10 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       a 
                                       
                                         9 
                                         - 
                                         179 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         
                                           8 
                                           - 
                                           179 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         180 
                                       
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             9 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             199 
                           
                           + 
                           
                             
                               a 
                               179 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               162 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               a 
                               87 
                             
                             ⁢ 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               209 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               48 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                           
                             
                               a 
                               201 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               133 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               182 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               215 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   52 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Γ 
                       2 
                     
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     1 
                     + 
                     
                       
                         a 
                         180 
                       
                       ⁢ 
                       x 
                     
                   
                 
               
               
                 
                   ( 
                   53 
                   ) 
                 
               
             
           
         
       
         
         
           
             4. Getting erasure symbol ν 178 *=α 12 ; computing Equation (47): 
           
         
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               T 
                               3 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               199 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     179 
                                   
                                   + 
                                   
                                     
                                       a 
                                       178 
                                     
                                     ⁢ 
                                     
                                       a 
                                       199 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               x 
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     162 
                                   
                                   + 
                                   
                                     
                                       a 
                                       178 
                                     
                                     ⁢ 
                                     
                                       a 
                                       179 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             … 
                             + 
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   
                                     a 
                                     215 
                                   
                                   + 
                                   
                                     
                                       a 
                                       178 
                                     
                                     ⁢ 
                                     
                                       a 
                                       182 
                                     
                                   
                                 
                                 ) 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                             + 
                             
                               a 
                               12 
                             
                             + 
                             
                               
                                 a 
                                 12 
                               
                               ⁢ 
                               
                                 a 
                                 180 
                               
                               ⁢ 
                               x 
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               a 
                               216 
                             
                             + 
                             
                               
                                 a 
                                 36 
                               
                               ⁢ 
                               x 
                             
                             + 
                             
                               
                                 a 
                                 234 
                               
                               ⁢ 
                               
                                 x 
                                 2 
                               
                             
                             + 
                             
                               
                                 a 
                                 135 
                               
                               ⁢ 
                               
                                 x 
                                 3 
                               
                             
                             + 
                             
                               
                                 a 
                                 85 
                               
                               ⁢ 
                               
                                 x 
                                 4 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 + 
                                 
                                   a 
                                   88 
                                 
                               
                               ⁢ 
                               
                                 x 
                                 5 
                               
                             
                             + 
                             
                               
                                 a 
                                 202 
                               
                               ⁢ 
                               
                                 x 
                                 6 
                               
                             
                             + 
                             
                               
                                 a 
                                 244 
                               
                               ⁢ 
                               
                                 x 
                                 7 
                               
                             
                             + 
                             
                               
                                 a 
                                 166 
                               
                               ⁢ 
                               
                                 x 
                                 8 
                               
                             
                             + 
                             
                               
                                 a 
                                 231 
                               
                               ⁢ 
                               
                                 x 
                                 9 
                               
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   54 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           
                             Γ 
                             3 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   180 
                                 
                                 + 
                                 
                                   a 
                                   178 
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               180 
                             
                             ⁢ 
                             
                               a 
                               178 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               a 
                               228 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               103 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   55 
                   ) 
                 
               
             
           
         
       
         
         
           
             5. Getting data symbol ν 177 =α 15 ; computing Equation (46): 
           
         
       
    
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             T 
                             4 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 216 
                               
                               + 
                               
                                 a 
                                 15 
                               
                             
                             ) 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   36 
                                 
                                 + 
                                 
                                   
                                     a 
                                     15 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         177 
                                       
                                       + 
                                       
                                         a 
                                         228 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   a 
                                   234 
                                 
                                 + 
                                 
                                   
                                     a 
                                     15 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         a 
                                         
                                           2 
                                           - 
                                           177 
                                         
                                       
                                       + 
                                       
                                         
                                           a 
                                           177 
                                         
                                         ⁢ 
                                         
                                           a 
                                           228 
                                         
                                       
                                       + 
                                       
                                         a 
                                         103 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 a 
                                 231 
                               
                               + 
                               
                                 
                                   a 
                                   15 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       a 
                                       
                                         9 
                                         - 
                                         177 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         
                                           8 
                                           - 
                                           177 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         228 
                                       
                                     
                                     + 
                                     
                                       
                                         a 
                                         
                                           7 
                                           - 
                                           177 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         103 
                                       
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                           ⁢ 
                           
                             x 
                             9 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             a 
                             169 
                           
                           + 
                           
                             
                               a 
                               134 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               119 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                           + 
                           
                             
                               a 
                               68 
                             
                             ⁢ 
                             
                               x 
                               3 
                             
                           
                           + 
                           
                             
                               a 
                               128 
                             
                             ⁢ 
                             
                               x 
                               4 
                             
                           
                           + 
                           
                             
                               a 
                               172 
                             
                             ⁢ 
                             
                               x 
                               5 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                         ⁢ 
                         
                           
                             
                               a 
                               21 
                             
                             ⁢ 
                             
                               x 
                               6 
                             
                           
                           + 
                           
                             
                               a 
                               40 
                             
                             ⁢ 
                             
                               x 
                               7 
                             
                           
                           + 
                           
                             
                               a 
                               217 
                             
                             ⁢ 
                             
                               x 
                               8 
                             
                           
                           + 
                           
                             
                               a 
                               152 
                             
                             ⁢ 
                             
                               x 
                               9 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   56 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           
                             Γ 
                             4 
                           
                           ⁡ 
                           
                             ( 
                             x 
                             ) 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               ( 
                               
                                 
                                   a 
                                   180 
                                 
                                 + 
                                 
                                   a 
                                   178 
                                 
                               
                               ) 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               180 
                             
                             ⁢ 
                             
                               a 
                               178 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           1 
                           + 
                           
                             
                               a 
                               228 
                             
                             ⁢ 
                             x 
                           
                           + 
                           
                             
                               a 
                               103 
                             
                             ⁢ 
                             
                               x 
                               2 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   57 
                   ) 
                 
               
             
           
         
       
     
     Comparison of Equation (56) with (29) and (57) with (30) verifies the algorithm. This result is an intermediate result, it is not the finally modified syndrome, it is the modified syndrome up to that symbol. The modified syndrome of the whole code sequence is obtained after the 182nd computation.