# Patent

## Title
Low area architecture in BCH decoder

## 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<(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.

## Background
FIELD
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
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.
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's algorithm has been refined by Gorenstein and Zierler, Berlekamp, Massey, Chien, Forney, and many others.
BCH codes are generally developed as follows. GF(q) is defined as a finite field of q elements, q=2s, called the base field, and α is defined as a primitive element of extension field GF(qm), where n|qm−1. The variable t is defined as an error detecting BCH code of length n over GF(q) as the set of all sequences (c0, c1, . . . , cn-1), ciεGF(q) such that polynomial

c(x)=c0+c1x+ . . . +cn-1xn-1εGF(qm)[x]

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
First, we calculate the generator polynomial g(x)εGF(q):

g(x)=(x−α)(x−α2) . . . (x−α2t)=LCM{M1(x), M2(x), . . . , M2t(x)},

where LCM is the least common multiplier and Mi(x) is the minimal polynomial for αi. Let (d0, d1, . . . , dk-1) denote k data symbols that are to be transmitted over a communication channel, and d(x)=d0+d1x+ . . . dk-1xk-1εGF(q)[x]. The systematic encoding of vector (d0, d1, . . . , dk-1) into a codeword (c0, c1, . . . , cn-1) is as follows:

c(x)=xn-pd(x)+t(x),

where p=deg g(x) and t(x)=−xn-pd(x)mod g(x), c(x)=c0+c1x+ . . . +Cn-1xn-1.
Decoding of BCH Codes
There are many BCH decoder architectures. A typical BCH decoder works as follows. Let (c0, c1, . . . , Cn-1) be a transmitted codeword and (e0, e1, . . . , en-1) be an error vector in a communication channel, where in r (with r≦t) positions i1, i2, . . . , ir there are non-zero values Y1=ei1, . . . , Yr=eir. Let also X1=αi1, . . . , Xr=αi. Define e(x)=e0+e1x+ . . . +en-1xn-1 and t(x)=c(x)+e(x), t(x)=t0+t1x+ . . . +tn-1xn-1, where (t0, t1, . . . , tn-1) is a word is to be decoded. Then, the decoding algorithm consists of three main steps:
1. Syndrome Computation Block
The decoder begins by computing 2t syndrome values

S0=c(α), S1=c(α2), . . . , S2t-1=c(α2t)

2. Key Equation Solver Block

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:




  
    
      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
                
              
              )
            
          
        
      
    
  




It is well known that these three polynomials are related with the following key equation:

Λ(x)S(x)=Ω(x)mod x2t 

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
The last block finds the positions of the errors, and corrects the errors using the Forney formula:



  
    
      For
      ⁢
      
        
      
      ⁢
      all
      ⁢
      
        
      
      ⁢
      i
    
    ∈
    
      
        {
        
          0
          ,
          1
          ,
          ...
          ⁢
          
            
          
          ,
          
            n
            -
            1
          
        
        }
      
      ⁢
      
        :
      
    
  




  
    
      if
      ⁢
      
        
      
      ⁢
      
        Λ
        ⁡
        
          (
          
            α
            
              -
              i
            
          
          )
        
      
    
    =
    0
  




  
    
      then
      ⁢
      
        
      
      ⁢
      
        t
        i
      
    
    :=
    
      
        t
        i
      
      +
      
        
          Ω
          ⁡
          
            (
            
              α
              
                -
                i
              
            
            )
          
        
        
          
            Λ
            ′
          
          ⁡
          
            (
            
              α
              
                -
                i
              
            
            )
          
        
      
    
  




  
    else
    ⁢
    
      
    
    ⁢
    we
    ⁢
    
      
    
    ⁢
    
      don
      '
    
    ⁢
    t
    ⁢
    
      
    
    ⁢
    change
    ⁢
    
      
    
    ⁢
    
      
        t
        i
      
      .
    
  



What is desired is a scalable architecture for the BM algorithm.
SUMMARY
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:

t*(7*t−1)/(codeword_len−3)≦X<(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.



BRIEF DESCRIPTION OF THE DRAWINGS
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:
FIG. 1 is a functional block diagram of a key equation solver block according to one embodiment of the present invention.
FIGS. 2-8 depict additional detail for the functional units depicted in FIG. 1, according to one embodiment of the present invention.



DETAILED DESCRIPTION
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.
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.
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.
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
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: S0, S1, . . . , S2t-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
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
The key equation solver block according to the embodiment described in this section uses the following registers:
1) SR0, SR1, . . . , SR2t-1 to save syndrome values,
2) Λ0, Λ1, . . . , Λt-1 to save coefficients of the error locator polynomial,
3) L to save the degree of the error locator polynomial,
4) r to save the step index,
5) Ξ0, Ξ1, . . . , Ξt-1,
6) Γ0, Γ1, . . . , Γt-1,
7) Δpr,
8) Δ, and
9) δ
Initialization
The key equation solver block according to this embodiment is initiated with the following values:
1) SR0.D=S0, SR1.D=S1, . . . , SRt-1.D=St-1;
1) Λ0.D=1, Λ1.D=0, . . . , Λt-1.D=0;
2) Γ0.D=1, Γ1.D=0, . . . , Γt-1.D=0;
3) Δpr=1;
3) L=0; and
4) r=0.
Process
The key equation solver block according to this embodiment consists of two main steps:
1) Computation of the coefficients of the error locator polynomial; and
2) Computation of the coefficients of the error evaluator polynomial.
The computation of the coefficients of the error locator polynomial consists of 2t elementary steps. The qth elementary step consists of 3k clock cycles:



  
    
      
        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
        .
      
    
  



The computation of the coefficients of the error evaluator polynomial consists of t−1 elementary steps.
The qth elementary step consists of k clock cycles:



  
    
      
        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

If R is a register and RE is not assigned, then RE is assumed to be one.
Interface and Registers
Inputs
1. S0, S1, S2t-1 are syndrome values.
2. start is a start signal.
Outputs
1. Λ0, Λ1, Λt-1 are coefficients of the error locator polynomial.
2. Ω0, Ω1, . . . , Ωt-2 are coefficients of the error evaluator polynomial.
3. finish is a finish signal.
4. fail is a fail signal.
Constants
1. n=]t/k[.
2. m=3*k.
3. l=t mod n.
4. if l=0 then q=], otherwise q=2.
Registers
1. SR0, SR1, . . . , SR2t-1 are syndrome registers.
2. Λ0, Λ1, . . . , Λt-1, are registers for the error locator polynomial coefficients.
3. finish is the finish signal register.
4. fail is the fail signal register.
5. L is the register to save the degree of the error locator polynomial.
6. r is a register to save the step index.
7. Ξ0, Ξ1, . . . , Ξt-1.
8. Γ0, Γ1, . . . , Γt-1.
9. T0, T1, . . . , Tm-1 are clock registers for the error locator polynomial calculation.
10. T0′, T1′, Tk-1′ are clock registers for the error evaluator polynomial calculation.
11. M0, M1, . . . , Mn-1 are output registers for the multipliers.
12. Δpr.
13. Δ
14. Δ0.
15. start_omega.
16. calc_omega.
17. Lr.
18. rδ.
19. after_start.
Internal Wires
1. A0, A1, . . . , An-1; B0, B1, . . . , Bn-1 are inputs for the multipliers.
2. LL0, LL1, . . . , LLt-1.
3. δ.
4. sum.
5. sum_control.
Computations



  
    
      
        
          
            
              
                
                  
                    
                      
                        
                          
                            
                              
                                
                                  
                                    
                                      1.
                                      ⁢
                                      
                                        
                                      
                                      ⁢
                                      
                                        
                                          T
                                          0
                                        
                                        .
                                        D
                                      
                                    
                                    =
                                    
                                      
                                        
                                          start
                                          ⋁
                                          
                                            ⫬
                                            
                                              finish
                                              .
                                              Q
                                            
                                          
                                        
                                        &
                                      
                                      ⁢
                                      
                                        MUX
                                        ⁡
                                        
                                          (
                                          
                                            
                                              calc_omega
                                              .
                                              Q
                                            
                                            ,
                                            
                                              

                                            
                                            ⁢
                                            
                                              
                                            
                                            ⁢
                                            
                                              
                                                T
                                                
                                                  m
                                                  -
                                                  1
                                                
                                              
                                              .
                                              Q
                                            
                                            ,
                                            
                                              
                                                T
                                                
                                                  k
                                                  -
                                                  1
                                                
                                              
                                              .
                                              Q
                                            
                                          
                                          )
                                        
                                      
                                    
                                  
                                  ;
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      T
                                      k
                                    
                                    .
                                    D
                                  
                                  =
                                  
                                    
                                      
                                        
                                          ⫬
                                          start
                                        
                                        &
                                      
                                      ⁢
                                      
                                        ⫬
                                        
                                          finish
                                          .
                                          Q
                                        
                                      
                                    
                                    &
                                  
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      
                                        ⫬
                                        
                                          calc_omega
                                          .
                                          Q
                                        
                                      
                                      &
                                    
                                    ⁢
                                    
                                      
                                        T
                                        
                                          k
                                          -
                                          1
                                        
                                      
                                      .
                                      Q
                                    
                                  
                                  ;
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      
                                        T
                                        i
                                      
                                      .
                                      D
                                    
                                    =
                                    
                                      
                                        
                                          
                                            
                                              ⫬
                                              start
                                            
                                            &
                                          
                                          ⁢
                                          
                                            ⫬
                                            
                                              finish
                                              .
                                              Q
                                            
                                          
                                        
                                        &
                                      
                                      ⁢
                                      
                                        
                                          T
                                          
                                            i
                                            -
                                            1
                                          
                                        
                                        .
                                        Q
                                      
                                    
                                  
                                  ,
                                  
                                    

                                  
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    i
                                    =
                                    1
                                  
                                  ,
                                  2
                                  ,
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ,
                                  
                                    k
                                    -
                                    1
                                  
                                  ,
                                  
                                    k
                                    +
                                    1
                                  
                                  ,
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ,
                                  
                                    
                                      m
                                      -
                                      1
                                    
                                    ;
                                  
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      
                                        T
                                        0
                                        ′
                                      
                                      .
                                      D
                                    
                                    =
                                    
                                      
                                        
                                          
                                            
                                              ⫬
                                              
                                                start_omega
                                                .
                                                Q
                                              
                                            
                                            &
                                          
                                          ⁢
                                          
                                            ⫬
                                            
                                              finish
                                              .
                                              Q
                                            
                                          
                                        
                                        &
                                      
                                      ⁢
                                      
                                        
                                          T
                                          
                                            k
                                            -
                                            1
                                          
                                          ′
                                        
                                        .
                                        Q
                                      
                                    
                                  
                                  ;
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      T
                                      
                                        k
                                        -
                                        2
                                      
                                      ′
                                    
                                    =
                                    
                                      
                                        start_omega
                                        .
                                        Q
                                      
                                      ⋁
                                      
                                        (
                                        
                                          
                                            
                                              ⫬
                                              
                                                finish
                                                .
                                                Q
                                              
                                            
                                            &
                                          
                                          ⁢
                                          
                                            
                                              T
                                              
                                                k
                                                -
                                                3
                                              
                                              ′
                                            
                                            .
                                            Q
                                          
                                        
                                        )
                                      
                                    
                                  
                                  ;
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      
                                        T
                                        i
                                        ′
                                      
                                      .
                                      D
                                    
                                    =
                                    
                                      
                                        
                                          
                                            
                                              ⫬
                                              
                                                start_omega
                                                .
                                                Q
                                              
                                            
                                            &
                                          
                                          ⁢
                                          
                                            ⫬
                                            
                                              finish
                                              .
                                              Q
                                            
                                          
                                        
                                        &
                                      
                                      ⁢
                                      
                                        
                                          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
                                                
                                              
                                              &
                                            
                                            ⁢
                                            
                                              
                                                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
                                                            
                                                            &
                                                          
                                                          ⁢
                                                          
                                                            
                                                              
                                                                SR
                                                                
                                                                  
                                                                    (
                                                                    
                                                                      
                                                                        2
                                                                        ⁢
                                                                        t
                                                                      
                                                                      -
                                                                      i
                                                                    
                                                                    )
                                                                  
                                                                  ⁢
                                                                  
                                                                    mod
                                                                    ⁡
                                                                    
                                                                      (
                                                                      
                                                                        2
                                                                        ⁢
                                                                        t
                                                                      
                                                                      )
                                                                    
                                                                  
                                                                
                                                              
                                                              .
                                                              Q
                                                            
                                                            ⋁
                                                            
                                                              
                                                                T
                                                                1
                                                              
                                                              .
                                                              Q
                                                            
                                                          
                                                        
                                                        &
                                                      
                                                      ⁢
                                                      
                                                        
                                                          
                                                            SR
                                                            
                                                              (
                                                              
                                                                
                                                                  2
                                                                  ⁢
                                                                  t
                                                                
                                                                -
                                                                n
                                                                -
                                                                i
                                                              
                                                              )
                                                            
                                                          
                                                          .
                                                          Q
                                                        
                                                        ⋁
                                                        ...
                                                        ⋁
                                                        
                                                          

                                                        
                                                        ⁢
                                                        
                                                          
                                                        
                                                        ⁢
                                                        
                                                          
                                                            T
                                                            
                                                              k
                                                              -
                                                              1
                                                            
                                                          
                                                          .
                                                          Q
                                                        
                                                      
                                                    
                                                    &
                                                  
                                                  ⁢
                                                  
                                                    
                                                      SR
                                                      
                                                        (
                                                        
                                                          
                                                            2
                                                            ⁢
                                                            t
                                                          
                                                          -
                                                          
                                                            
                                                              (
                                                              
                                                                k
                                                                -
                                                                1
                                                              
                                                              )
                                                            
                                                            ⁢
                                                            n
                                                          
                                                          -
                                                          i
                                                        
                                                        )
                                                      
                                                    
                                                    .
                                                    Q
                                                  
                                                
                                                )
                                              
                                              ⋁
                                              
                                                (
                                                
                                                  
                                                    
                                                      T
                                                      k
                                                    
                                                    .
                                                    Q
                                                  
                                                  ⋁
                                                  ...
                                                  ⋁
                                                  
                                                    
                                                      T
                                                      
                                                        
                                                          2
                                                          ⁢
                                                          k
                                                        
                                                        -
                                                        1
                                                      
                                                    
                                                    .
                                                    Q
                                                  
                                                
                                                )
                                              
                                            
                                            &
                                          
                                          ⁢
                                          
                                            
                                              
                                                Δ
                                                pr
                                              
                                              .
                                              Q
                                            
                                            ⋁
                                            
                                              

                                            
                                            ⁢
                                            
                                              
                                            
                                            ⁢
                                            
                                              (
                                              
                                                
                                                  
                                                    T
                                                    
                                                      2
                                                      ⁢
                                                      k
                                                    
                                                  
                                                  .
                                                  Q
                                                
                                                ⋁
                                                ...
                                                ⋁
                                                
                                                  
                                                    T
                                                    
                                                      
                                                        3
                                                        ⁢
                                                        k
                                                      
                                                      -
                                                      1
                                                    
                                                  
                                                  .
                                                  Q
                                                
                                              
                                              )
                                            
                                          
                                        
                                        &
                                      
                                      ⁢
                                      
                                        Δ
                                        .
                                        Q
                                      
                                    
                                  
                                  ,
                                  
                                    i
                                    =
                                    0
                                  
                                  ,
                                  1
                                  ,
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ,
                                  
                                    
                                      l
                                      -
                                      1
                                    
                                    ;
                                  
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  
                                    
                                      A
                                      i
                                    
                                    =
                                    
                                      
                                        
                                          
                                            
                                              
                                                (
                                                
                                                  
                                                    
                                                      
                                                        
                                                          
                                                            
                                                              
                                                                T
                                                                0
                                                              
                                                              .
                                                              Q
                                                            
                                                            &
                                                          
                                                          ⁢
                                                          
                                                            
                                                              
                                                                SR
                                                                
                                                                  
                                                                    (
                                                                    
                                                                      
                                                                        2
                                                                        ⁢
                                                                        t
                                                                      
                                                                      -
                                                                      i
                                                                    
                                                                    )
                                                                  
                                                                  ⁢
                                                                  
                                                                    mod
                                                                    ⁡
                                                                    
                                                                      (
                                                                      
                                                                        2
                                                                        ⁢
                                                                        t
                                                                      
                                                                      )
                                                                    
                                                                  
                                                                
                                                              
                                                              .
                                                              Q
                                                            
                                                            ⋁
                                                            
                                                              T
                                                              1
                                                            
                                                          
                                                          ⁢
                                                          Q
                                                        
                                                        &
                                                      
                                                      ⁢
                                                      
                                                        
                                                          
                                                            SR
                                                            
                                                              (
                                                              
                                                                
                                                                  2
                                                                  ⁢
                                                                  t
                                                                
                                                                -
                                                                n
                                                                -
                                                                i
                                                              
                                                              )
                                                            
                                                          
                                                          .
                                                          Q
                                                        
                                                        ⋁
                                                        ...
                                                        ⋁
                                                        
                                                          

                                                        
                                                        ⁢
                                                        
                                                          
                                                        
                                                        ⁢
                                                        
                                                          
                                                            T
                                                            
                                                              k
                                                              -
                                                              q
                                                            
                                                          
                                                          .
                                                          Q
                                                        
                                                      
                                                    
                                                    &
                                                  
                                                  ⁢
                                                  
                                                    
                                                      SR
                                                      
                                                        (
                                                        
                                                          
                                                            2
                                                            ⁢
                                                            t
                                                          
                                                          -
                                                          
                                                            
                                                              (
                                                              
                                                                k
                                                                -
                                                                q
                                                              
                                                              )
                                                            
                                                            ⁢
                                                            n
                                                          
                                                          -
                                                          i
                                                        
                                                        )
                                                      
                                                    
                                                    .
                                                    Q
                                                  
                                                
                                                )
                                              
                                              ⋁
                                              
                                                (
                                                
                                                  
                                                    
                                                      T
                                                      k
                                                    
                                                    .
                                                    Q
                                                  
                                                  ⋁
                                                  ...
                                                  ⋁
                                                  
                                                    
                                                      T
                                                      
                                                        k
                                                        -
                                                        1
                                                      
                                                    
                                                    .
                                                    Q
                                                  
                                                
                                                )
                                              
                                            
                                            &
                                          
                                          ⁢
                                          
                                            
                                              
                                                Δ
                                                pr
                                              
                                              .
                                              Q
                                            
                                            ⋁
                                            
                                              

                                            
                                            ⁢
                                            
                                              
                                            
                                            ⁢
                                            
                                              (
                                              
                                                
                                                  
                                                    T
                                                    
                                                      2
                                                      ⁢
                                                      k
                                                    
                                                  
                                                  .
                                                  Q
                                                
                                                ⋁
                                                ...
                                                ⋁
                                                
                                                  
                                                    T
                                                    
                                                      
                                                        3
                                                        ⁢
                                                        k
                                                      
                                                      -
                                                      1
                                                    
                                                  
                                                  .
                                                  Q
                                                
                                              
                                              )
                                            
                                          
                                        
                                        &
                                      
                                      ⁢
                                      
                                        Δ
                                        .
                                        Q
                                      
                                    
                                  
                                  ,
                                  
                                    i
                                    =
                                    l
                                  
                                  ,
                                  
                                    l
                                    +
                                    1
                                  
                                  ,
                                  ...
                                  ⁢
                                  
                                    
                                  
                                  ,
                                  
                                    n
                                    -
                                    1.
                                  
                                
                                ⁢
                                
                                  

                                
                                ⁢
                                
                                  
                                    4.
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      B
                                      0
                                    
                                  
                                  =
                                  
                                    (
                                    
                                      
                                        
                                          
                                            
                                              
                                                
                                                  
                                                    
                                                      (
                                                      
                                                        
                                                          
                                                            T
                                                            0
                                                          
                                                          .
                                                          Q
                                                        
                                                        ⋁
                                                        
                                                          
                                                            T
                                                            k
                                                          
                                                          .
                                                          Q
                                                        
                                                      
                                                      )
                                                    
                                                    &
                                                  
                                                  ⁢
                                                  
                                                    
                                                      Λ
                                                      0
                                                    
                                                    ⋁
                                                    
                                                      (
                                                      
                                                        
                                                          T
                                                          1
                                                        
                                                        ·
                                                        
                                                          Q
                                                          ⋁
                                                          
                                                            
                                                              T
                                                              
                                                                k
                                                                +
                                                                1
                                                              
                                                            
                                                            .
                                                            Q
                                                          
                                                        
                                                      
                                                      )
                                                    
                                                  
                                                
                                                &
                                              
                                              ⁢
                                              
                                                
                                                  Λ
                                                  n
                                                
                                                ⋁
                                              
                                            
                                            ...
                                          
                                          ⋁
                                          
                                            

                                          
                                          ⁢
                                          
                                            
                                          
                                          ⁢
                                          
                                            (
                                            
                                              
                                                
                                                  T
                                                  
                                                    k
                                                    -
                                                    1
                                                  
                                                
                                                .
                                                Q
                                              
                                              ⋁
                                              
                                                
                                                  T
                                                  
                                                    
                                                      2
                                                      ⁢
                                                      k
                                                    
                                                    -
                                                    1
                                                  
                                                
                                                .
                                                Q
                                              
                                            
                                            )
                                          
                                        
                                        &
                                      
                                      ⁢
                                      
                                        Λ
                                        
                                          
                                            (
                                            
                                              k
                                              -
                                              1
                                            
                                            )
                                          
                                          ⁢
                                          n
                                        
                                      
                                    
                                    )
                                  
                                
                              
                              )
                            
                            ⋁
                            
                              (
                              
                                
                                  
                                    
                                      
                                        
                                          
                                            
                                              T
                                              
                                                
                                                  2
                                                  ⁢
                                                  k
                                                
                                                +
                                                1
                                              
                                            
                                            .
                                            Q
                                          
                                          &
                                        
                                        ⁢
                                        
                                          
                                            
                                              Γ
                                              
                                                n
                                                -
                                                1
                                              
                                            
                                            .
                                            Q
                                          
                                          ⋁
                                          
                                            
                                              T
                                              
                                                
                                                  2
                                                  ⁢
                                                  k
                                                
                                                +
                                                2
                                              
                                            
                                            .
                                            Q
                                          
                                        
                                      
                                      &
                                    
                                    ⁢
                                    
                                      

                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      
                                        
                                          Γ
                                          
                                            
                                              2
                                              ⁢
                                              n
                                            
                                            -
                                            1
                                          
                                        
                                        .
                                        Q
                                      
                                      ⋁
                                      ...
                                      ⋁
                                      
                                        
                                          T
                                          
                                            
                                              3
                                              ⁢
                                              k
                                            
                                            -
                                            1
                                          
                                        
                                        .
                                        Q
                                      
                                    
                                  
                                  &
                                
                                ⁢
                                
                                  
                                    Γ
                                    
                                      
                                        
                                          (
                                          
                                            k
                                            -
                                            1
                                          
                                          )
                                        
                                        ⁢
                                        n
                                      
                                      -
                                      1
                                    
                                  
                                  .
                                  Q
                                
                              
                              )
                            
                          
                          ;
                        
                        ⁢
                        
                          

                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            B
                            i
                          
                          =
                          
                            (
                            
                              
                                
                                  
                                    
                                      
                                        
                                          (
                                          
                                            
                                              
                                                T
                                                0
                                              
                                              .
                                              Q
                                            
                                            ⋁
                                            
                                              
                                                T
                                                k
                                              
                                              .
                                              Q
                                            
                                          
                                          )
                                        
                                        &
                                      
                                      ⁢
                                      
                                        
                                          Λ
                                          i
                                        
                                        ⋁
                                        
                                          (
                                          
                                            
                                              
                                                T
                                                1
                                              
                                              .
                                              Q
                                            
                                            ⋁
                                            
                                              
                                                T
                                                
                                                  k
                                                  -
                                                  1
                                                
                                              
                                              .
                                              Q
                                            
                                          
                                          )
                                        
                                      
                                    
                                    &
                                  
                                  ⁢
                                  
                                    
                                      Λ
                                      
                                        n
                                        +
                                        i
                                      
                                    
                                    ⋁
                                    ...
                                    ⋁
                                    
                                      

                                    
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      (
                                      
                                        
                                          
                                            T
                                            
                                              k
                                              -
                                              1
                                            
                                          
                                          .
                                          Q
                                        
                                        ⋁
                                        
                                          
                                            T
                                            
                                              
                                                2
                                                ⁢
                                                k
                                              
                                              -
                                              1
                                            
                                          
                                          .
                                          Q
                                        
                                      
                                      )
                                    
                                  
                                
                                &
                              
                              ⁢
                              
                                Λ
                                
                                  
                                    
                                      (
                                      
                                        k
                                        -
                                        1
                                      
                                      )
                                    
                                    ⁢
                                    n
                                  
                                  -
                                  1
                                
                              
                            
                            )
                          
                        
                      
                      )
                    
                    ⋁
                    
                      (
                      
                        
                          
                            
                              
                                
                                  
                                    
                                      T
                                      
                                        2
                                        ⁢
                                        k
                                      
                                    
                                    .
                                    Q
                                  
                                  &
                                
                                ⁢
                                
                                  
                                    
                                      Γ
                                      
                                        i
                                        -
                                        1
                                      
                                    
                                    .
                                    Q
                                  
                                  ⋁
                                  
                                    
                                      T
                                      
                                        
                                          2
                                          ⁢
                                          k
                                        
                                        +
                                        1
                                      
                                    
                                    .
                                    Q
                                  
                                
                              
                              &
                            
                            ⁢
                            
                              

                            
                            ⁢
                            
                              
                            
                            ⁢
                            
                              
                                
                                  Γ
                                  
                                    n
                                    +
                                    i
                                    -
                                    1
                                  
                                
                                .
                                Q
                              
                              ⋁
                              ...
                              ⋁
                              
                                
                                  T
                                  
                                    
                                      3
                                      ⁢
                                      k
                                    
                                    -
                                    1
                                  
                                
                                .
                                Q
                              
                            
                          
                          &
                        
                        ⁢
                        
                          
                            Γ
                            
                              
                                
                                  (
                                  
                                    k
                                    -
                                    1
                                  
                                  )
                                
                                ⁢
                                n
                              
                              +
                              i
                              -
                              1
                            
                          
                          .
                          Q
                        
                      
                      )
                    
                  
                  ,
                  
                    i
                    =
                    1
                  
                  ,
                  2
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    
                      l
                      -
                      1
                    
                    ;
                  
                
                ⁢
                
                  

                
                ⁢
                
                  
                
                ⁢
                
                  
                    B
                    i
                  
                  =
                  
                    (
                    
                      
                        
                          
                            
                              
                                
                                  (
                                  
                                    
                                      
                                        T
                                        0
                                      
                                      .
                                      Q
                                    
                                    ⋁
                                    
                                      
                                        T
                                        k
                                      
                                      .
                                      Q
                                    
                                  
                                  )
                                
                                &
                              
                              ⁢
                              
                                
                                  Λ
                                  i
                                
                                ⋁
                                
                                  (
                                  
                                    
                                      
                                        T
                                        1
                                      
                                      .
                                      Q
                                    
                                    ⋁
                                    
                                      
                                        T
                                        
                                          k
                                          +
                                          1
                                        
                                      
                                      .
                                      Q
                                    
                                  
                                  )
                                
                              
                            
                            &
                          
                          ⁢
                          
                            
                              Λ
                              
                                n
                                +
                                i
                              
                            
                            ⋁
                            ...
                            ⋁
                            
                              

                            
                            ⁢
                            
                              
                            
                            ⁢
                            
                              (
                              
                                
                                  
                                    T
                                    
                                      k
                                      -
                                      q
                                    
                                  
                                  .
                                  Q
                                
                                ⋁
                                
                                  
                                    T
                                    
                                      
                                        2
                                        ⁢
                                        k
                                      
                                      -
                                      q
                                    
                                  
                                  .
                                  Q
                                
                              
                              )
                            
                          
                        
                        &
                      
                      ⁢
                      
                        Λ
                        
                          
                            
                              (
                              
                                k
                                -
                                q
                              
                              )
                            
                            ⁢
                            n
                          
                          +
                          i
                        
                      
                    
                    )
                  
                
              
              )
            
            ⋁
            
              (
            
          
          ⁢
          
            
              T
              
                2
                ⁢
                k
              
            
            .
            Q
          
        
        &
      
      ⁢
      
        
          
            Γ
            
              i
              -
              1
            
          
          .
          Q
        
        ⋁
        
          
            T
            
              
                2
                ⁢
                k
              
              +
              1
            
          
          .
          Q
        
      
    
    &
  




  
    
      
    
    ⁢
    
      
        
          
            
              
                Γ
                
                  n
                  +
                  i
                  -
                  1
                
              
              .
              Q
            
            ⋁
            ...
            ⋁
            
              
                T
                
                  
                    3
                    ⁢
                    k
                  
                  -
                  q
                
              
              .
              Q
            
          
          &
        
        ⁢
        
          
            Γ
            
              
                
                  (
                  
                    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
                  
                  &
                
                ⁢
                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
                    
                  
                  )
                
                &
              
              ⁢
              
                
                  T
                  
                    k
                    -
                    1
                  
                
                .
                Q
                .
                
                  

                
                ⁢
                11.
              
              ⁢
              
                
              
              ⁢
              δ
            
            =
            
              
                
                  
                    
                      
                        
                          L
                          r
                        
                        .
                        Q
                      
                      &
                    
                    ⁢
                    
                      
                        Δ
                        0
                      
                      .
                      Q
                    
                  
                  &
                
                ⁢
                
                  ⫬
                  
                    
                      calc_omega
                      .
                      Q
                      .
                      
                        

                      
                      ⁢
                      12.
                    
                    ⁢
                    
                      
                    
                    ⁢
                    r
                    ⁢
                    
                      
                    
                    ⁢
                    
                      δ
                      .
                      D
                    
                  
                
              
              =
              δ
            
          
        
      
      ;
      
        
          r
          ⁢
          
            
          
          ⁢
          
            δ
            .
            E
          
        
        =
        
          
            
              
                T
                
                  k
                  +
                  2
                
              
              .
              Q
              .
              
                

              
              ⁢
              13.
            
            ⁢
            
              
            
            ⁢
            
              
                Δ
                pr
              
              .
              D
            
          
          =
          
            
              (
              
                
                  start
                  &
                
                ⁢
                1
              
              )
            
            ⋁
            
              Δ
              .
              Q
            
          
        
      
      ;
    
  




  
    
      
    
    ⁢
    
      
        
          
            
              Δ
              pr
            
            .
            E
          
          =
          
            
              
                start
                ⋁
                
                  
                    (
                    
                      
                        
                          r
                          ⁢
                          
                            
                          
                          ⁢
                          
                            δ
                            .
                            Q
                          
                        
                        &
                      
                      ⁢
                      
                        
                          T
                          
                            
                              2
                              ⁢
                              k
                            
                            -
                            1
                          
                        
                        .
                        Q
                      
                    
                    )
                  
                  .
                  
                    

                  
                  ⁢
                  14.
                
              
              ⁢
              
                
              
              ⁢
              
                L
                .
                D
              
            
            =
            
              
                
                  ⫬
                  start
                
                &
              
              ⁢
              
                (
                
                  
                    r
                    .
                    Q
                  
                  +
                  1
                  -
                  
                    L
                    .
                    Q
                  
                
                )
              
            
          
        
        ;
        
          
            L
            .
            E
          
          =
          
            
              start
              ⋁
              
                δ
                .
                
                  

                
                ⁢
                15.
              
            
            ⁢
            
              
            
            ⁢
            
              Ξ
              i
            
          
        
      
      ,
      
        D
        =
        
          
            
              ⫬
              start
            
            &
          
          ⁢
          
            
              M
              
                i
                ⁢
                
                  
                
                ⁢
                mod
                ⁢
                
                  
                
                ⁢
                n
              
            
            .
            Q
          
        
      
      ,
      
        
          
            Ξ
            i
          
          .
          E
        
        =
        
          start
          ⋁
          
            
              T
              
                k
                +
                1
                +
                
                  i
                  /
                  n
                
              
            
            .
            Q
          
        
      
      ,
      
        

      
      ⁢
      
        
      
      ⁢
      
        i
        =
        0
      
      ,
      1
      ,
      ...
      ⁢
      
        
      
      ,
      
        t
        -
        1.
      
    
  




  
    
      
        16.
        ⁢
        
          
        
        ⁢
        
          
            Γ
            0
          
          .
          D
        
      
      =
      
        
          (
          
            
              start
              &
            
            ⁢
            1
          
          )
        
        ⋁
        
          (
          
            
              
                r
                ⁢
                
                  
                
                ⁢
                
                  δ
                  .
                  Q
                
              
              &
            
            ⁢
            
              
                Λ
                0
              
              .
              Q
            
          
          )
        
        ⋁
        
          (
          
            
              
                Δ
                .
                Q
              
              &
            
            ⁢
            
              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
            
            &
          
          ⁢
          
            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
                
                &
              
              ⁢
              
                LL
                i
              
            
          
        
      
    
    ,
    
      

    
    ⁢
    
      
    
    ⁢
    
      i
      =
      1
    
    ,
    2
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        t
        -
        1
      
      ;
      
        

      
      ⁢
      
        
      
      ⁢
      
        
          
            Λ
            i
          
          .
          E
        
        =
        
          
            
              start
              ⋁
              
                
                  T
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                      +
                      
                        i
                        .
                        n
                      
                    
                    )
                  
                
                .
                Q
              
            
            &
          
          ⁢
          
            ⫬
            
              calc_omega
              .
              Q
            
          
        
      
    
    ,
    
      

    
    ⁢
    
      
    
    ⁢
    
      i
      =
      0
    
    ,
    1
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        t
        -
        2
      
      ;
    
  




  
    
      
    
    ⁢
    
      
        
          after_start
          .
          D
        
        =
        start
      
      ;
    
  




  
    
      
    
    ⁢
    
      
        
          
            Λ
            
              t
              -
              1
            
          
          .
          E
        
        =
        
          
            
              start
              ⋁
              
                
                  (
                  
                    
                      
                        
                          
                            
                              T
                              0
                            
                            .
                            Q
                          
                          &
                        
                        ⁢
                        
                          ⫬
                          
                            calc_omega
                            .
                            Q
                          
                        
                      
                      &
                    
                    ⁢
                    
                      ⫬
                      
                        after_start
                        .
                        Q
                      
                    
                  
                  )
                
                .
                
                  

                
                ⁢
                19.
              
            
            ⁢
            
              
            
            ⁢
            
              fail
              .
              D
            
          
          =
          
            
              
                
                  (
                  
                    
                      L
                      .
                      Q
                    
                    ≤
                    t
                  
                  )
                
                .
                
                  

                
                ⁢
                20.
              
              ⁢
              
                
              
              ⁢
              
                r
                .
                D
              
            
            =
            
              
                
                  
                    
                      ⫬
                      start
                    
                    &
                  
                  ⁢
                  
                    ⫬
                    
                      start_omega
                      .
                      Q
                    
                  
                
                &
              
              ⁢
              
                (
                
                  
                    r
                    .
                    Q
                  
                  +
                  1
                
                )
              
            
          
        
      
      ;
    
  




  
    
      
    
    ⁢
    
      
        
          r
          .
          E
        
        =
        
          
            
              start
              ⋁
              
                
                  T
                  
                    m
                    -
                    1
                  
                
                .
                Q
              
              ⋁
              
                
                  T
                  
                    k
                    -
                    1
                  
                  ′
                
                .
                Q
                .
                
                  

                
                ⁢
                21.
              
            
            ⁢
            
              
            
            ⁢
            
              start_omega
              .
              D
            
          
          =
          
            
              
                
                  
                    
                      ⫬
                      start
                    
                    &
                  
                  ⁢
                  
                    (
                    
                      
                        r
                        .
                        Q
                      
                      ==
                      
                        
                          2
                          *
                          t
                        
                        -
                        1
                      
                    
                    )
                  
                
                &
              
              ⁢
              
                
                  T
                  
                    m
                    -
                    2
                  
                
                .
                Q
                .
                
                  

                
                ⁢
                22.
              
              ⁢
              
                
              
              ⁢
              
                calc_omega
                .
                D
              
            
            =
            
              
                
                  
                    
                      
                        ⫬
                        start
                      
                      &
                    
                    ⁢
                    
                      ⫬
                      
                        finish
                        .
                        Q
                      
                    
                  
                  &
                
                ⁢
                
                  
                    (
                    
                      
                        start_omega
                        .
                        Q
                      
                      ⋁
                      
                        

                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        calc_omega
                        .
                        Q
                      
                    
                    )
                  
                  .
                  
                    

                  
                  ⁢
                  23.
                
                ⁢
                
                  
                
                ⁢
                
                  Ω
                  i
                
              
              =
              
                
                  Γ
                  
                    t
                    -
                    2
                    -
                    i
                  
                
                .
                Q
              
            
          
        
      
      ,
      
        i
        =
        0
      
      ,
      1
      ,
      ...
      ⁢
      
        
      
      ,
      
        
          t
          -
          
            2.
            ⁢
            
              

            
            ⁢
            24.
            ⁢
            
              
            
            ⁢
            
              finish
              .
              D
            
          
        
        =
        
          
            
              
                
                  
                    T
                    
                      k
                      -
                      1
                    
                    ′
                  
                  .
                  Q
                
                &
              
              ⁢
              
                ⫬
                
                  finish
                  .
                  Q
                
              
            
            &
          
          ⁢
          
            
              (
              
                
                  r
                  .
                  Q
                
                ==
                
                  t
                  -
                  1
                
              
              )
            
            .
          
        
      
    
  



Key Equation Solver Block Scheme

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 SRi. Block T (FIG. 2) contains the generator for the control sequence Ti that governs one iteration of the iBM algorithm. Blocks Ai and Bi (FIGS. 4 and 6 (and FIG. 5 for Block B0) respectively) act as multiplexers, switching the inputs of the multiplier units to the proper values for the current clock cycle, as indicated by Ti.
The outputs of the multiplier units are stored in the registers Mi. The partial results of the calculation of the new value for the error locator polynomial are stored in blocks ACCi (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, 7B, and 7C) 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 Ti. Block Δ (FIG. 3C) is used for the iterative calculation of the value Δ. FIG. 3A depicts Block SAi.
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.
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.

## Claims

1. In a key equation solver block for a processor-based BCH decoder, the improvement comprising the key equation solver block having a number of multiplier units specified by X, where:


t*(7*t−1)/(codeword_len−3)≦X<(t+1),

where t is a non-zero number of transmission errors for the key equation solver block to correct using the processor, and codeword_len is a length, greater than 3, of a transmitted codeword to be decoded by the processor-based BCH decoder.