PATENT DOCUMENT

Abstract:
An improvement to a key equation solver block for a BCH decoder, where the key equation solver block having a number of multiplier units specified by X, where: t*(7*t−1)/(codeword_len−3)≦X&lt;(t+1), where t is a number of transmission errors for the key equation solver block to correct, and codeword_len is a length of a transmitted codeword to be decoded by the BCH decoder.

Full Description:
FIELD 
       [0001]    This invention relates to the field of integrated circuits. More particularly, this invention relates to error correcting codes, such as those used during the transmission of digital information. 
       BACKGROUND 
       [0002]    BCH (Bose-Chaudhuri-Hocquenghem) codes are a large class of multiple error-correcting codes. The binary BCH codes were discovered in 1959 by Hocquenghem and independently in 1960 by Bose and Ray-Chaudhuri. Later, Gorenstein and Zierler generalized them to all finite fields. At about the same time Reed and Solomon published their paper on the special case of BCH codes that now bear their names. 
         [0003]    In practice, the binary BCH and Reed-Solomon codes are the most commonly used variants of BCH codes. They have applications in a variety of communication systems: space communication links, digital subscriber loops, wireless systems, networking communications, and magnetic and data storage systems. Continual demand for ever higher data rates and storage capacity provide an incentive to devise very high-speed and space-efficient VLSI implementations of BCH decoders. The first decoding algorithm for binary BCH codes was devised by Peterson in 1960. Since then, Peterson&#39;s algorithm has been refined by Gorenstein and Zierler, Berlekamp, Massey, Chien, Forney, and many others. 
         [0004]    BCH codes are generally developed as follows. GF(q) is defined as a finite field of q elements, q=2 s , called the base field, and α is defined as a primitive element of extension field GF(q m ), where n|q m −1. The variable t is defined as an error detecting BCH code of length n over GF(q) as the set of all sequences (c 0 , c 1 , . . . , c n-1), c   i εGF(q) such that polynomial 
         [0000]        c ( x )= c   0   +c   1   x+ . . . +c   n-1   x   n-1   εGF ( q   m )[ x]   
         [0005]    has roots in points: α 1 , α 2 , . . . , α 2t . The BCH code with m=1 is called the Reed Solomon code, and the BCH code with s=1 is called the binary BCH code. 
       Encoding of BCH Codes 
       [0006]    First, we calculate the generator polynomial g(x)εGF(q): 
         [0000]        g ( x )=( x −α)( x−α   2 ) . . . ( x−α   2t )= LCM{M   1 ( x ),  M   2 ( x ), . . . ,  M   2t ( x )}, 
         [0007]    where LCM is the least common multiplier and M i (x) is the minimal polynomial for α i . Let (d 0 , d 1 , . . . , d k-1 ) denote k data symbols that are to be transmitted over a communication channel, and d(x)=d 0 +d 1 x+ . . . d k-1 x k-1 εGF(q)[x]. The systematic encoding of vector (d 0 , d 1 , . . . , d k-1 ) into a codeword (c 0 , c 1 , . . . , c n-1 ) is as follows: 
         [0000]        c ( x )= x   n-p   d ( x )+ t ( x ), 
         [0008]    where p=deg g(x) and t(x)=−x n-p d(x)mod g(x), c(x)=c 0 +c 1 x+ . . . +C n-1 x n-1 . 
       Decoding of BCH Codes 
       [0009]    There are many BCH decoder architectures. A typical BCH decoder works as follows. Let (c 0 , c 1 , . . . , C n-1 ) be a transmitted codeword and (e 0 , e 1 , . . . , e n-1 ) be an error vector in a communication channel, where in r (with r≦t) positions i 1 , i 2 , . . . , i r  there are non-zero values Y 1 =e i     1   , . . . , Yr=e i     r   . Let also X 1 =α i     1   , . . . , X r =α i . Define e(x)=e 0 +e 1 x+ . . . +e n-1 x n-1  and t(x)=c(x)+e(x), t(x)=t 0 +t 1 x+ . . . +t n-1 x n-1 , where (t 0 , t 1 , . . . , t n-1 ) is a word is to be decoded. Then, the decoding algorithm consists of three main steps: 
       1. Syndrome Computation Block 
       [0010]    The decoder begins by computing 2t syndrome values 
         [0000]        S   0   =c (α),  S   1   =c (α 2 ), . . . ,  S   2t-1   =c (α 2t ) 
       2. Key Equation Solver Block 
       [0011]    This block is perhaps the most intricate part of BCH decoder. Define the syndrome polynomial S(x), error locator polynomial Λ(x), and error evaluator polynomial Ω(x) as follows: 
         [0000]    
       
         
           
             
               
                 S 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               = 
               
                 
                   S 
                   0 
                 
                 + 
                 
                   
                     S 
                     1 
                   
                    
                   x 
                 
                 + 
                 … 
                 + 
                 
                   
                     S 
                     
                       
                         2 
                          
                         t 
                       
                       - 
                       1 
                     
                   
                    
                   
                     x 
                     
                       
                         2 
                          
                         t 
                       
                       - 
                       1 
                     
                   
                 
               
             
             , 
             
               
 
             
              
             
               
                 Λ 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               = 
               
                 
                   
                     Λ 
                     0 
                   
                   + 
                   
                     
                       Λ 
                       1 
                     
                      
                     x 
                   
                   + 
                   … 
                   + 
                   
                     
                       Λ 
                       r 
                     
                      
                     
                       x 
                       r 
                     
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     r 
                   
                    
                   
                     ( 
                     
                       1 
                       - 
                       
                         
                           X 
                           i 
                         
                          
                         x 
                       
                     
                     ) 
                   
                 
               
             
             , 
             
               
 
             
              
             
               
                 Ω 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               = 
               
                 
                   
                     Ω 
                     0 
                   
                   + 
                   
                     
                       Ω 
                       1 
                     
                      
                     x 
                   
                   + 
                   … 
                   + 
                   
                     
                       Ω 
                       
                         r 
                         - 
                         1 
                       
                     
                      
                     
                       x 
                       
                         r 
                         - 
                         1 
                       
                     
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     r 
                   
                    
                   
                     
                       Y 
                       i 
                     
                      
                     
                       X 
                       i 
                     
                      
                     
                       
                         ∏ 
                         
                           
                             j 
                             = 
                             1 
                           
                           , 
                           
                             j 
                             ≠ 
                             i 
                           
                         
                         r 
                       
                        
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               X 
                               j 
                             
                              
                             x 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0012]    It is well known that these three polynomials are related with the following key equation: 
         [0000]      Λ( x ) S ( x )=Ω( x )mod  x   2t    
         [0013]    There are two major methods for solving the key equation: first, the Berlekamp-Massey algorithm (BM), and second, the extended Euclidean algorithm (eE). Until recently the architectures based on the eE algorithm were more popular because of its simplicity and regularity. In addition, they had smaller critical path delays then architectures based on the BM algorithm. Lately, however, BM based architectures have gained in popularity, due to a number of modifications in the standard BM algorithm that have made them even faster and more space-efficient than the eE based architectures. 
       3. Chien/Forney Block 
       [0014]    The last block finds the positions of the errors, and corrects the errors using the Forney formula: 
         [0000]    
       
         
           
             
               For 
                
               
                   
               
                
               all 
                
               
                   
               
                
               i 
             
             ∈ 
             
               
                 { 
                 
                   0 
                   , 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     n 
                     - 
                     1 
                   
                 
                 } 
               
                
               
                 : 
               
             
           
         
       
       
         
           
             
               if 
                
               
                   
               
                
               
                 Λ 
                  
                 
                   ( 
                   
                     α 
                     
                       - 
                       i 
                     
                   
                   ) 
                 
               
             
             = 
             0 
           
         
       
       
         
           
             
               then 
                
               
                   
               
                
               
                 t 
                 i 
               
             
             := 
             
               
                 t 
                 i 
               
               + 
               
                 
                   Ω 
                    
                   
                     ( 
                     
                       α 
                       
                         - 
                         i 
                       
                     
                     ) 
                   
                 
                 
                   
                     Λ 
                     ′ 
                   
                    
                   
                     ( 
                     
                       α 
                       
                         - 
                         i 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             else 
              
             
                 
             
              
             we 
              
             
                 
             
              
             
               don 
               &#39; 
             
              
             t 
              
             
                 
             
              
             change 
              
             
                 
             
              
             
               
                 t 
                 i 
               
               . 
             
           
         
       
     
         [0015]    What is desired is a scalable architecture for the BM algorithm. 
       SUMMARY 
       [0016]    The above and other needs are met by an improvement to a key equation solver block for a BCH decoder, where the key equation solver block having a number of multiplier units specified by X, where: 
         [0000]        t *(7* t− 1   )/(codeword_len−3)≦ X &lt;( t+ 1   ), 
         [0017]    where t is a number of transmission errors for the key equation solver block to correct, and codeword_len is a length of a transmitted codeword to be decoded by the BCH decoder. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0018]    Further advantages of the invention are apparent by reference to the detailed description when considered in conjunction with the figures, which are not to scale so as to more clearly show the details, wherein like reference numbers indicate like elements throughout the several views, and wherein: 
           [0019]      FIG. 1  is a functional block diagram of a key equation solver block according to one embodiment of the present invention. 
           [0020]      FIGS. 2-8  depict additional detail for the functional units depicted in  FIG. 1 , according to one embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    Multiplication in Galois fields is one of the most expensive operations in terms of the design area that is occupies on integrated circuits. For this reason, reducing the number of multipliers generally leads to a significant decrease in the amount of design area required. 
         [0022]    In the embodiments of the key equation solver (KES) block according to the present invention, the number of clock cycles of service of one codeword depends on the number of multipliers, according to the following relationship: N=t*(7*t−1)/mult_num+3, where N is the number of clock cycles of service of one codeword, t is the number of errors to be corrected, and mult_num is the number of multipliers in the KES block. Hence, when the number of multipliers is reduced, the number of clock cycles generally increases. 
         [0023]    For a pipeline decoder according to the present invention, the number of clock cycles of service for one codeword by the KES block is preferably no greater than the codeword length. As a result, the formula for the minimal acceptable number of multipliers for the pipeline decoder can be obtained as: min_mult_num=t*(7*t−1)/(codeword_len−3), where min_mult_num is the minimal acceptable number of multipliers for the pipeline decoder, t is the number of errors to correct, and codeword_len is the codeword length. 
         [0024]    In a standard KES block, usually 2t or (t+1) multipliers are used. In the KES blocks according to the present invention, any number of multipliers can be used. The architecture of KES blocks according to the present invention preferably has a variable number of multipliers that is dependent, at least in part, on codeword lengths. 
       Key Equation Solver Block with Variable Number of Multipliers 
       [0025]    The key equation solver block proposed herein is termed an inversionless Berlekamp-Massey algorithm (iBM). The embodiment of the key equation solver block described in this section depends on two parameters. First, parameter t is the number of errors to correct. If the number of errors to correct is more than or equal to t, then the key equation solver block returns a fail code. The second parameter k defines the number of multipliers. The number of multipliers is equal to n=]t/k[. Here ]x[ is a minimal integer number such that ]x[≧x. The inputs of the key equation solver block are 2t syndrome values: S 0 , S 1 , . . . , S 2t-1 . The output of the key equation solver block are t coefficients of the error locator polynomial: Λ 0 , Λ 1 , . . . , Λ t-1 , and t−1 coefficients of the error evaluator polynomial: Ω 0 , Ω 1 , . . . , Ω t-2 . 
       Definitions 
       [0026]    If R is a register then RD is the data input to the register, RE is the enable input to the register, and RQ is the output of the register. If for the r clock cycle RD=A and RE=1, then for the r+1 clock cycle RQ=A. If for the r clock cycle RD=A, RQ=B, and RE=0, then for the r+1 clock cycle RQ=B. Denote by | and · sum and multiplication operations in the finite field, respectively. 
       Structure 
       [0027]    The key equation solver block according to the embodiment described in this section uses the following registers: 
         [0028]    1) SR 0 , SR 1 , . . . , SR 2t-1  to save syndrome values, 
         [0029]    2) Λ 0 , Λ 1 , . . . , Λ t-1  to save coefficients of the error locator polynomial, 
         [0030]    3) L to save the degree of the error locator polynomial, 
         [0031]    4) r to save the step index, 
         [0032]    5) Ξ 0 , Ξ 1 , . . . , Ξ t-1 , 
         [0033]    6) Γ 0 , Γ 1 , . . . , Γ t-1 , 
         [0034]    7) Δ pr , 
         [0035]    8) Δ, and 
         [0036]    9) δ 
       Initialization 
       [0037]    The key equation solver block according to this embodiment is initiated with the following values: 
         [0038]    1) SR 0 .D=S 0 , SR 1 .D=S 1 , . . . , SR t-1 .D=S t-1 ; 
         [0039]    1) Λ 0 .D=1, Λ 1 .D=0, . . . , Λ t-1 .D=0; 
         [0040]    2) Γ 0 .D=1, Γ 1 .D=0, . . . , Γ t-1 .D=0; 
         [0041]    3) Δpr=1; 
         [0042]    3) L=0; and 
         [0043]    4) r=0. 
       Process 
       [0044]    The key equation solver block according to this embodiment consists of two main steps: 
         [0045]    1) Computation of the coefficients of the error locator polynomial; and 
         [0046]    2) Computation of the coefficients of the error evaluator polynomial. 
         [0047]    The computation of the coefficients of the error locator polynomial consists of 2t elementary steps. The q th  elementary step consists of 3k clock cycles: 
         [0000]    
       
         
           
             
               
                 1 
                 ) 
               
                
               
                   
               
                
               
                 Δ 
                 . 
                 D 
               
             
             = 
             
               
                 
                   
                     ⊕ 
                     
                       j 
                       = 
                       0 
                     
                   
                   
                     n 
                     - 
                     1 
                   
                 
                  
                 
                   
                     
                       
                         Λ 
                         j 
                       
                       . 
                       Q 
                     
                     · 
                     
                       
                         SR 
                         r 
                       
                        
                       
                         . 
                         
                           Q 
                           - 
                           j 
                         
                       
                     
                     · 
                     Q 
                   
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         remember 
                          
                         
                             
                         
                          
                         n 
                       
                       = 
                     
                     ] 
                   
                    
                   
                     t 
                     / 
                     
                       
                         k 
                         [ 
                         
                           is 
                            
                           
                               
                           
                            
                           the 
                            
                           
                               
                           
                            
                           number 
                            
                           
                              
                           
                            
                           
                               
                           
                            
                           of 
                            
                           
                               
                           
                            
                           multipliers 
                         
                         ) 
                       
                       . 
                       
                         
 
                       
                        
                       2 
                     
                   
                    
                   
                     ) 
                   
                    
                   
                       
                   
                    
                   
                     Δ 
                     . 
                     D 
                   
                 
               
               = 
               
                 
                   Δ 
                   . 
                   Q 
                 
                 ⊕ 
                 
                   
                     
                       ⊕ 
                       
                         j 
                         = 
                         n 
                       
                     
                     
                       
                         2 
                          
                         n 
                       
                       - 
                       1 
                     
                   
                    
                   
                     
                       
                         Λ 
                         j 
                       
                       . 
                       Q 
                     
                     · 
                     
                       
                         SR 
                         r 
                       
                        
                       
                         . 
                         
                           Q 
                           - 
                           j 
                         
                       
                       . 
                       Q 
                       . 
                       
                         
 
                       
                        
                       … 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               k 
                
               
                 ) 
               
                
               
                   
               
                
               
                 Δ 
                 . 
                 D 
               
             
             = 
             
               
                 
                   Δ 
                   . 
                   Q 
                 
                 ⊕ 
                 
                   
                     
                       ⊕ 
                       
                         j 
                         = 
                         
                           n 
                            
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                       
                     
                     
                       t 
                       - 
                       1 
                     
                   
                    
                   
                     
                       
                         Λ 
                         j 
                       
                       . 
                       D 
                     
                     · 
                     
                       
                         SR 
                         r 
                       
                        
                       
                         . 
                         
                           Q 
                           - 
                           j 
                         
                       
                       . 
                       D 
                       . 
                       
                         
 
                       
                        
                       k 
                     
                   
                 
               
               + 
               
                 1 
                  
                 
                   ) 
                 
                  
                 
                     
                 
                  
                 Define 
                  
                 
                     
                 
                  
                 δ 
                  
                 
                   : 
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 if 
                  
                 
                     
                 
                  
                 
                   Δ 
                   . 
                   Q 
                 
               
               ≠ 
               
                 0 
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 2 
                  
                 
                   L 
                   . 
                   Q 
                 
               
               ≤ 
               
                 r 
                 . 
                 Q 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 then 
                  
                 
                     
                 
                  
                 
                   δ 
                   . 
                   D 
                 
               
               = 
               1 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   else 
                    
                   
                       
                   
                    
                   
                     δ 
                     . 
                     D 
                   
                 
                 = 
                 0 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     
                       Ξ 
                       j 
                     
                     . 
                     D 
                   
                   = 
                   
                     
                       
                         Δ 
                         pr 
                       
                       . 
                       Q 
                     
                     · 
                     
                       
                         Λ 
                         j 
                       
                       . 
                       Q 
                     
                   
                 
                 ; 
                 
                   j 
                   = 
                   0 
                 
               
               , 
               1 
               , 
               … 
                
               
                   
               
               , 
               
                 n 
                 - 
                 
                   1. 
                    
                   
                     
 
                   
                    
                   
                     
                       
                         k 
                         + 
                         
                           2 
                            
                           
                             ) 
                           
                            
                           
                               
                           
                            
                           
                             
                               Ξ 
                               j 
                             
                             . 
                             D 
                           
                         
                       
                       = 
                       
                         
                           
                             Δ 
                             pr 
                           
                           . 
                           Q 
                         
                         · 
                         
                           
                             Λ 
                             j 
                           
                           . 
                           Q 
                         
                       
                     
                     ; 
                     
                       j 
                       = 
                       n 
                     
                   
                 
               
               , 
               
                 n 
                 + 
                 1 
               
               , 
               … 
                
               
                   
               
               , 
               
                 
                   2 
                    
                   n 
                 
                 - 
                 
                   1. 
                    
                   
                     
 
                   
                    
                   … 
                    
                   
                     
 
                   
                    
                   
                     
                       2 
                        
                       k 
                        
                       
                         ) 
                       
                        
                       
                           
                       
                        
                       
                         
                           Ξ 
                           j 
                         
                         . 
                         D 
                       
                     
                     = 
                     
                       
                         
                           
                             Δ 
                             pr 
                           
                           . 
                           Q 
                         
                         · 
                         
                           Λ 
                           
                             j 
                             . 
                           
                         
                       
                        
                       Q 
                     
                   
                 
               
               , 
               
                 j 
                 = 
                 
                   n 
                    
                   
                     ( 
                     
                       k 
                       - 
                       1 
                     
                     ) 
                   
                 
               
               , 
               
                 
                   n 
                    
                   
                     ( 
                     
                       k 
                       - 
                       1 
                     
                     ) 
                   
                 
                 + 
                 1 
               
               , 
               … 
                
               
                   
               
               , 
               
                 
                   
                     
                       t 
                       - 
                       
                         1. 
                          
                         
                           
 
                         
                          
                         2 
                          
                         k 
                       
                       + 
                       
                         1 
                          
                         
                           ) 
                         
                          
                         
                             
                         
                          
                         if 
                          
                         
                             
                         
                          
                         
                           δ 
                           . 
                           Q 
                         
                       
                     
                     ≠ 
                     
                       0 
                        
                       
                           
                       
                        
                       then 
                        
                       
                           
                       
                        
                       
                         
                           Γ 
                           j 
                         
                         . 
                         D 
                       
                     
                   
                   = 
                   
                     
                       Λ 
                       j 
                     
                     . 
                     Q 
                   
                 
                 ; 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     
                       Λ 
                       j 
                     
                     . 
                     D 
                   
                   = 
                   
                     
                       
                         Ξ 
                         j 
                       
                       . 
                       D 
                     
                     ⊕ 
                     
                       
                         Δ 
                         . 
                         Q 
                       
                       · 
                       
                         
                           Γ 
                           
                             j 
                             - 
                             1 
                           
                         
                         . 
                         Q 
                       
                     
                   
                 
                 ; 
                 
                   j 
                   = 
                   0 
                 
               
               , 
               1 
               , 
               … 
                
               
                   
               
               , 
               
                 n 
                 - 
                 1. 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     3 
                      
                     k 
                   
                   - 
                   
                     1 
                      
                     
                       ) 
                     
                      
                     
                         
                     
                      
                     if 
                      
                     
                         
                     
                      
                     
                       δ 
                       . 
                       Q 
                     
                   
                 
                 ≠ 
                 
                   0 
                    
                   
                       
                   
                    
                   then 
                    
                   
                       
                   
                    
                   
                     
                       Γ 
                       j 
                     
                     . 
                     D 
                   
                 
               
               = 
               
                 
                   Λ 
                   j 
                 
                 . 
                 Q 
               
             
             ; 
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     Λ 
                     j 
                   
                   . 
                   D 
                 
                 = 
                 
                   
                     
                       Ξ 
                       j 
                     
                     . 
                     D 
                   
                   ⊕ 
                   
                     
                       Δ 
                       . 
                       Q 
                     
                     · 
                     
                       
                         Γ 
                         
                           j 
                           - 
                           1 
                         
                       
                       . 
                       Q 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 j 
                 = 
                 
                   n 
                    
                   
                     ( 
                     
                       k 
                       - 
                       2 
                     
                     ) 
                   
                 
               
               , 
               
                 
                   n 
                    
                   
                     ( 
                     
                       k 
                       - 
                       2 
                     
                     ) 
                   
                 
                 + 
                 1 
               
               , 
               … 
                
               
                   
               
               , 
               
                 
                   n 
                    
                   
                     ( 
                     
                       k 
                       - 
                       1 
                     
                     ) 
                   
                 
                 - 
                 1. 
               
             
           
         
       
       
         
           
             
               
                 3 
                  
                 k 
                  
                 
                   ) 
                 
                  
                 
                     
                 
                  
                 
                   
                     Λ 
                     j 
                   
                   . 
                   D 
                 
               
               = 
               
                 
                   
                     Ξ 
                     j 
                   
                   . 
                   D 
                 
                 ⊕ 
                 
                   
                     Δ 
                     . 
                     Q 
                   
                   · 
                   
                     
                       Γ 
                       
                         j 
                         - 
                         1 
                       
                     
                     . 
                     Q 
                   
                 
               
             
             , 
             
               
 
             
              
             
                 
             
              
             
               j 
               = 
               
                 n 
                  
                 
                   ( 
                   
                     k 
                     - 
                     1 
                   
                   ) 
                 
               
             
             , 
             
               
                 n 
                  
                 
                   ( 
                   
                     k 
                     - 
                     1 
                   
                   ) 
                 
               
               + 
               1 
             
             , 
             … 
              
             
                 
             
             , 
             
               
                 t 
                 - 
                 1 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 if 
                  
                 
                     
                 
                  
                 
                   δ 
                   . 
                   Q 
                 
               
               ≠ 
               0 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   then 
                    
                   
                       
                   
                    
                   
                     
                       Γ 
                       j 
                     
                     . 
                     D 
                   
                 
                 = 
                 
                   
                     Λ 
                     j 
                   
                   . 
                   Q 
                 
               
               , 
               
                 j 
                 = 
                 
                   n 
                    
                   
                     ( 
                     
                       k 
                       - 
                       1 
                     
                     ) 
                   
                 
               
               , 
               
                 
                   n 
                    
                   
                     ( 
                     
                       k 
                       - 
                       1 
                     
                     ) 
                   
                 
                 + 
                 1 
               
               , 
               … 
                
               
                   
               
               , 
               
                 
                   t 
                   - 
                   1 
                 
                 ; 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   otherwise 
                    
                   
                       
                   
                    
                   
                     
                       Γ 
                       0 
                     
                     . 
                     D 
                   
                 
                 = 
                 0 
               
               , 
               
                 
                   
                     Γ 
                     j 
                   
                   . 
                   D 
                 
                 = 
                 
                   
                     Γ 
                     
                       j 
                       - 
                       1 
                     
                   
                   . 
                   Q 
                 
               
               , 
               
                 j 
                 = 
                 1 
               
               , 
               2 
               , 
               … 
                
               
                   
               
               , 
               
                 
                   t 
                   - 
                   1 
                 
                 ; 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   if 
                    
                   
                       
                   
                    
                   
                     δ 
                     . 
                     Q 
                   
                 
                 ≠ 
                 
                   0 
                    
                   
                       
                   
                    
                   then 
                    
                   
                       
                   
                    
                   
                     L 
                     . 
                     D 
                   
                 
               
               = 
               
                 
                   
                     r 
                     . 
                     Q 
                   
                   + 
                   1 
                   - 
                   
                     
                       L 
                       . 
                       Q 
                     
                      
                     
                         
                     
                      
                     and 
                      
                     
                         
                     
                      
                     
                       
                         Δ 
                         pr 
                       
                       . 
                       D 
                     
                   
                 
                 = 
                 
                   
                     
                       Δ 
                       . 
                       Q 
                       . 
                       
                         
 
                       
                        
                       
                           
                       
                        
                       If 
                     
                      
                     
                         
                     
                      
                     after 
                      
                     
                         
                     
                      
                     2 
                      
                     t 
                      
                     
                         
                     
                      
                     elementary 
                      
                     
                         
                     
                      
                     steps 
                      
                     
                         
                     
                      
                     
                       L 
                       . 
                       Q 
                     
                   
                   ≥ 
                   
                     t 
                      
                     
                         
                     
                      
                     then 
                      
                     
                         
                     
                      
                     the 
                      
                     
                         
                     
                      
                     key 
                      
                     
                         
                     
                      
                     equation 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               solver 
                
               
                   
               
                
               block 
             
           
         
       
       
         
           
             
                 
             
              
             
               returns 
                
               
                   
               
                
               a 
                
               
                   
               
                
               
                 “ 
                 fail 
                 ” 
               
                
               
                   
               
                
               
                 indication 
                 . 
               
             
           
         
       
     
         [0048]    The computation of the coefficients of the error evaluator polynomial consists of t−1 elementary steps. 
         [0049]    The q th  elementary step consists of k clock cycles: 
         [0000]    
       
         
           
             
               
                 1 
                 ) 
               
                
               
                   
               
                
               
                 Δ 
                 . 
                 D 
               
             
             = 
             
               
                 
                   
                     ⊕ 
                     
                       j 
                       = 
                       0 
                     
                   
                   
                     n 
                     - 
                     1 
                   
                 
                  
                 
                   
                     
                       
                         Λ 
                         j 
                       
                       . 
                       Q 
                     
                     · 
                     
                       
                         SR 
                         r 
                       
                        
                       
                         . 
                         
                           Q 
                           - 
                           j 
                         
                       
                       . 
                       Q 
                       . 
                       
                         
 
                       
                        
                       2 
                     
                   
                    
                   
                     ) 
                   
                    
                   
                       
                   
                    
                   
                     Δ 
                     . 
                     D 
                   
                 
               
               = 
               
                 
                   Δ 
                   . 
                   Q 
                 
                 ⊕ 
                 
                   
                     
                       ⊕ 
                       
                         j 
                         = 
                         n 
                       
                     
                     
                       
                         2 
                          
                         n 
                       
                       - 
                       1 
                     
                   
                    
                   
                     
                       
                         Λ 
                         j 
                       
                       . 
                       Q 
                     
                     · 
                     
                       
                         SR 
                         r 
                       
                        
                       
                         . 
                         
                           Q 
                           - 
                           j 
                         
                       
                       . 
                       Q 
                       . 
                       
                         
 
                       
                        
                       … 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               k 
               - 
               
                 1 
                  
                 
                   ) 
                 
                  
                 
                     
                 
                  
                 
                   Δ 
                   . 
                   D 
                 
               
             
             = 
             
               
                 
                   Δ 
                   . 
                   Q 
                 
                 ⊕ 
                 
                   
                     
                       ⊕ 
                       
                         j 
                         = 
                         
                           n 
                            
                           
                             ( 
                             
                               k 
                               - 
                               2 
                             
                             ) 
                           
                         
                       
                     
                     
                       
                         n 
                          
                         
                           ( 
                           
                             k 
                             - 
                             1 
                           
                           ) 
                         
                       
                       - 
                       1 
                     
                   
                    
                   
                     
                       
                         
                           Λ 
                           j 
                         
                         . 
                         Q 
                       
                       · 
                       
                         
                           SR 
                           r 
                         
                          
                         
                           . 
                           
                             Q 
                             - 
                             j 
                           
                         
                         . 
                         D 
                         . 
                         
                           
 
                         
                          
                         k 
                       
                     
                      
                     
                       ) 
                     
                      
                     
                         
                     
                      
                     
                       Ω 
                       q 
                     
                   
                 
               
               = 
               
                 
                   Δ 
                   . 
                   Q 
                 
                 ⊕ 
                 
                   
                     
                       ⊕ 
                       
                         j 
                         = 
                         
                           n 
                            
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                       
                     
                     
                       t 
                       - 
                       1 
                     
                   
                    
                   
                     
                       
                         Λ 
                         j 
                       
                       . 
                       D 
                     
                     · 
                     
                       
                         SR 
                         r 
                       
                        
                       
                         . 
                         
                           Q 
                           - 
                           j 
                         
                       
                       . 
                       D 
                       . 
                     
                   
                 
               
             
           
         
       
     
       Key Equation Solver Block Description 
       [0050]    If R is a register and RE is not assigned, then RE is assumed to be one. 
       Interface and Registers 
     Inputs 
       [0051]    1. S 0 , S 1 , S 2t-1  are syndrome values. 
         [0052]    2. start is a start signal. 
       Outputs 
       [0053]    1. Λ 0 , Λ 1 , Λ t-1  are coefficients of the error locator polynomial. 
         [0054]    2. Ω 0 , Ω 1 , . . . , Ω t-2  are coefficients of the error evaluator polynomial. 
         [0055]    3. finish is a finish signal. 
         [0056]    4. fail is a fail signal. 
       Constants 
       [0057]    1. n=]t/k[. 
         [0058]    2. m=3*k. 
         [0059]    3l=t mod n. 
         [0060]    4. if l=0 then q=], otherwise q=2. 
       Registers 
       [0061]    1. SR 0 , SR 1 , . . . , SR 2t-1  are syndrome registers. 
         [0062]    2. Λ 0 , Λ 1 , . . . , Λ t-1 , are registers for the error locator polynomial coefficients. 
         [0063]    3. finish is the finish signal register. 
         [0064]    4. fail is the fail signal register. 
         [0065]    5. L is the register to save the degree of the error locator polynomial. 
         [0066]    6. r is a register to save the step index. 
         [0067]    7. Ξ 0 , Ξ 1 , . . . , Ξ t-1 . 
         [0068]    8. Γ 0 , Γ 1 , . . . , Γ t-1 . 
         [0069]    9. T 0 , T 1 , . . . , T m-1  are clock registers for the error locator polynomial calculation. 
         [0070]    10. T 0 ′, T 1 ′, T k-1 ′ are clock registers for the error evaluator polynomial calculation. 
         [0071]    11. M 0 , M 1 , . . . , M n-1  are output registers for the multipliers. 
         [0072]    12. Δ pr . 
         [0073]    13. Δ 
         [0074]    14. Δ 0 . 
         [0075]    15. start_omega. 
         [0076]    16. calc_omega. 
         [0077]    17. L r . 
         [0078]    18. rδ. 
         [0079]    19. after_start. 
       Internal Wires 
       [0080]    1. A 0 , A 1 , . . . , A n-1 ; B 0 , B 1 , . . . , B n-1  are inputs for the multipliers. 
         [0081]    2. LL 0 , LL 1 , . . . , LL t-1 . 
         [0082]    3. δ. 
         [0083]    4. sum. 
         [0084]    5. sum_control. 
       Computations 
       [0085]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               1. 
                                                
                                               
                                                   
                                               
                                                
                                               
                                                 
                                                   T 
                                                   0 
                                                 
                                                 . 
                                                 D 
                                               
                                             
                                             = 
                                             
                                               
                                                 
                                                   start 
                                                   ⋁ 
                                                   
                                                      
                                                     
                                                       finish 
                                                       . 
                                                       Q 
                                                     
                                                   
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 MUX 
                                                  
                                                 
                                                   ( 
                                                   
                                                     
                                                       calc_omega 
                                                       . 
                                                       Q 
                                                     
                                                     , 
                                                     
                                                       
 
                                                     
                                                      
                                                     
                                                         
                                                     
                                                      
                                                     
                                                       
                                                         T 
                                                         
                                                           m 
                                                           - 
                                                           1 
                                                         
                                                       
                                                       . 
                                                       Q 
                                                     
                                                     , 
                                                     
                                                       
                                                         T 
                                                         
                                                           k 
                                                           - 
                                                           1 
                                                         
                                                       
                                                       . 
                                                       Q 
                                                     
                                                   
                                                   ) 
                                                 
                                               
                                             
                                           
                                           ; 
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               T 
                                               k 
                                             
                                             . 
                                             D 
                                           
                                           = 
                                           
                                             
                                               
                                                 
                                                    
                                                   start 
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                  
                                                 
                                                   finish 
                                                   . 
                                                   Q 
                                                 
                                               
                                             
                                             &amp; 
                                           
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               
                                                  
                                                 
                                                   calc_omega 
                                                   . 
                                                   Q 
                                                 
                                               
                                               &amp; 
                                             
                                              
                                             
                                               
                                                 T 
                                                 
                                                   k 
                                                   - 
                                                   1 
                                                 
                                               
                                               . 
                                               Q 
                                             
                                           
                                           ; 
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               
                                                 T 
                                                 i 
                                               
                                               . 
                                               D 
                                             
                                             = 
                                             
                                               
                                                 
                                                   
                                                     
                                                        
                                                       start 
                                                     
                                                     &amp; 
                                                   
                                                    
                                                   
                                                      
                                                     
                                                       finish 
                                                       . 
                                                       Q 
                                                     
                                                   
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 
                                                   T 
                                                   
                                                     i 
                                                     - 
                                                     1 
                                                   
                                                 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           , 
                                           
                                             
 
                                           
                                            
                                           
                                               
                                           
                                            
                                           
                                             i 
                                             = 
                                             1 
                                           
                                           , 
                                           2 
                                           , 
                                           … 
                                            
                                           
                                               
                                           
                                           , 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                           , 
                                           
                                             k 
                                             + 
                                             1 
                                           
                                           , 
                                           … 
                                            
                                           
                                               
                                           
                                           , 
                                           
                                             
                                               m 
                                               - 
                                               1 
                                             
                                             ; 
                                           
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               
                                                 T 
                                                 0 
                                                 ′ 
                                               
                                               . 
                                               D 
                                             
                                             = 
                                             
                                               
                                                 
                                                   
                                                     
                                                        
                                                       
                                                         start_omega 
                                                         . 
                                                         Q 
                                                       
                                                     
                                                     &amp; 
                                                   
                                                    
                                                   
                                                      
                                                     
                                                       finish 
                                                       . 
                                                       Q 
                                                     
                                                   
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 
                                                   T 
                                                   
                                                     k 
                                                     - 
                                                     1 
                                                   
                                                   ′ 
                                                 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           ; 
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               T 
                                               
                                                 k 
                                                 - 
                                                 2 
                                               
                                               ′ 
                                             
                                             = 
                                             
                                               
                                                 start_omega 
                                                 . 
                                                 Q 
                                               
                                               ⋁ 
                                               
                                                 ( 
                                                 
                                                   
                                                     
                                                        
                                                       
                                                         finish 
                                                         . 
                                                         Q 
                                                       
                                                     
                                                     &amp; 
                                                   
                                                    
                                                   
                                                     
                                                       T 
                                                       
                                                         k 
                                                         - 
                                                         3 
                                                       
                                                       ′ 
                                                     
                                                     . 
                                                     Q 
                                                   
                                                 
                                                 ) 
                                               
                                             
                                           
                                           ; 
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               
                                                 T 
                                                 i 
                                                 ′ 
                                               
                                               . 
                                               D 
                                             
                                             = 
                                             
                                               
                                                 
                                                   
                                                     
                                                        
                                                       
                                                         start_omega 
                                                         . 
                                                         Q 
                                                       
                                                     
                                                     &amp; 
                                                   
                                                    
                                                   
                                                      
                                                     
                                                       finish 
                                                       . 
                                                       Q 
                                                     
                                                   
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 
                                                   T 
                                                   
                                                     i 
                                                     - 
                                                     1 
                                                   
                                                   ′ 
                                                 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           ; 
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             i 
                                             = 
                                             1 
                                           
                                           , 
                                           2 
                                           , 
                                           … 
                                            
                                           
                                               
                                           
                                           , 
                                           
                                             k 
                                             - 
                                             3 
                                           
                                           , 
                                           
                                             k 
                                             - 
                                             1. 
                                           
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                           
                                             
                                               2. 
                                                
                                               
                                                   
                                               
                                                
                                               
                                                 SR 
                                                 i 
                                               
                                                
                                               D 
                                             
                                             = 
                                             
                                               MUX 
                                                
                                               
                                                 ( 
                                                 
                                                   start 
                                                   , 
                                                   
                                                     
                                                       SR 
                                                       
                                                         i 
                                                         + 
                                                         1 
                                                       
                                                     
                                                     . 
                                                     Q 
                                                   
                                                   , 
                                                   
                                                     S 
                                                     i 
                                                   
                                                 
                                                 ) 
                                               
                                             
                                           
                                           , 
                                           
                                             
 
                                           
                                            
                                           
                                               
                                           
                                            
                                           
                                             
                                               
                                                 SR 
                                                 i 
                                               
                                               . 
                                               E 
                                             
                                             = 
                                             
                                               start 
                                               ⋁ 
                                               
                                                 
                                                   T 
                                                   
                                                     k 
                                                     - 
                                                     1 
                                                   
                                                 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           , 
                                           
                                             i 
                                             = 
                                             0 
                                           
                                           , 
                                           1 
                                           , 
                                           
                                             
                                               1. 
                                               .. 
                                             
                                              
                                             1 
                                           
                                            
                                           
                                               
                                           
                                           , 
                                           
                                             t 
                                             ; 
                                           
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               
                                                 SR 
                                                 i 
                                               
                                                
                                               D 
                                             
                                             = 
                                             
                                               MUX 
                                                
                                               
                                                 ( 
                                                 
                                                   start 
                                                   , 
                                                   
                                                     
                                                       
                                                          
                                                         
                                                           start_omega 
                                                           . 
                                                           Q 
                                                         
                                                       
                                                       &amp; 
                                                     
                                                      
                                                     
                                                       
                                                         SR 
                                                         
                                                           
                                                             ( 
                                                             
                                                             i 
                                                             + 
                                                             1 
                                                             
                                                             ) 
                                                           
                                                            
                                                           
                                                             mod 
                                                              
                                                             
                                                             ( 
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             ) 
                                                             
                                                           
                                                         
                                                       
                                                       . 
                                                       Q 
                                                     
                                                   
                                                   , 
                                                   
                                                     S 
                                                     i 
                                                   
                                                 
                                                 ) 
                                               
                                             
                                           
                                           , 
                                           
                                             
 
                                           
                                            
                                           
                                               
                                           
                                            
                                           
                                             SR 
                                             i 
                                           
                                           , 
                                           
                                             E 
                                             = 
                                             
                                               start 
                                               ⋁ 
                                               
                                                 
                                                   T 
                                                   
                                                     k 
                                                     - 
                                                     1 
                                                   
                                                 
                                                 . 
                                                 Q 
                                               
                                               ⋁ 
                                               
                                                 start_omega 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           , 
                                           
                                             i 
                                             = 
                                             
                                               t 
                                               + 
                                               1 
                                             
                                           
                                           , 
                                           … 
                                            
                                           
                                               
                                           
                                           , 
                                           
                                             
                                               2 
                                                
                                               t 
                                             
                                             - 
                                             1. 
                                           
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                           
                                             
                                               3. 
                                                
                                               
                                                   
                                               
                                                
                                               
                                                 A 
                                                 i 
                                               
                                             
                                             = 
                                             
                                               
                                                 
                                                   
                                                     
                                                       
                                                         ( 
                                                         
                                                           
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             T 
                                                             0 
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             &amp; 
                                                             
                                                              
                                                             
                                                             
                                                             
                                                             SR 
                                                             
                                                             
                                                             ( 
                                                             
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             - 
                                                             i 
                                                             
                                                             ) 
                                                             
                                                              
                                                             
                                                             mod 
                                                              
                                                             
                                                             ( 
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             ) 
                                                             
                                                             
                                                             
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             ⋁ 
                                                             
                                                             
                                                             T 
                                                             1 
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             
                                                             
                                                             &amp; 
                                                             
                                                              
                                                             
                                                             
                                                             
                                                             SR 
                                                             
                                                             ( 
                                                             
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             - 
                                                             n 
                                                             - 
                                                             i 
                                                             
                                                             ) 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             ⋁ 
                                                             … 
                                                             ⋁ 
                                                             
                                                               
                                                             
                                                              
                                                             
                                                               
                                                             
                                                              
                                                             
                                                             
                                                             T 
                                                             
                                                             k 
                                                             - 
                                                             1 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             
                                                             
                                                             &amp; 
                                                           
                                                            
                                                           
                                                             
                                                             SR 
                                                             
                                                             ( 
                                                             
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             - 
                                                             
                                                             
                                                             ( 
                                                             
                                                             k 
                                                             - 
                                                             1 
                                                             
                                                             ) 
                                                             
                                                              
                                                             n 
                                                             
                                                             - 
                                                             i 
                                                             
                                                             ) 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                           
                                                         
                                                         ) 
                                                       
                                                       ⋁ 
                                                       
                                                         ( 
                                                         
                                                           
                                                             
                                                             T 
                                                             k 
                                                             
                                                             . 
                                                             Q 
                                                           
                                                           ⋁ 
                                                           … 
                                                           ⋁ 
                                                           
                                                             
                                                             T 
                                                             
                                                             
                                                             2 
                                                              
                                                             k 
                                                             
                                                             - 
                                                             1 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                           
                                                         
                                                         ) 
                                                       
                                                     
                                                     &amp; 
                                                   
                                                    
                                                   
                                                     
                                                       
                                                         Δ 
                                                         pr 
                                                       
                                                       . 
                                                       Q 
                                                     
                                                     ⋁ 
                                                     
                                                       
 
                                                     
                                                      
                                                     
                                                         
                                                     
                                                      
                                                     
                                                       ( 
                                                       
                                                         
                                                           
                                                             T 
                                                             
                                                             2 
                                                              
                                                             k 
                                                             
                                                           
                                                           . 
                                                           Q 
                                                         
                                                         ⋁ 
                                                         … 
                                                         ⋁ 
                                                         
                                                           
                                                             T 
                                                             
                                                             
                                                             3 
                                                              
                                                             k 
                                                             
                                                             - 
                                                             1 
                                                             
                                                           
                                                           . 
                                                           Q 
                                                         
                                                       
                                                       ) 
                                                     
                                                   
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 Δ 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           , 
                                           
                                             i 
                                             = 
                                             0 
                                           
                                           , 
                                           1 
                                           , 
                                           … 
                                            
                                           
                                               
                                           
                                           , 
                                           
                                             
                                               l 
                                               - 
                                               1 
                                             
                                             ; 
                                           
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           
                                             
                                               A 
                                               i 
                                             
                                             = 
                                             
                                               
                                                 
                                                   
                                                     
                                                       
                                                         ( 
                                                         
                                                           
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             
                                                             T 
                                                             0 
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             &amp; 
                                                             
                                                              
                                                             
                                                             
                                                             
                                                             SR 
                                                             
                                                             
                                                             ( 
                                                             
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             - 
                                                             i 
                                                             
                                                             ) 
                                                             
                                                              
                                                             
                                                             mod 
                                                              
                                                             
                                                             ( 
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             ) 
                                                             
                                                             
                                                             
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             ⋁ 
                                                             
                                                             T 
                                                             1 
                                                             
                                                             
                                                              
                                                             Q 
                                                             
                                                             &amp; 
                                                             
                                                              
                                                             
                                                             
                                                             
                                                             SR 
                                                             
                                                             ( 
                                                             
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             - 
                                                             n 
                                                             - 
                                                             i 
                                                             
                                                             ) 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             ⋁ 
                                                             … 
                                                             ⋁ 
                                                             
                                                             
 
                                                             
                                                              
                                                             
                                                               
                                                             
                                                              
                                                             
                                                             
                                                             T 
                                                             
                                                             k 
                                                             - 
                                                             q 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             
                                                             
                                                             &amp; 
                                                           
                                                            
                                                           
                                                             
                                                             SR 
                                                             
                                                             ( 
                                                             
                                                             
                                                             2 
                                                              
                                                             t 
                                                             
                                                             - 
                                                             
                                                             
                                                             ( 
                                                             
                                                             k 
                                                             - 
                                                             q 
                                                             
                                                             ) 
                                                             
                                                              
                                                             n 
                                                             
                                                             - 
                                                             i 
                                                             
                                                             ) 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                           
                                                         
                                                         ) 
                                                       
                                                       ⋁ 
                                                       
                                                         ( 
                                                         
                                                           
                                                             
                                                             T 
                                                             k 
                                                             
                                                             . 
                                                             Q 
                                                           
                                                           ⋁ 
                                                           … 
                                                           ⋁ 
                                                           
                                                             
                                                             T 
                                                             
                                                             k 
                                                             - 
                                                             1 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                           
                                                         
                                                         ) 
                                                       
                                                     
                                                     &amp; 
                                                   
                                                    
                                                   
                                                     
                                                       
                                                         Δ 
                                                         pr 
                                                       
                                                       . 
                                                       Q 
                                                     
                                                     ⋁ 
                                                     
                                                       
 
                                                     
                                                      
                                                     
                                                         
                                                     
                                                      
                                                     
                                                       ( 
                                                       
                                                         
                                                           
                                                             T 
                                                             
                                                             2 
                                                              
                                                             k 
                                                             
                                                           
                                                           . 
                                                           Q 
                                                         
                                                         ⋁ 
                                                         … 
                                                         ⋁ 
                                                         
                                                           
                                                             T 
                                                             
                                                             
                                                             3 
                                                              
                                                             k 
                                                             
                                                             - 
                                                             1 
                                                             
                                                           
                                                           . 
                                                           Q 
                                                         
                                                       
                                                       ) 
                                                     
                                                   
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 Δ 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           , 
                                           
                                             i 
                                             = 
                                             l 
                                           
                                           , 
                                           
                                             l 
                                             + 
                                             1 
                                           
                                           , 
                                           … 
                                            
                                           
                                               
                                           
                                           , 
                                           
                                             n 
                                             - 
                                             1. 
                                           
                                         
                                          
                                         
                                           
 
                                         
                                          
                                         
                                           
                                             4. 
                                              
                                             
                                                 
                                             
                                              
                                             
                                               B 
                                               0 
                                             
                                           
                                           = 
                                           
                                             ( 
                                             
                                               
                                                 
                                                   
                                                     
                                                       
                                                         
                                                           
                                                             
                                                             ( 
                                                             
                                                             
                                                             
                                                             T 
                                                             0 
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             ⋁ 
                                                             
                                                             
                                                             T 
                                                             k 
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             
                                                             ) 
                                                             
                                                             &amp; 
                                                           
                                                            
                                                           
                                                             
                                                             Λ 
                                                             0 
                                                             
                                                             ⋁ 
                                                             
                                                             ( 
                                                             
                                                             
                                                             T 
                                                             1 
                                                             
                                                             · 
                                                             
                                                             Q 
                                                             ⋁ 
                                                             
                                                             
                                                             T 
                                                             
                                                             k 
                                                             + 
                                                             1 
                                                             
                                                             
                                                             . 
                                                             Q 
                                                             
                                                             
                                                             
                                                             ) 
                                                             
                                                           
                                                         
                                                         &amp; 
                                                       
                                                        
                                                       
                                                         
                                                           Λ 
                                                           n 
                                                         
                                                         ⋁ 
                                                       
                                                     
                                                     ... 
                                                   
                                                   ⋁ 
                                                   
                                                     
 
                                                   
                                                    
                                                   
                                                       
                                                   
                                                    
                                                   
                                                     ( 
                                                     
                                                       
                                                         
                                                           T 
                                                           
                                                             k 
                                                             - 
                                                             1 
                                                           
                                                         
                                                         . 
                                                         Q 
                                                       
                                                       ⋁ 
                                                       
                                                         
                                                           T 
                                                           
                                                             
                                                             2 
                                                              
                                                             k 
                                                             
                                                             - 
                                                             1 
                                                           
                                                         
                                                         . 
                                                         Q 
                                                       
                                                     
                                                     ) 
                                                   
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 Λ 
                                                 
                                                   
                                                     ( 
                                                     
                                                       k 
                                                       - 
                                                       1 
                                                     
                                                     ) 
                                                   
                                                    
                                                   n 
                                                 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                       ) 
                                     
                                     ⋁ 
                                     
                                       ( 
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   
                                                     
                                                       T 
                                                       
                                                         
                                                           2 
                                                            
                                                           k 
                                                         
                                                         + 
                                                         1 
                                                       
                                                     
                                                     . 
                                                     Q 
                                                   
                                                   &amp; 
                                                 
                                                  
                                                 
                                                   
                                                     
                                                       Γ 
                                                       
                                                         n 
                                                         - 
                                                         1 
                                                       
                                                     
                                                     . 
                                                     Q 
                                                   
                                                   ⋁ 
                                                   
                                                     
                                                       T 
                                                       
                                                         
                                                           2 
                                                            
                                                           k 
                                                         
                                                         + 
                                                         2 
                                                       
                                                     
                                                     . 
                                                     Q 
                                                   
                                                 
                                               
                                               &amp; 
                                             
                                              
                                             
                                               
 
                                             
                                              
                                             
                                                 
                                             
                                              
                                             
                                               
                                                 
                                                   Γ 
                                                   
                                                     
                                                       2 
                                                        
                                                       n 
                                                     
                                                     - 
                                                     1 
                                                   
                                                 
                                                 . 
                                                 Q 
                                               
                                               ⋁ 
                                               … 
                                               ⋁ 
                                               
                                                 
                                                   T 
                                                   
                                                     
                                                       3 
                                                        
                                                       k 
                                                     
                                                     - 
                                                     1 
                                                   
                                                 
                                                 . 
                                                 Q 
                                               
                                             
                                           
                                           &amp; 
                                         
                                          
                                         
                                           
                                             Γ 
                                             
                                               
                                                 
                                                   ( 
                                                   
                                                     k 
                                                     - 
                                                     1 
                                                   
                                                   ) 
                                                 
                                                  
                                                 n 
                                               
                                               - 
                                               1 
                                             
                                           
                                           . 
                                           Q 
                                         
                                       
                                       ) 
                                     
                                   
                                   ; 
                                 
                                  
                                 
                                   
 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   
                                     B 
                                     i 
                                   
                                   = 
                                   
                                     ( 
                                     
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   ( 
                                                   
                                                     
                                                       
                                                         T 
                                                         0 
                                                       
                                                       . 
                                                       Q 
                                                     
                                                     ⋁ 
                                                     
                                                       
                                                         T 
                                                         k 
                                                       
                                                       . 
                                                       Q 
                                                     
                                                   
                                                   ) 
                                                 
                                                 &amp; 
                                               
                                                
                                               
                                                 
                                                   Λ 
                                                   i 
                                                 
                                                 ⋁ 
                                                 
                                                   ( 
                                                   
                                                     
                                                       
                                                         T 
                                                         1 
                                                       
                                                       . 
                                                       Q 
                                                     
                                                     ⋁ 
                                                     
                                                       
                                                         T 
                                                         
                                                           k 
                                                           - 
                                                           1 
                                                         
                                                       
                                                       . 
                                                       Q 
                                                     
                                                   
                                                   ) 
                                                 
                                               
                                             
                                             &amp; 
                                           
                                            
                                           
                                             
                                               Λ 
                                               
                                                 n 
                                                 + 
                                                 i 
                                               
                                             
                                             ⋁ 
                                             … 
                                             ⋁ 
                                             
                                               
 
                                             
                                              
                                             
                                                 
                                             
                                              
                                             
                                               ( 
                                               
                                                 
                                                   
                                                     T 
                                                     
                                                       k 
                                                       - 
                                                       1 
                                                     
                                                   
                                                   . 
                                                   Q 
                                                 
                                                 ⋁ 
                                                 
                                                   
                                                     T 
                                                     
                                                       
                                                         2 
                                                          
                                                         k 
                                                       
                                                       - 
                                                       1 
                                                     
                                                   
                                                   . 
                                                   Q 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         &amp; 
                                       
                                        
                                       
                                         Λ 
                                         
                                           
                                             
                                               ( 
                                               
                                                 k 
                                                 - 
                                                 1 
                                               
                                               ) 
                                             
                                              
                                             n 
                                           
                                           - 
                                           1 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             ⋁ 
                             
                               ( 
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             
                                               T 
                                               
                                                 2 
                                                  
                                                 k 
                                               
                                             
                                             . 
                                             Q 
                                           
                                           &amp; 
                                         
                                          
                                         
                                           
                                             
                                               Γ 
                                               
                                                 i 
                                                 - 
                                                 1 
                                               
                                             
                                             . 
                                             Q 
                                           
                                           ⋁ 
                                           
                                             
                                               T 
                                               
                                                 
                                                   2 
                                                    
                                                   k 
                                                 
                                                 + 
                                                 1 
                                               
                                             
                                             . 
                                             Q 
                                           
                                         
                                       
                                       &amp; 
                                     
                                      
                                     
                                       
 
                                     
                                      
                                     
                                         
                                     
                                      
                                     
                                       
                                         
                                           Γ 
                                           
                                             n 
                                             + 
                                             i 
                                             - 
                                             1 
                                           
                                         
                                         . 
                                         Q 
                                       
                                       ⋁ 
                                       … 
                                       ⋁ 
                                       
                                         
                                           T 
                                           
                                             
                                               3 
                                                
                                               k 
                                             
                                             - 
                                             1 
                                           
                                         
                                         . 
                                         Q 
                                       
                                     
                                   
                                   &amp; 
                                 
                                  
                                 
                                   
                                     Γ 
                                     
                                       
                                         
                                           ( 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                           ) 
                                         
                                          
                                         n 
                                       
                                       + 
                                       i 
                                       - 
                                       1 
                                     
                                   
                                   . 
                                   Q 
                                 
                               
                               ) 
                             
                           
                           , 
                           
                             i 
                             = 
                             1 
                           
                           , 
                           2 
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             
                               l 
                               - 
                               1 
                             
                             ; 
                           
                         
                          
                         
                           
 
                         
                          
                         
                             
                         
                          
                         
                           
                             B 
                             i 
                           
                           = 
                           
                             ( 
                             
                               
                                 
                                   
                                     
                                       
                                         
                                           ( 
                                           
                                             
                                               
                                                 T 
                                                 0 
                                               
                                               . 
                                               Q 
                                             
                                             ⋁ 
                                             
                                               
                                                 T 
                                                 k 
                                               
                                               . 
                                               Q 
                                             
                                           
                                           ) 
                                         
                                         &amp; 
                                       
                                        
                                       
                                         
                                           Λ 
                                           i 
                                         
                                         ⋁ 
                                         
                                           ( 
                                           
                                             
                                               
                                                 T 
                                                 1 
                                               
                                               . 
                                               Q 
                                             
                                             ⋁ 
                                             
                                               
                                                 T 
                                                 
                                                   k 
                                                   + 
                                                   1 
                                                 
                                               
                                               . 
                                               Q 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                     &amp; 
                                   
                                    
                                   
                                     
                                       Λ 
                                       
                                         n 
                                         + 
                                         i 
                                       
                                     
                                     ⋁ 
                                     … 
                                     ⋁ 
                                     
                                       
 
                                     
                                      
                                     
                                         
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             T 
                                             
                                               k 
                                               - 
                                               q 
                                             
                                           
                                           . 
                                           Q 
                                         
                                         ⋁ 
                                         
                                           
                                             T 
                                             
                                               
                                                 2 
                                                  
                                                 k 
                                               
                                               - 
                                               q 
                                             
                                           
                                           . 
                                           Q 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 &amp; 
                               
                                
                               
                                 Λ 
                                 
                                   
                                     
                                       ( 
                                       
                                         k 
                                         - 
                                         q 
                                       
                                       ) 
                                     
                                      
                                     n 
                                   
                                   + 
                                   i 
                                 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                     ⋁ 
                     
                       ( 
                     
                   
                    
                   
                     
                       T 
                       
                         2 
                          
                         k 
                       
                     
                     . 
                     Q 
                   
                 
                 &amp; 
               
                
               
                 
                   
                     Γ 
                     
                       i 
                       - 
                       1 
                     
                   
                   . 
                   Q 
                 
                 ⋁ 
                 
                   
                     T 
                     
                       
                         2 
                          
                         k 
                       
                       + 
                       1 
                     
                   
                   . 
                   Q 
                 
               
             
             &amp; 
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     
                       
                         Γ 
                         
                           n 
                           + 
                           i 
                           - 
                           1 
                         
                       
                       . 
                       Q 
                     
                     ⋁ 
                     … 
                     ⋁ 
                     
                       
                         T 
                         
                           
                             3 
                              
                             k 
                           
                           - 
                           q 
                         
                       
                       . 
                       Q 
                     
                   
                   &amp; 
                 
                  
                 
                   
                     Γ 
                     
                       
                         
                           ( 
                           
                             k 
                             - 
                             q 
                           
                           ) 
                         
                          
                         n 
                       
                       + 
                       i 
                       - 
                       1 
                     
                   
                   . 
                   Q 
                 
               
               , 
               
                 
 
               
                
               
                   
               
                
               
                 i 
                 = 
                 
                   max 
                    
                   
                     ( 
                     
                       1 
                       , 
                       l 
                     
                     ) 
                   
                 
               
               , 
               … 
                
               
                   
               
               , 
               
                 
                   n 
                   - 
                   
                     1. 
                      
                     
                       
 
                     
                      
                     5. 
                      
                     
                         
                     
                      
                     
                       
                         M 
                         i 
                       
                       . 
                       D 
                     
                   
                 
                 = 
                 
                   
                     A 
                     i 
                   
                   · 
                   
                     B 
                     i 
                   
                 
               
               , 
               
                 i 
                 = 
                 0 
               
               , 
               1 
               , 
               … 
                
               
                   
               
               , 
               
                 n 
                 - 
                 1. 
               
             
           
         
       
       
         
           
             
               
                 6. 
                  
                 
                     
                 
                  
                 sum 
               
               = 
               
                 
                   
                     
                       ⊕ 
                       
                         j 
                         = 
                         0 
                       
                     
                     
                       n 
                       - 
                       1 
                     
                   
                    
                   
                     
                       
                         M 
                         i 
                       
                       . 
                       Q 
                       . 
                       
                         
 
                       
                        
                       7. 
                     
                      
                     
                         
                     
                      
                     sum_control 
                   
                 
                 = 
                 
                   
                     
                       
                         
                           T 
                           0 
                         
                         . 
                         Q 
                       
                       ⋁ 
                       
                         
                           T 
                           2 
                         
                         . 
                         Q 
                       
                       ⋁ 
                       … 
                       ⋁ 
                       
                         
                           T 
                           k 
                         
                         . 
                         Q 
                         . 
                         
                           
 
                         
                          
                         8. 
                       
                     
                      
                     
                         
                     
                      
                     
                       Δ 
                       . 
                       D 
                     
                   
                   = 
                   
                     sum 
                     + 
                     
                       ( 
                       
                         
                           
                             Δ 
                             . 
                             Q 
                           
                           &amp; 
                         
                          
                         sum_control 
                       
                       ) 
                     
                   
                 
               
             
             ; 
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   Δ 
                    
                   
                       
                   
                    
                   E 
                 
                 = 
                 
                   
                     
                       
                         
                           T 
                           1 
                         
                         . 
                         Q 
                       
                       ⋁ 
                       
                         sum_control 
                         . 
                         
                           
 
                         
                          
                         9. 
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         Δ 
                         0 
                       
                       . 
                       D 
                     
                   
                   = 
                   
                     ( 
                     
                       
                         Δ 
                         . 
                         Q 
                       
                       ≠ 
                       0 
                     
                     ) 
                   
                 
               
               ; 
               
                 
                   
                     Δ 
                     0 
                   
                   . 
                   E 
                 
                 = 
                 
                   
                     
                       
                         T 
                         
                           k 
                           + 
                           1 
                         
                       
                       . 
                       Q 
                       . 
                       
                         
 
                       
                        
                       10. 
                     
                      
                     
                         
                     
                      
                     
                       
                         L 
                         r 
                       
                       . 
                       D 
                     
                   
                   = 
                   
                     
                       
                         
                           ( 
                           
                             
                               2 
                                
                               
                                 L 
                                 . 
                                 Q 
                               
                             
                             ≤ 
                             
                               r 
                               . 
                               Q 
                             
                           
                           ) 
                         
                         &amp; 
                       
                        
                       
                         
                           T 
                           
                             k 
                             - 
                             1 
                           
                         
                         . 
                         Q 
                         . 
                         
                           
 
                         
                          
                         11. 
                       
                        
                       
                           
                       
                        
                       δ 
                     
                     = 
                     
                       
                         
                           
                             
                               
                                 
                                   L 
                                   r 
                                 
                                 . 
                                 Q 
                               
                               &amp; 
                             
                              
                             
                               
                                 Δ 
                                 0 
                               
                               . 
                               Q 
                             
                           
                           &amp; 
                         
                          
                         
                            
                           
                             
                               calc_omega 
                               . 
                               Q 
                               . 
                               
                                 
 
                               
                                
                               12. 
                             
                              
                             
                                 
                             
                              
                             r 
                              
                             
                                 
                             
                              
                             
                               δ 
                               . 
                               D 
                             
                           
                         
                       
                       = 
                       δ 
                     
                   
                 
               
               ; 
               
                 
                   r 
                    
                   
                       
                   
                    
                   
                     δ 
                     . 
                     E 
                   
                 
                 = 
                 
                   
                     
                       
                         T 
                         
                           k 
                           + 
                           2 
                         
                       
                       . 
                       Q 
                       . 
                       
                         
 
                       
                        
                       13. 
                     
                      
                     
                         
                     
                      
                     
                       
                         Δ 
                         pr 
                       
                       . 
                       D 
                     
                   
                   = 
                   
                     
                       ( 
                       
                         
                           start 
                           &amp; 
                         
                          
                         1 
                       
                       ) 
                     
                     ⋁ 
                     
                       Δ 
                       . 
                       Q 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     
                       Δ 
                       pr 
                     
                     . 
                     E 
                   
                   = 
                   
                     
                       
                         start 
                         ⋁ 
                         
                           
                             ( 
                             
                               
                                 
                                   r 
                                    
                                   
                                       
                                   
                                    
                                   
                                     δ 
                                     . 
                                     Q 
                                   
                                 
                                 &amp; 
                               
                                
                               
                                 
                                   T 
                                   
                                     
                                       2 
                                        
                                       k 
                                     
                                     - 
                                     1 
                                   
                                 
                                 . 
                                 Q 
                               
                             
                             ) 
                           
                           . 
                           
                             
 
                           
                            
                           14. 
                         
                       
                        
                       
                           
                       
                        
                       
                         L 
                         . 
                         D 
                       
                     
                     = 
                     
                       
                         
                            
                           start 
                         
                         &amp; 
                       
                        
                       
                         ( 
                         
                           
                             r 
                             . 
                             Q 
                           
                           + 
                           1 
                           - 
                           
                             L 
                             . 
                             Q 
                           
                         
                         ) 
                       
                     
                   
                 
                 ; 
                 
                   
                     L 
                     . 
                     E 
                   
                   = 
                   
                     
                       start 
                       ⋁ 
                       
                         δ 
                         . 
                         
                           
 
                         
                          
                         15. 
                       
                     
                      
                     
                         
                     
                      
                     
                       Ξ 
                       i 
                     
                   
                 
               
               , 
               
                 D 
                 = 
                 
                   
                     
                        
                       start 
                     
                     &amp; 
                   
                    
                   
                     
                       M 
                       
                         i 
                          
                         
                             
                         
                          
                         mod 
                          
                         
                             
                         
                          
                         n 
                       
                     
                     . 
                     Q 
                   
                 
               
               , 
               
                 
                   
                     Ξ 
                     i 
                   
                   . 
                   E 
                 
                 = 
                 
                   start 
                   ⋁ 
                   
                     
                       T 
                       
                         k 
                         + 
                         1 
                         + 
                         
                           i 
                           / 
                           n 
                         
                       
                     
                     . 
                     Q 
                   
                 
               
               , 
               
                 
 
               
                
               
                   
               
                
               
                 i 
                 = 
                 0 
               
               , 
               1 
               , 
               … 
                
               
                   
               
               , 
               
                 t 
                 - 
                 1. 
               
             
           
         
       
       
         
           
             
               
                 16. 
                  
                 
                     
                 
                  
                 
                   
                     Γ 
                     0 
                   
                   . 
                   D 
                 
               
               = 
               
                 
                   ( 
                   
                     
                       start 
                       &amp; 
                     
                      
                     1 
                   
                   ) 
                 
                 ⋁ 
                 
                   ( 
                   
                     
                       
                         r 
                          
                         
                             
                         
                          
                         
                           δ 
                           . 
                           Q 
                         
                       
                       &amp; 
                     
                      
                     
                       
                         Λ 
                         0 
                       
                       . 
                       Q 
                     
                   
                   ) 
                 
                 ⋁ 
                 
                   ( 
                   
                     
                       
                         Δ 
                         . 
                         Q 
                       
                       &amp; 
                     
                      
                     
                       calc_omega 
                       . 
                       Q 
                     
                   
                   ) 
                 
               
             
             ; 
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     Γ 
                     0 
                   
                   . 
                   E 
                 
                 = 
                 
                   start 
                   ⋁ 
                   
                     MUX 
                      
                     
                       ( 
                       
                         
                           r 
                            
                           
                               
                           
                            
                           
                             δ 
                             . 
                             Q 
                           
                         
                         , 
                         
                           
                             
                               T 
                               
                                 m 
                                 - 
                                 1 
                               
                             
                             . 
                             Q 
                           
                           ⋁ 
                           
                             
                               T 
                               
                                 k 
                                 - 
                                 1 
                               
                               ′ 
                             
                             . 
                             Q 
                           
                         
                         , 
                         
                           
                             T 
                             
                               
                                 2 
                                  
                                 k 
                               
                               + 
                               1 
                             
                           
                           . 
                           Q 
                         
                       
                       ) 
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     Γ 
                     i 
                   
                   . 
                   D 
                 
                 = 
                 
                   
                     
                        
                       start 
                     
                     &amp; 
                   
                    
                   
                     MUX 
                      
                     
                       ( 
                       
                         
                           r 
                            
                           
                               
                           
                            
                           
                             δ 
                             . 
                             Q 
                           
                         
                         , 
                         
                           
                             Γ 
                             
                               i 
                               - 
                               1 
                             
                           
                           . 
                           Q 
                         
                         , 
                         
                           
                             Λ 
                             i 
                           
                           . 
                           Q 
                         
                       
                       ) 
                     
                   
                 
               
               , 
               
                 
 
               
                
               
                   
               
                
               
                 
                   
                     Γ 
                     i 
                   
                   . 
                   E 
                 
                 = 
                 
                   start 
                   ⋁ 
                   
                     MUX 
                      
                     
                       ( 
                       
                         
                           r 
                            
                           
                               
                           
                            
                           
                             δ 
                             . 
                             Q 
                           
                         
                         , 
                         
                           
                             
                               T 
                               
                                 m 
                                 - 
                                 1 
                               
                             
                             . 
                             Q 
                           
                           ⋁ 
                           
                             
                               T 
                               
                                 k 
                                 - 
                                 1 
                               
                               ′ 
                             
                             . 
                             Q 
                           
                         
                         , 
                         
                           
 
                         
                          
                         
                             
                         
                          
                         
                           
                             T 
                             
                               
                                 ( 
                                 
                                   
                                     2 
                                      
                                     k 
                                   
                                   + 
                                   1 
                                   + 
                                   
                                     i 
                                     / 
                                     n 
                                   
                                 
                                 ) 
                               
                                
                               mod 
                                
                               
                                   
                               
                                
                               m 
                             
                           
                           . 
                           Q 
                         
                       
                       ) 
                     
                   
                 
               
               , 
               
                 i 
                 = 
                 1 
               
               , 
               2 
               , 
               … 
                
               
                   
               
               , 
               
                 t 
                 - 
                 1. 
               
             
           
         
       
       
         
           
             
               
                 17. 
                  
                 
                     
                 
                  
                 
                   LL 
                   i 
                 
               
               = 
               
                 
                   
                     Ξ 
                     i 
                   
                   . 
                   Q 
                 
                 ⊕ 
                 
                   
                     M 
                     
                       i 
                        
                       
                           
                       
                        
                       mod 
                        
                       
                           
                       
                        
                       n 
                     
                   
                   . 
                   Q 
                 
               
             
             , 
             
               i 
               = 
               0 
             
             , 
             1 
             , 
             … 
              
             
                 
             
             , 
             
               t 
               - 
               
                 1. 
                  
                 
                   
 
                 
                  
                 
                   
                     
                       18. 
                        
                       
                           
                       
                        
                       
                         
                           Λ 
                           0 
                         
                         . 
                         D 
                       
                     
                     = 
                     
                       MUX 
                        
                       
                         ( 
                         
                           start 
                           , 
                           
                             LL 
                             0 
                           
                           , 
                           1 
                         
                         ) 
                       
                     
                   
                   ; 
                   
                     
                       
                         Λ 
                         i 
                       
                       . 
                       D 
                     
                     = 
                     
                       
                         
                            
                           start 
                         
                         &amp; 
                       
                        
                       
                         LL 
                         i 
                       
                     
                   
                 
               
             
             , 
             
               
 
             
              
             
                 
             
              
             
               i 
               = 
               1 
             
             , 
             2 
             , 
             … 
              
             
                 
             
             , 
             
               
                 t 
                 - 
                 1 
               
               ; 
               
                 
 
               
                
               
                   
               
                
               
                 
                   
                     Λ 
                     i 
                   
                   . 
                   E 
                 
                 = 
                 
                   
                     
                       start 
                       ⋁ 
                       
                         
                           T 
                           
                             ( 
                             
                               
                                 2 
                                  
                                 k 
                               
                               + 
                               1 
                               + 
                               
                                 i 
                                 . 
                                 n 
                               
                             
                             ) 
                           
                         
                         . 
                         Q 
                       
                     
                     &amp; 
                   
                    
                   
                      
                     
                       calc_omega 
                       . 
                       Q 
                     
                   
                 
               
             
             , 
             
               
 
             
              
             
                 
             
              
             
               i 
               = 
               0 
             
             , 
             1 
             , 
             … 
              
             
                 
             
             , 
             
               
                 t 
                 - 
                 2 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   after_start 
                   . 
                   D 
                 
                 = 
                 start 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   
                     Λ 
                     
                       t 
                       - 
                       1 
                     
                   
                   . 
                   E 
                 
                 = 
                 
                   
                     
                       start 
                       ⋁ 
                       
                         
                           ( 
                           
                             
                               
                                 
                                   
                                     
                                       T 
                                       0 
                                     
                                     . 
                                     Q 
                                   
                                   &amp; 
                                 
                                  
                                 
                                    
                                   
                                     calc_omega 
                                     . 
                                     Q 
                                   
                                 
                               
                               &amp; 
                             
                              
                             
                                
                               
                                 after_start 
                                 . 
                                 Q 
                               
                             
                           
                           ) 
                         
                         . 
                         
                           
 
                         
                          
                         19. 
                       
                     
                      
                     
                         
                     
                      
                     
                       fail 
                       . 
                       D 
                     
                   
                   = 
                   
                     
                       
                         
                           ( 
                           
                             
                               L 
                               . 
                               Q 
                             
                             ≤ 
                             t 
                           
                           ) 
                         
                         . 
                         
                           
 
                         
                          
                         20. 
                       
                        
                       
                           
                       
                        
                       
                         r 
                         . 
                         D 
                       
                     
                     = 
                     
                       
                         
                           
                             
                                
                               start 
                             
                             &amp; 
                           
                            
                           
                              
                             
                               start_omega 
                               . 
                               Q 
                             
                           
                         
                         &amp; 
                       
                        
                       
                         ( 
                         
                           
                             r 
                             . 
                             Q 
                           
                           + 
                           1 
                         
                         ) 
                       
                     
                   
                 
               
               ; 
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   r 
                   . 
                   E 
                 
                 = 
                 
                   
                     
                       start 
                       ⋁ 
                       
                         
                           T 
                           
                             m 
                             - 
                             1 
                           
                         
                         . 
                         Q 
                       
                       ⋁ 
                       
                         
                           T 
                           
                             k 
                             - 
                             1 
                           
                           ′ 
                         
                         . 
                         Q 
                         . 
                         
                           
 
                         
                          
                         21. 
                       
                     
                      
                     
                         
                     
                      
                     
                       start_omega 
                       . 
                       D 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             
                                
                               start 
                             
                             &amp; 
                           
                            
                           
                             ( 
                             
                               
                                 r 
                                 . 
                                 Q 
                               
                               == 
                               
                                 
                                   2 
                                   * 
                                   t 
                                 
                                 - 
                                 1 
                               
                             
                             ) 
                           
                         
                         &amp; 
                       
                        
                       
                         
                           T 
                           
                             m 
                             - 
                             2 
                           
                         
                         . 
                         Q 
                         . 
                         
                           
 
                         
                          
                         22. 
                       
                        
                       
                           
                       
                        
                       
                         calc_omega 
                         . 
                         D 
                       
                     
                     = 
                     
                       
                         
                           
                             
                               
                                  
                                 start 
                               
                               &amp; 
                             
                              
                             
                                
                               
                                 finish 
                                 . 
                                 Q 
                               
                             
                           
                           &amp; 
                         
                          
                         
                           
                             ( 
                             
                               
                                 start_omega 
                                 . 
                                 Q 
                               
                               ⋁ 
                               
                                 
 
                               
                                
                               
                                   
                               
                                
                               
                                 calc_omega 
                                 . 
                                 Q 
                               
                             
                             ) 
                           
                           . 
                           
                             
 
                           
                            
                           23. 
                         
                          
                         
                             
                         
                          
                         
                           Ω 
                           i 
                         
                       
                       = 
                       
                         
                           Γ 
                           
                             t 
                             - 
                             2 
                             - 
                             i 
                           
                         
                         . 
                         Q 
                       
                     
                   
                 
               
               , 
               
                 i 
                 = 
                 0 
               
               , 
               1 
               , 
               … 
                
               
                   
               
               , 
               
                 
                   t 
                   - 
                   
                     2. 
                      
                     
                       
 
                     
                      
                     24. 
                      
                     
                         
                     
                      
                     
                       finish 
                       . 
                       D 
                     
                   
                 
                 = 
                 
                   
                     
                       
                         
                           
                             T 
                             
                               k 
                               - 
                               1 
                             
                             ′ 
                           
                           . 
                           Q 
                         
                         &amp; 
                       
                        
                       
                          
                         
                           finish 
                           . 
                           Q 
                         
                       
                     
                     &amp; 
                   
                    
                   
                     
                       ( 
                       
                         
                           r 
                           . 
                           Q 
                         
                         == 
                         
                           t 
                           - 
                           1 
                         
                       
                       ) 
                     
                     . 
                   
                 
               
             
           
         
       
     
       Key Equation Solver Block Scheme 
       [0086]      FIG. 1  shows the complete structure of the key equation solver block according to the embodiment of the invention described herein. As depicted in  FIG. 1  (and in  FIGS. 2-8  as applicable) syndromes are stored in the registers SR i . Block T ( FIG. 2 ) contains the generator for the control sequence T i  that governs one iteration of the iBM algorithm. Blocks A i  and B i  ( FIGS. 4 and 6  (and  FIG. 5  for Block B 0 ) respectively) act as multiplexers, switching the inputs of the multiplier units to the proper values for the current clock cycle, as indicated by T i . 
         [0087]    The outputs of the multiplier units are stored in the registers M i . The partial results of the calculation of the new value for the error locator polynomial are stored in blocks ACC i  ( FIG. 3B ). Coefficients for the error locator polynomial are collected in the array of registers Λ i , and the register array Γ i  is used to store the coefficients for the auxiliary correcting polynomial. Blocks ΛΛ i  ( FIGS. 7A ,  7 B, and  7 C) and ΓΓ i  ( FIGS. 8A and 8B ) manage the enable inputs and data inputs for Λ i  and Γ i  respectively, according to the state of the control sequence T i . Block Δ ( FIG. 3C ) is used for the iterative calculation of the value Δ.  FIG. 3A  depicts Block SA i . 
         [0088]    Block C contains logic that manages the iteration counter r, the error locator polynomial degree L, etc, and calculates the values of the signals Δ pr , rδ, finish, fail, start_omega and calc_omega. The schematics for these modules, except for the module C, are depicted in  FIGS. 2-8 . The configuration of the module C follows directly from the description of its outputs in the computation scheme. 
         [0089]    The foregoing description of preferred embodiments for this invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Obvious modifications or variations are possible in light of the above teachings. The embodiments are chosen and described in an effort to provide the best illustrations of the principles of the invention and its practical application, and to thereby enable one of ordinary skill in the art to utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. All such modifications and variations are within the scope of the invention as determined by the appended claims when interpreted in accordance with the breadth to which they are fairly, legally, and equitably entitled.