# Patent

## Title
Incremental generation of polynomials for decoding reed-solomon codes

## Abstract

Generating a polynomial is disclosed. A prior error locator polynomial, associated with locating errors in encoded data, is obtained. A new error locator polynomial, associated with a test error pattern, is incrementally generated based at least in part on the prior error locator polynomial.

## Background
BACKGROUND OF THE INVENTION
Chase decoding is a soft-decision decoding technique for algebraic codes where an efficient bounded-distance decoder is available. The straightforward approach to perform Chase decoding is to repeatedly flip test error patterns and perform a full Berlekamp-Massey process for each test error pattern. From a computational point of view, this has a complexity of O(nd), where n denotes the code length and d denotes the minimum Hamming distance. In hardware implementations (e.g., implemented as an Application Specific Integrated Circuit (ASIC) or Field Programmable Gate Array (FPGA)) and software implementations (e.g., a computer program) performing Chase decoding in a straightforward manner requires increasing amounts of time as the code length and/or the minimum Hamming distance increase. Techniques to perform Chase decoding in less time would be useful.



BRIEF DESCRIPTION OF THE DRAWINGS
Various embodiments of the invention are disclosed in the following detailed description and the accompanying drawings.
FIG. 1 is a diagram illustrating an embodiment of a Reed-Solomon decoder.
FIG. 2 is a diagram illustrating an embodiment of test error patterns associated with a Chase decoding process.
FIG. 3 is a flowchart illustrating an embodiment of a process for incrementally generating error locator polynomials.
FIG. 4 is a flowchart illustrating an embodiment of a process for initialization associated with incrementally generating error locator polynomials.
FIG. 5 is a flowchart illustrating an embodiment of a process for performing error correction using polynomials selected from an incrementally generated group.



DETAILED DESCRIPTION
The invention can be implemented in numerous ways, including as a process, an apparatus, a system, a composition of matter, a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. A component such as a processor or a memory described as being configured to perform a task includes both a general component that is temporarily configured to perform the task at a given time or a specific component that is manufactured to perform the task. In general, the order of the steps of disclosed processes may be altered within the scope of the invention.
A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured.
A Chase decoder that generates a new error locator polynomial using interpolation and linear feedback shift register techniques is disclosed. In some embodiments, after performing a full Berlekamp-Massey process once, a new error locator polynomial is obtained by flipping a test error pattern and employing an interpolation-based linear feedback shift register, rather than repeatedly going through the full Berlekamp-Massey process which takes d−1 iterations, where d denotes the minimum Hamming distance. In some embodiments, there are multiple interpolation-based linear feedback shift registers operating in parallel. From a computational point of view, this requires complexity O(n) in attempting to determine a codeword, compared to O(nd) when straightforwardly utilizing the Berlekamp-Massey process, where n denotes the code length and d denotes the minimum Hamming distance.
Although the embodiments described herein discuss a Chase decoder to process Reed-Solomon codes, the techniques described may be modified as appropriate for other codes. In some embodiments, other codes such as Bose, Ray-Chaudhuri, Hocquenghem (BCH) codes and generalized Reed-Solomon codes are processed.
FIG. 1 is a diagram illustrating an embodiment of a Reed-Solomon decoder. In the example shown, for a Reed-Solomon C(n, k) code over a Galois Field of GF(q), a k-symbol data word D[Dk−1, Dk−2, . . . , D1, D0] is encoded to produce an n-symbol codeword C[Cn−1, Cn−2, . . . , C1, C0]. Another way of expressing this is that a data word polynomial D(x)=Dk−1xk−1+Dk−2xk−2+ . . . +D1x1+D0 is encoded to produce a codeword polynomial C(x)=Cn−1xn−1+Cn−2xn−2+ . . . +C1x+C0, by means of a generator polynomial




  
    
      G
      ⁡
      
        (
        x
        )
      
    
    ⁢
    
      =
      Δ
    
    ⁢
    
      
        ∏
        
          i
          =
          0
        
        
          n
          -
          k
          -
          1
        
      
      ⁢
      
        
      
      ⁢
      
        (
        
          x
          -
          
            α
            
              
                m
                0
              
              +
              i
            
          
        
        )
      
    
  
  ,




where m0 is typically 0 or 1 and α is a primitive element of GF(q). As used herein, vector A=[A0, A1, A2, . . . , Al] and its polynomial representation A(x)=A0+A1x+A2x2+ . . . Alxl may be used interchangeably. In some embodiments, a polynomial of degree less than n is a codeword polynomial if and only if it is a multiple of the generator polynomial, G(x). A codeword polynomial C(x) satisfies

C(αm0+i)=0, i=0,1,2, . . . , n−k−1.

The minimum Hamming distance of the code is dmin=n−k+1, a feature known as maximally-distance-separable. For purposes of illustration, the examples described herein consider the specific case where q=2m (i.e., GF(2m)), instead of the general case where GF(pm), and m0=1. In other words, the code illustrated in this embodiment is defined such that n−k=2t (where t is the error-correction capability). Although examples described herein consider the above specific case, in some embodiments, other cases may be used.
A systematic encoding generates a codeword that is comprised of the data word and parity-check symbols. To generate a codeword, let Ψ(x)Ψ2t−1x2t−1+Ψ2t−2x2t−2+ . . . +Ψ1x+Ψ0 denote the remainder when x2tD(x) is divided by G(x) . The polynomial x2tD(x)−Ψ(x) is then a multiple of G(x) and is denoted as a systematic codeword polynomial; alternatively, C=[Dk−1, Dk−2, . . . , D0, −Ψ2t−1, −Ψ2t−2, . . . , −Ψ0].
Let C(x) denote the transmitted codeword polynomial and R(x) the received word polynomial after appropriate channel quantization. The received word polynomial, R(x), is passed to decoder 100 and may include some errors. The decoding objective is to determine the error polynomial E(x) such that C(x)=R(x)−E(x) . That is, decoder 100 attempts to produce the original codeword, C(x), using the received polynomial, R(x) .
Syndrome generator 102 generates syndrome values using the received polynomial, R(x) . Syndrome values are computed using:

Si=R(αi+1)=C(αi+1)+E(αi+1)=E(αi+1), i=0,1,2, . . . , 2t−1.

If all 2t syndrome values are zero, then R(x) is a codeword and it may be assumed that C(x)=R(x), i.e., no errors have occurred. Otherwise, the decoder attempts to solve the following equation system:





  {
  
    
      
        
          
            
              Y
              1
            
            ⁢
            
              X
              1
              1
            
          
          +
        
      
      
        
          
            
              Y
              2
            
            ⁢
            
              X
              2
              1
            
          
          +
        
      
      
        
          ...
          ⁢
          
            
          
          +
        
      
      
        
          
            Y
            e
          
          ⁢
          
            X
            e
            1
          
        
      
      
        
          =
          
            S
            0
          
        
      
    
    
      
        
          
            
              Y
              1
            
            ⁢
            
              X
              1
              2
            
          
          +
        
      
      
        
          
            
              Y
              2
            
            ⁢
            
              X
              2
              2
            
          
          +
        
      
      
        
          ...
          ⁢
          
            
          
          +
        
      
      
        
          
            Y
            e
          
          ⁢
          
            X
            e
            2
          
        
      
      
        
          =
          
            S
            1
          
        
      
    
    
      
        
          
        
      
      
        
          
        
      
      
        
          
        
      
      
        
          
        
      
      
        ⋮
      
    
    
      
        
          
            
              Y
              1
            
            ⁢
            
              X
              1
              
                2
                ⁢
                t
              
            
          
          +
        
      
      
        
          
            
              Y
              2
            
            ⁢
            
              X
              2
              
                2
                ⁢
                t
              
            
          
          +
        
      
      
        
          ...
          ⁢
          
            
          
          +
        
      
      
        
          
            Y
            e
          
          ⁢
          
            X
            e
            
              2
              ⁢
              t
            
          
        
      
      
        
          =
          
            S
            
              
                2
                ⁢
                t
              
              -
              1
            
          
        
      
    
  




where e denotes the (unknown) number of errors, X1, X2, . . . , Xe denote the error locations, and Y1, Y2, . . . , Ye denote the corresponding error magnitudes.

The syndrome polynomial generated by syndrome generator 102 is defined to be:

S(x)S0+S1x+S2x2+ . . . +S2t−1x2t−1.   (1)

The syndromes (i.e., the coefficients of the syndrome polynomial) are passed from syndrome generator 102 to error polynomial generator 104. Error polynomial generator 104 generates the error locator polynomial, Λ(x) , which is defined to be:




  
    
      
        
          Λ
          ⁡
          
            (
            x
            )
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            
              ∏
              
                i
                =
                1
              
              e
            
            ⁢
            
              
            
            ⁢
            
              (
              
                1
                -
                
                  
                    X
                    i
                  
                  ⁢
                  x
                
              
              )
            
          
          =
          
            1
            +
            
              
                Λ
                1
              
              ⁢
              x
            
            +
            
              
                Λ
                2
              
              ⁢
              
                x
                2
              
            
            +
            ...
            +
            
              
                Λ
                e
              
              ⁢
              
                
                  x
                  e
                
                .
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




Additional polynomials besides the error locator polynomial may be generated by error polynomial generator 104.
The error evaluator polynomial is defined to be:




  
    
      
        
          Ω
          ⁡
          
            (
            x
            )
          
        
        ⁢
        
          =
          Δ
        
        ⁢
        
          
            
              ∑
              
                i
                =
                1
              
              e
            
            ⁢
            
              
            
            ⁢
            
              
                Y
                i
              
              ⁢
              
                X
                i
              
              ⁢
              
                
                  ∏
                  
                    
                      j
                      =
                      1
                    
                    ,
                    
                      j
                      ≠
                      i
                    
                  
                  e
                
                ⁢
                
                  
                
                ⁢
                
                  (
                  
                    1
                    -
                    
                      
                        X
                        j
                      
                      ⁢
                      x
                    
                  
                  )
                
              
            
          
          =
          
            
              Ω
              0
            
            +
            
              
                Ω
                1
              
              ⁢
              x
            
            +
            
              
                Ω
                2
              
              ⁢
              
                x
                2
              
            
            +
            ...
            +
            
              
                Ω
                
                  e
                  -
                  1
                
              
              ⁢
              
                
                  x
                  
                    e
                    -
                    1
                  
                
                .
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




The three polynomials satisfy the following equation:

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

The Berlekamp-Massey method can be used to solve equation 4, given that the number of errors e does not exceed the error-correction capability t . The essence of the Berlekamp-Massey method is to determine a minimum-length linear feedback shift register (LFSR) that generates the syndrome sequence S0, S1, S2, . . . , S2t−1, where an LFSR of length L, a0, a1, a2, . . . , aL, generates the sequence S0, S1, S2, . . . , S2t−1 if




  
    
      
        
          
            
              ∑
              
                j
                =
                0
              
              L
            
            ⁢
            
              
            
            ⁢
            
              
                S
                
                  i
                  -
                  j
                
              
              ⁢
              
                a
                j
              
            
          
          =
          0
        
        ,
        
          
        
        ⁢
        
          i
          =
          L
        
        ,
        
          L
          +
          1
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          
            2
            ⁢
            t
          
          -
          1.
        
      
    
    
      
        (
        5
        )
      
    
  




More specifically, the Berlekamp-Massey method produces two polynomials, Λ(x) and B(x) as characterized by the following lemma.
Lemma 1 (i). Λ(x) is a minimum-length LFSR that generates the sequence S0, S1, S2, . . . , S2t−1. B(x) is a minimum-length LFSR that generates the sequence S0, S1, S2, . . . , S2t−2 but not S0, S1, S2, . . . , S2t−1.
(ii). The degrees of Λ(x) and B(x), denoted by LΛ and LB respectively, satisfy

LΛ+LB=2t.   (6)

(iii). The polynomials Λ(x) and B(x) are relatively prime, i.e., the two do not share a common factor.
It is worth mentioning that there may exist multiple minimum-length LFSRs that generate the sequence S0, S1, S2, . . . , S2t−1, and Λ(x) obtained from the
Berlekamp-Massy process is one of them when non-unique. Note also that “a polynomial a(x) generating the sequence S0, S1, S2, . . . , S2t−1” is equivalent to “the degree of the polynomial a(x)S(x) (mod x2t) less than that of a(x).”
Note in this presentation an error locator polynomial does not have to be normalized. For notational convenience, the following is defined

Θ(x)B(x)S(x) (mod x2t−1).   (7)

Note that the above definition differs slightly from that of Ω(x) which takes mod x2t, due to the fact that Λ(x) generates S0, S1, S2, . . . , S2t−1; whereas B(x) generates only S0, S1, S2, . . . , S2t−2.
The error locator polynomial, Λ(x) , is passed from error polynomial generator 104 to error locator 106. Error locations may correspond to the roots, Xi, of the error locator polynomial, Λ(x) . Error locator 106 may use a Chien search method to determine error locations.
Error evaluator 108 determines the error magnitudes, Yi . Error locations are received from error locator 106 and are used to determine the error magnitudes. Some Reed Solomon decoders use the Forney formula to determine the error magnitudes. Other error magnitude formulas besides the Forney formula may be determined and used to generate the error magnitudes. For example, error magnitudes formulas that allow reduced hardware or reduced clock cycles may be preferred. In some embodiments, the error magnitude formula may allow improvements in other blocks besides the error evaluator. For example, using some error magnitude formulas, error polynomial generator 104 or error locator 106 may also be improved.
Error corrector 110 uses the error magnitudes and error locations to correct the received polynomial, R(x). If the error correction capability of the code is able to correct for the received errors, E(x), then the output of error corrector 110 is C(x), the codeword originally transmitted.
Decoder 100 can be used in a variety of applications. In some embodiments, decoder 100 is used in a storage system, such as a disk drive system. Data written to a storage medium is encoded (e.g., using a Reed-Solomon code) and the stored data is decoded (e.g., using the incremental polynomial generation technique described herein) when read back. Other applications of decoder 100, and thus the incremental polynomial generation technique, include compact disk players, digital televisions, wireless communication (e.g., satellites), and wired communication (e.g., Asymmetric Digital Subscriber Line (ADSL) modems).
FIG. 2 is a diagram illustrating an embodiment of test error patterns associated with a Chase decoding process. In the example shown, τ=3, where τ is the number of symbols identified to have an error by a soft output Viterbi decoder. In a straightforward Chase decoding process, all combinations of a set of τ(τ≦t) symbol error patterns are flipped, each time applying bounded-distance decoding to that particular combination of flipped/non-flipped symbol error patterns. The most likely codeword, if any, is selected from the decoded candidate codewords.
In this section, an incremental generation technique is described to determine valid error locator polynomials. In some embodiments, the incremental generation technique is performed in one-pass. By one-pass, it is meant that one iteration can be performed in a constant number of steps or amount of time, independent of code length, n, as well as the error-correction capability, t, when the process is performed in parallel.
The diagram shown illustrates one embodiment of a flipping sequence. In discussing how to incrementally generate error locator polynomials, processing with respect to one branch is described and it is to be understood that the operations performed in one branch are repeated for other branches. To obtain test error pattern 208, an initial dataword 200 is flipped at bit pattern Y1 at symbol X1. To obtain test error pattern 209 from test error pattern 208, bit pattern Y2 at symbol X2 is flipped.
Error locator polynomials in this example are first incrementally generated for the first branch (202), where incrementally generating includes generating based on a prior version or iteration of that polynomial. For example, an error locator polynomial is generated for test error pattern 208 based on the error locator polynomial associated with initial dataword 200. The error locator polynomial for test error pattern 209 is based on that for 208 and similarly the error locator polynomial for test error pattern 210 is based on that for 209. The process is repeated for the second branch (204) and the third branch (206). At the start of each branch the process is reinitialized using data associated with initial dataword 200.
A tree structure (identical or similar to that shown in this figure) may be a memory efficient way of incrementally generating error locator polynomials. By using a tree structure, it may not be necessary to store all error locator polynomials generated as the tree is traversed. In some embodiments, only the best (or one of the best) error locator polynomials generated is used in subsequent processing, such as a Chien search to find the error locations using the best error locator polynomial, error correction, etc. Thus, it may be sufficient to store the current best error locator polynomial (to be used subsequently) and the immediately prior error locator polynomial (used to incrementally generate the current error locator polynomial). In some embodiments, a different sequence of test patterns (and correspondingly a difference sequence of generating error locator polynomials) is used compared to that illustrated. For example, it is not necessary to use a tree structure or a different tree structure is used.
Let (X1, Y1), (X2, Y2), . . . , (Xτ, Yτ), where Xi indicates the symbol location and Yi indicates the corresponding bit pattern associated with that symbol location, be the sequence to be sequentially flipped. Cumulative sets σi, i=0, 1, 2, . . . , τ, are defined such that

σi={(X1, Y1), (X2, Y2), . . . , (Xi, Yi)}.   (8)

For example, the first branch (202) of test error patterns can be generated by sequentially flipping as described. The second and third branches (204 and 206) are generated slightly differently. Let Sj(σi), j=0, 1, 2, . . . , 2t−1, be the variant syndrome associated with flipping pattern set σi.




  
    
      
        
          S
          j
          
            (
            
              σ
              i
            
            )
          
        
        =
        
          
            
              S
              j
            
            +
            
              
                ∑
                
                  l
                  =
                  1
                
                i
              
              ⁢
              
                
              
              ⁢
              
                
                  Y
                  l
                
                ⁢
                
                  X
                  l
                  
                    j
                    +
                    1
                  
                
              
            
          
          =
          
            
              S
              j
              
                (
                
                  σ
                  
                    i
                    -
                    1
                  
                
                )
              
            
            +
            
              
                Y
                i
              
              ⁢
              
                
                  X
                  i
                  
                    j
                    +
                    1
                  
                
                .
              
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




Let Λ(σ0)(x) and B(σ0)(x) denote the polynomials Λ(x) and B(x), respectively, obtained from the Berlekamp-Massey process using an initial syndrome.
Some optimization problems associated with incrementally generating error locator polynomials for the test error patterns are presented below. Discussion of the optimization problems follows.
A[σi]: Determine a minimum-length LFSR Λ(σi)(x), subject to (i) Λ0(σi)≠0 and Λ(σi)(x) generates the sequence S0, S1, S2, . . . , S2t−1; (ii) Λ(σi)(x) contains roots X1−1, X2−1, . . . , Xi−1; and (iii) {circumflex over (Ω)}(σi)(x)(σi)(x)Λ(σi)(x) (mod x2t) contains roots X1−1, X2−1, . . . , Xi−1.
B[σi]: Determine a minimum-length LFSR B(σi)(x), subject to (i) B(σi)(x) generates the sequence S0, S1, S2, . . . , S2t−2 but not S0, S1, S2, . . . , S2t−1; (ii) B(σi)(x) contains roots X1−1, X2−1, . . . , Xi−1; and (iii) {circumflex over (Θ)}(σi)(x)S(σi)(x)B(σi)(x) (mod x2t) contains roots X1−1, X2−1, . . . , Xi−1.
Note that {circumflex over (Ω)} and {circumflex over (Θ)} are variants of Ω and Θ, respectively. The second criterion, (ii), for A[σi] and B[σi] suggest cumulative or incremental interpolation and is discussed in further detail below. The following lemma discusses some properties associated with cumulative interpolation.
Lemma 2 Let Λ(σi)(x) and B(σi)(x) (i<t) be a solution of the optimization problems A[σi] and B[σi], respectively.
(i). Let Λ(σi+1)(x) be a minimum-length LFSR in the form of

Λ(σi+1)(x)=(1+xa(x))·Λ(σi)(x)+b(x)·xB(σi)(x)   (10)

with the polynomials a(x) and b(x) selected so that both Λ(σi+1)(x) and {circumflex over (Ω)}(σi+1)(x) contain the root Xi+1−1. Then, Λ(σi+1)(x) is a solution of the optimization problem A[σi+1].

(ii). Let B(σi+1)(x) be a minimum-length LFSR in the form of

B(σi+1)(x)=a′(x)·Λ(σi)(x)+(1+xb′(x))B(σi)(x)   (11)

with the polynomials a′(x) and b′(x) selected so that both B(σi+1)(x) and {circumflex over (Θ)}(σi+1)(x) contain the root Xi+1−1. Then, B(σi+1)(x) is a solution of the optimization problem B[σi+1].

Proof of (i) for Lemma 2. Λ(σi+1)(x) satisfies criterion (ii) of A[σi+1]. The conclusion that Λ(σi+1)(x) generates S0, S1, S2, . . . , S2t−1 results from the fact that both Λ(σi)(x) and xB(σi)(x) generate S0, S1, S2, . . . , S2t−1 (i.e., criterion (i) of A[σi+1] is satisfied). Criterion (iii) of A[σi+1] is demonstrated. It is noted that




  
    
      
        
          
            
              Ω
              ^
            
            
              (
              
                σ
                
                  i
                  +
                  1
                
              
              )
            
          
          ⁡
          
            (
            x
            )
          
        
        =
        
        ⁢
        
          
            
              S
              
                (
                
                  σ
                  
                    i
                    +
                    1
                  
                
                )
              
            
            ⁡
            
              (
              x
              )
            
          
          ⁢
          
            
              Λ
              
                (
                
                  σ
                  
                    i
                    +
                    1
                  
                
                )
              
            
            ⁡
            
              (
              x
              )
            
          
          ⁢
          
            (
            
              mod
              ⁢
              
                
              
              ⁢
              
                x
                
                  2
                  ⁢
                  t
                
              
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              
                
                  S
                  
                    (
                    
                      σ
                      i
                    
                    )
                  
                
                ⁡
                
                  (
                  x
                  )
                
              
              +
              
                
                  Y
                  
                    i
                    +
                    1
                  
                
                ⁢
                
                  X
                  
                    i
                    +
                    1
                  
                
                ⁢
                
                  
                    ∑
                    
                      j
                      =
                      0
                    
                    
                      
                        2
                        ⁢
                        t
                      
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      X
                      
                        i
                        +
                        1
                      
                      j
                    
                    ⁢
                    
                      x
                      j
                    
                  
                
              
            
            )
          
          ⁢
          
            
              Λ
              
                (
                
                  σ
                  
                    i
                    +
                    1
                  
                
                )
              
            
            ⁡
            
              (
              x
              )
            
          
          ⁢
          
            (
            
              mod
              ⁢
              
                
              
              ⁢
              
                x
                
                  2
                  ⁢
                  t
                
              
            
            )
          
        
      
    
  
  
    
      
        
          
            
              =
              
              ⁢
              
                
                  
                    
                      S
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ⁢
                  
                    
                      (
                      
                        1
                        +
                        
                          xa
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                      
                      )
                    
                    ·
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
                +
                
                  
                    b
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ·
                  
                    
                      xB
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                
              
            
            )
          
          ⁢
          
            (
            
              mod
              ⁢
              
                
              
              ⁢
              
                x
                
                  2
                  ⁢
                  t
                
              
            
            )
          
        
        +
      
    
  
  
    
      
        
        ⁢
        
          
            Y
            
              i
              +
              1
            
          
          ⁢
          
            X
            
              i
              +
              1
            
          
          ⁢
          
            
              1
              -
              
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    2
                    ⁢
                    t
                  
                
                ⁢
                
                  x
                  
                    2
                    ⁢
                    t
                  
                
              
            
            
              1
              -
              
                
                  X
                  
                    i
                    +
                    1
                  
                
                ⁢
                x
              
            
          
          ⁢
          
            
              Λ
              
                (
                
                  σ
                  
                    i
                    +
                    1
                  
                
                )
              
            
            ⁡
            
              (
              x
              )
            
          
          ⁢
          
            (
            
              mod
              ⁢
              
                
              
              ⁢
              
                x
                
                  2
                  ⁢
                  t
                
              
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
              (
              
                1
                +
                
                  xa
                  ⁡
                  
                    (
                    x
                    )
                  
                
              
              )
            
            ·
            
              
                
                  Ω
                  ^
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                x
                )
              
            
          
          +
          
            
              
                b
                ⁡
                
                  (
                  x
                  )
                
              
              ·
              x
            
            ⁢
            
              
                
                  Θ
                  ^
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                x
                )
              
            
          
          +
          
            
              Y
              
                i
                +
                1
              
            
            ⁢
            
              X
              
                i
                +
                1
              
            
            ⁢
            
              
                
                  Λ
                  
                    (
                    
                      σ
                      
                        i
                        +
                        1
                      
                    
                    )
                  
                
                ⁡
                
                  (
                  x
                  )
                
              
              
                1
                -
                
                  
                    X
                    
                      i
                      +
                      1
                    
                  
                  ⁢
                  x
                
              
            
          
        
      
    
  




where in the last equality, the first two terms are due to criterion (i) of A[σi] for Λ(σi)(x) and criterion (i) of B[σi] for B((σi)(x), so that the degrees of {circumflex over (Ω)}(σi)(x) and {circumflex over (Θ)}(σi)(x) are less than that of Λ(σi)(x) and B(σi)(x), respectively. The last term is due to the assumption that 1−Xi+1x is divisible by Λ(σi+1)(x). Thus, Λ(σi+1)(x) also contains the roots X1−1, X2−1, . . . , Xi−1 (i.e., it satisfies criterion (iii) of A[σi+1]).

The conclusion that B(σi+1)(x) generates S0, S1, S2, . . . , S2t−2 but not S0, S1, S2, . . . , S2t−1 results from the fact that B(σi)(x), a component of B(σi+1)(x), generates only S0, S1, S2, . . . , S2t−2. Proof of the remainder of Lemma 2 follows that of part (i).
The following lemma in turn discusses the properness of the proposed problem formulation.
Lemma 3 If (X1, Y1), (X2, Y2), . . . , (Xi, Yi) (i≦t) are true error patterns out of t+i symbol errors, then the true error locator polynomial is the unique solution (upon normalization) of the proposed optimization problem, A[σi].
Proof: Let {tilde over (X)}1, {tilde over (X)}2, . . . , {tilde over (X)}i be associated with the remaining erroneous locations in addition to X1, X2, . . . , Xi. Then the error locator polynomial can be expressed as




  
    
      Λ
      *
    
    ⁡
    
      (
      x
      )
    
  
  =
  
    
      ∏
      
        j
        =
        1
      
      i
    
    ⁢
    
      
    
    ⁢
    
      
        (
        
          1
          -
          
            
              X
              j
            
            ⁢
            x
          
        
        )
      
      ⁢
      
        
          ∏
          
            j
            =
            1
          
          t
        
        ⁢
        
          
        
        ⁢
        
          
            (
            
              1
              -
              
                
                  
                    X
                    ~
                  
                  j
                
                ⁢
                x
              
            
            )
          
          .
        
      
    
  




The genuine error locator polynomial Λ*(x) satisfies the criteria (i) and (ii) of A[σi]. It is observed that





  
    
      
        
          
            
              Ω
              ^
            
            *
          
          ⁡
          
            (
            x
            )
          
        
        =
        
        ⁢
        
          
            
              Λ
              *
            
            ⁡
            
              (
              x
              )
            
          
          ⁢
          
            
              S
              
                (
                
                  σ
                  i
                
                )
              
            
            ⁡
            
              (
              x
              )
            
          
          ⁢
          
            (
            
              mod
              ⁢
              
                
              
              ⁢
              
                x
                
                  2
                  ⁢
                  t
                
              
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∏
            
              j
              =
              1
            
            i
          
          ⁢
          
            
          
          ⁢
          
            
              (
              
                1
                -
                
                  
                    X
                    j
                  
                  ⁢
                  x
                
              
              )
            
            ⁢
            
              (
              
                
                  ∏
                  
                    j
                    =
                    1
                  
                  t
                
                ⁢
                
                  
                
                ⁢
                
                  
                    (
                    
                      1
                      -
                      
                        
                          
                            X
                            ~
                          
                          j
                        
                        ⁢
                        x
                      
                    
                    )
                  
                  ⁢
                  
                    
                      S
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    (
                    
                      mod
                      ⁢
                      
                        
                      
                      ⁢
                      
                        x
                        
                          2
                          ⁢
                          t
                        
                      
                    
                    )
                  
                
              
              )
            
          
        
      
    
  




Note in the last equality, the second term is of degree t−1. Therefore {circumflex over (Ω)}*(x) contains the roots X1−1, X2−1, . . . , Xi−1 (i.e., Λ*(x) also satisfies criterion (iii) of A[σi]).
It is next shown by contradiction that Λ*(x) is the unique solution of the optimization problem A[σi]. Otherwise, let the polynomial Λ(σi)(x) be a solution of the optimization problem A[σi]. By assumption, Λ(σi)(x) has a length less than or equal to t+i and Λ(σi)(x)≠Λ*(x). According to criterion (i) of A[σi], Ω(x)=Λ(σi)(x)S(x) (mod x2t) has a degree less than t+i. It is observed that




  
    
      
        
          
            
              
                Ω
                ⁡
                
                  (
                  x
                  )
                
              
              =
              
              ⁢
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  S
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                
                  (
                  
                    mod
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      
                        2
                        ⁢
                        t
                      
                    
                  
                  )
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  (
                  
                    
                      
                        S
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    +
                    
                      
                        ∑
                        
                          l
                          =
                          1
                        
                        i
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          ∑
                          
                            j
                            =
                            0
                          
                          
                            
                              2
                              ⁢
                              t
                            
                            -
                            1
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            Y
                            l
                          
                          ⁢
                          
                            X
                            l
                            
                              j
                              +
                              1
                            
                          
                          ⁢
                          
                            x
                            j
                          
                        
                      
                    
                  
                  )
                
                ⁢
                
                  (
                  
                    mod
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      
                        2
                        ⁢
                        t
                      
                    
                  
                  )
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  (
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ⁢
                    
                      
                        S
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      (
                      
                        mod
                        ⁢
                        
                          
                        
                        ⁢
                        
                          x
                          
                            2
                            ⁢
                            t
                          
                        
                      
                      )
                    
                  
                  )
                
                +
                
                  (
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ⁢
                    
                      
                        ∑
                        
                          l
                          =
                          1
                        
                        i
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          Y
                          l
                        
                        ⁢
                        
                          X
                          l
                        
                        ⁢
                        
                          
                            1
                            -
                            
                              
                                X
                                l
                                
                                  2
                                  ⁢
                                  t
                                
                              
                              ⁢
                              
                                x
                                
                                  2
                                  ⁢
                                  t
                                
                              
                            
                          
                          
                            1
                            -
                            
                              
                                X
                                l
                              
                              ⁢
                              x
                            
                          
                        
                        ⁢
                        
                          (
                          
                            mod
                            ⁢
                            
                              
                            
                            ⁢
                            
                              x
                              
                                2
                                ⁢
                                t
                              
                            
                          
                          )
                        
                      
                    
                  
                  )
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  
                    
                      Ω
                      ^
                    
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                +
                
                  
                    ∑
                    
                      l
                      =
                      1
                    
                    i
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      Y
                      l
                    
                    ⁢
                    
                      X
                      l
                    
                    ⁢
                    
                      
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                        
                          1
                          -
                          
                            
                              X
                              l
                            
                            ⁢
                            x
                          
                        
                      
                      .
                      
                        
                          
                            
                              (
                              13
                              )
                            
                          
                        
                        
                          
                            
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        12
        )
      
    
  




In the last equality, the second term has a degree less than that of Λ(σi)(x). Thus, the degree of the first term of {circumflex over (Ω)}(x) can not exceed that of Λ(σi)(x).

A new polynomial




  
    
      
        Λ
        ~
      
      
        (
        
          σ
          i
        
        )
      
    
    ⁢
    
      (
      x
      )
    
  
  ⁢
  
    =
    Δ
  
  ⁢
  
    
      
        Λ
        
          (
          
            σ
            i
          
          )
        
      
      ⁡
      
        (
        x
        )
      
    
    
      
        ∏
        
          l
          =
          1
        
        i
      
      ⁢
      
        (
        
          1
          -
          
            
              X
              l
            
            ⁢
            x
          
        
        )
      
    
  




is defined. By the definition of {circumflex over (Ω)}(σi)(x)

Λ(σi)(x)S(σi)(x)={circumflex over (Ω)}(σi)(x)+x2tƒ(x).

where ƒ(x) is a polynomial. Since both Λ(σi)(x) and {circumflex over (Ω)}(σi)(x) divide the term Πj=1i(1−Xjx), ƒ(x) divides Πj=1i(1−Xjx) as well. Thus,





  
    
      
        
          Λ
          ~
        
        
          (
          
            σ
            i
          
          )
        
      
      ⁡
      
        (
        x
        )
      
    
    ⁢
    
      
        S
        
          (
          
            σ
            i
          
          )
        
      
      ⁡
      
        (
        x
        )
      
    
  
  =
  
    
      
        
          
            Ω
            ^
          
          
            (
            
              σ
              i
            
            )
          
        
        ⁡
        
          (
          x
          )
        
      
      
        
          ∏
          
            j
            =
            1
          
          i
        
        ⁢
        
          
        
        ⁢
        
          (
          
            1
            -
            
              
                X
                j
              
              ⁢
              x
            
          
          )
        
      
    
    +
    
      
        x
        
          2
          ⁢
          t
        
      
      ⁢
      
        
          
            f
            ⁡
            
              (
              x
              )
            
          
          
            
              ∏
              
                j
                =
                1
              
              i
            
            ⁢
            
              
            
            ⁢
            
              (
              
                1
                -
                
                  
                    X
                    j
                  
                  ⁢
                  x
                
              
              )
            
          
        
        .
      
    
  




Equivalently,




  
    
      
        
          Ω
          ^
        
        
          (
          
            σ
            i
          
          )
        
      
      ⁡
      
        (
        x
        )
      
    
    
      
        ∏
        
          j
          =
          1
        
        i
      
      ⁢
      
        
      
      ⁢
      
        (
        
          1
          -
          
            
              X
              j
            
            ⁢
            x
          
        
        )
      
    
  
  =
  
    
      
        
          Λ
          ~
        
        
          (
          
            σ
            i
          
          )
        
      
      ⁡
      
        (
        x
        )
      
    
    ⁢
    
      
        S
        
          (
          
            σ
            i
          
          )
        
      
      ⁡
      
        (
        x
        )
      
    
    ⁢
    
      
    
    ⁢
    
      
        (
        
          mod
          ⁢
          
            
          
          ⁢
          
            x
            
              2
              ⁢
              t
            
          
        
        )
      
      .
    
  




The above equality, in conjunction with the fact that the degree of {circumflex over (Ω)}(σi)(x) is less than that of Λ(σi)(x), indicates that {tilde over (Λ)}(σi)(x) generates the sequence S0(σi), S1(σi), . . . , S2t−1(σi). On the other hand, the polynomial {tilde over (Λ)}(σi)(x) has a degree of at most t; this contradicts with the fact there is unique minimum degree polynomial that generates S0(σi), S1(σi), . . . , S2t−1(σi), namely, Πj=1t(1−{tilde over (X)}jx). This concludes the lemma.
The computation can be simplified

{circumflex over (Ω)}(σ+1)(x)=(1+xa(x))Λ(σi)(x)S(σi+1)(x)+b(x)·xB(σi)(x)S(σi+1)(x) (mod x2t)   (14)

where a(x) and b(x) are unknown polynomials with the underlying condition that Λ(σi+1)(x)=(1+xa(x))·Λ(σi)(x)+b(x)·xB(σi)(x) has a degree less than 2t and contains the roots Xi+1−1. Note that neither Λ(σi)(x) nor B(σi)(x) generates S(σi+1)(x). Thus, the following inequality holds

{circumflex over (Ω)}(σi+1)(x)≠(1+xa(x))(Λ(σi)(x)S(σi+1)(x) mod x2t)+b(x)(xB(σi)(x)S(σi+1)(x) mod x2t)

It has been shown in equation 13 that Λ(σi+1)(x) generates S(σi+1)(x). Thus, all terms with degrees higher than that of Λ(σi+1)(x) can be safely ignored. To this end, the following is defined

[xl Ω(σi)](x)xlΛ(σi)(x)S(σi+1)(x) (mod x2t−1).   (15)

[xl Θ(σi)](x)xlB(σi)(x)S(σi+1)(x) (mod x2t−1).   (16)

Consequently,




  
    
      
        
          
            [
            
              
                x
                l
              
              ⁢
              
                
                  Ω
                  _
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
            
            ]
          
          ⁢
          
            (
            x
            )
          
        
        =
        
          
            
              x
              l
            
            ⁡
            
              (
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  
                    S
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                
                  (
                  
                    mod
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      
                        L
                        Λ
                      
                    
                  
                  )
                
              
              )
            
          
          +
          
            
              
                Λ
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
            ⁢
            
              Y
              
                i
                +
                1
              
            
            ⁢
            
              X
              
                i
                +
                1
              
            
            ⁢
            
              
                ∑
                
                  j
                  =
                  
                    
                      L
                      Λ
                    
                    +
                    l
                  
                
                
                  
                    2
                    ⁢
                    t
                  
                  -
                  2
                
              
              ⁢
              
                
              
              ⁢
              
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    j
                    -
                    l
                  
                
                ⁢
                
                  x
                  j
                
              
            
          
        
      
    
    
      
        (
        17
        )
      
    
  
  
    
      
        
          
            [
            
              
                x
                l
              
              ⁢
              
                
                  Θ
                  _
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
            
            ]
          
          ⁢
          
            (
            x
            )
          
        
        =
        
          
            
              x
              l
            
            ⁡
            
              (
              
                
                  
                    B
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  
                    S
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                
                  (
                  
                    mod
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      
                        L
                        B
                      
                    
                  
                  )
                
              
              )
            
          
          +
          
            
              
                B
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
            ⁢
            
              Y
              
                i
                +
                1
              
            
            ⁢
            
              X
              
                i
                +
                1
              
            
            ⁢
            
              
                ∑
                
                  j
                  =
                  
                    
                      L
                      B
                    
                    +
                    l
                  
                
                
                  
                    2
                    ⁢
                    t
                  
                  -
                  2
                
              
              ⁢
              
                
              
              ⁢
              
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    j
                    -
                    l
                  
                
                ⁢
                
                  x
                  j
                
              
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




where LΛ and LB denote the length of Λ(σi)(x) and B(σi)(x), respectively.

It is observed that enforcing the criteria {circumflex over (Ω)}(σi+1)(Xi+1−1)=0 and {circumflex over (Θ)}(σi+1)(Xi+1−1)=0 is primarily of concern and it is therefore not necessary to keep track of {circumflex over (Ω)}(σi)(x) and {circumflex over (Θ)}(σi)(x). This can be effectively achieved by the following equations.




  
    
      
        
          
            
              
                
                  
                    Ω
                    _
                  
                  ⁢
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    
                      ∑
                      
                        j
                        =
                        0
                      
                      
                        
                          L
                          Λ
                        
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        S
                        j
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁢
                      
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            j
                          
                        
                        ·
                        
                          
                            ∑
                            
                              l
                              =
                              0
                            
                            
                              
                                L
                                Λ
                              
                              -
                              1
                              -
                              j
                            
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              Λ
                              l
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁢
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                l
                              
                            
                          
                        
                      
                    
                  
                  +
                  
                    
                      δ
                      
                        (
                        
                          
                            L
                            Λ
                          
                          -
                          1
                        
                        )
                      
                    
                    ⁢
                    
                      Y
                      
                        i
                        +
                        1
                      
                    
                    ⁢
                    
                      X
                      
                        i
                        +
                        1
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
              ,
            
          
          
            
              
            
          
        
      
    
    
      
        (
        19
        )
      
    
  
  
    
      
        
          
            
              
                
                  
                    Θ
                    _
                  
                  ⁢
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    
                      ∑
                      
                        j
                        =
                        0
                      
                      
                        
                          L
                          B
                        
                        -
                        1
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        S
                        j
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁢
                      
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            j
                          
                        
                        ·
                        
                          
                            ∑
                            
                              l
                              =
                              0
                            
                            
                              
                                L
                                B
                              
                              -
                              1
                              -
                              j
                            
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              B
                              l
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁢
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                l
                              
                            
                          
                        
                      
                    
                  
                  +
                  
                    
                      δ
                      
                        (
                        
                          
                            L
                            B
                          
                          -
                          1
                        
                        )
                      
                    
                    ⁢
                    
                      Y
                      
                        i
                        +
                        1
                      
                    
                    ⁢
                    
                      X
                      
                        i
                        +
                        1
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
              ,
            
          
          
            
              
            
          
        
      
    
    
      
        (
        20
        )
      
    
  




where δl 1 if l is odd or 0 otherwise. Note that the second summation in equation 19 can be obtained intermediately during the evaluation of Λ(σi)(Xi+1−1), and that

[xl Ω(σi)](Xi+1−1)=Xi+1−1( Ω(σi)(Xi+1−1)+δlYi+1Xi+1Λ(σi)(Xi+1−1))   (21)

[xl Θ(σi)](Xi+1−1)=Xi+1−1( Θ(σi)(Xi+1−1)+δlYi+1B(σi)(Xi+1−1))   (22)

The above equation is valid for {circumflex over (Ω)}(σi) (but not {circumflex over (Θ)}(σi)) with some modifications. For the last iteration, the evaluation of {circumflex over (Θ)}(σi) is not necessary.
FIG. 3 is a flowchart illustrating an embodiment of a process for incrementally generating error locator polynomials. In the example shown, the process is an alternative to a straightforward Chase decoder and circumvents repeatedly performing a Berlekamp-Massey process to obtain error locator polynomials for each test error pattern when flipping bit patterns. At 300, initialization is performed using an initial dataword. In some embodiments, the initial dataword is obtained from a soft output Viterbi decoder and a full Berlekamp-Massey process is performed. It is decided at 302 whether the results are satisfactory. For example, an error locator polynomial generated at 300 may be satisfactory and thus it is not necessary to generate other error locator polynomials. At 304, error locator polynomials are incrementally generated for test error patterns and one is selected for use in subsequent processing. In some embodiments, all possible test error patterns are processed. In some embodiments, the process terminates when at least one of the error locator polynomials generated at 304 satisfies certain criteria.
FIG. 4 is a flowchart illustrating an embodiment of a process for initialization associated with incrementally generating error locator polynomials. In the example shown, initialization at 300 can be performed using the process illustrated. Alternatively, other techniques may be used.
At 400, a received dataword and a list of error events are obtained from a soft output Viterbi decoder. For example, the inputs r=[rn−1, rn−2, . . . , r1, r0] and (X1, Y1), (X2, Y2), . . . , (Xτ, Yτ) are obtained.
At 402, syndromes are calculated. For example, the equation




  
    
      S
      i
    
    =
    
      
        ∑
        
          j
          =
          0
        
        
          n
          -
          1
        
      
      ⁢
      
        
      
      ⁢
      
        
          r
          j
        
        ⁢
        
          α
          
            j
            ⁡
            
              (
              
                i
                +
                1
              
              )
            
          
        
      
    
  
  ,
  
    j
    =
    0
  
  ,
  1
  ,
  2
  ,
  ...
  ⁢
  
    
  
  ,
  
    
      2
      ⁢
      t
    
    -
    1
  




is used.

A Berlekamp-Massey process is performed to obtain an error locator polynomial, Λ(x) , and a scratch polynomial, B(x), at 404. Some implementations of the Berlekamp-Massey process require 2t cycles. Incrementally generating error locator polynomials for each test error pattern circumvents repetition of the Berlekamp-Massey process and reduces the amount of time it takes to generate error locator polynomials for all combinations of flipped test error patterns. In some embodiments, additional or alternative polynomials are generated, such as the scratch polynomial, B(x).
At 406, a Chien search and error correction is performed using the error locator polynomial, Λ(x), and the scratch polynomial, B(x). If the Chien search and error correction are successful then processing may conclude without incrementally generating error locator polynomials for flipped test error patterns. For example, if the data is read back almost perfectly from a storage medium and there is little or no error in the received data then the error correction performed by the initialization process is sufficient.
In some embodiments, data associated with the initialization process is stored. Referring to the example of FIG. 2, the error locator polynomial, scratch polynomial, and syndromes are saved and associated with initial dataword 200. This saved data is then used to initialize processing for branches 202, 204, and/or 206.)

Λ(σ0)(x)←Λ(x), B(σ0)(x)←B(x), S(σ0)(x)←S(x)

FIG. 5 is a flowchart illustrating an embodiment of a process for performing error correction using polynomials selected from an incrementally generated group. In the example shown, the process can be used to incrementally generate polynomials at 304. Referring to the example of FIG. 2, the process can be used to traverse branches 202, 204, and 206.
At 500, syndromes for a current test error pattern are updated. In some embodiments, the following equation is used:

Sj(σi+1)←Sj(σi)+Yi+1Xi+1j+1 j=0,1,2, . . . , t+τ−1.

If it is the beginning of a branch in a tree structure, saved syndromes associated with initial test pattern 200 is used. If the process is in the middle of a given branch, syndromes from the immediately prior test error pattern are used.

In some embodiments, not all syndromes are updated since the syndromes St+τ(σi), St+τ+1(σi), . . . , S2t−1(σi) are not used in the iterations.
Polynomials associated with previous test error pattern are evaluated at 502. In some embodiments, the following polynomials are evaluated:

Λ(σi)(Xi+1−1), B(σi)(Xi+1−1), Ω(σi)(Xi+1−1), Θ(σi)(Xi+1−1)

An error locator polynomial and a scratch polynomial are generated for the current test error pattern using the evaluated polynomials. In some embodiments, case statements are used to determine an appropriate LSFR to use and the case statements cover all possible cases. In some embodiments, the following case statements and associated LSFR are used. In the embodiment shown, a given polynomial for the current test error pattern is based on the immediately prior version of that polynomial.




  
    
      
        
          
            Case
            ⁢
            
              
            
            ⁢
            1
            ⁢
            
              :
            
            ⁢
            
              
            
            ⁢
            
              
                Λ
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          =
          
            
              0
              ⋀
              
                
                  
                    Ω
                    _
                  
                  
                    (
                    
                      σ
                      i
                    
                    )
                  
                
                ⁡
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
            
            =
            0
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                
              
            
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      (
                      
                        1
                        -
                        
                          
                            X
                            
                              i
                              +
                              1
                            
                            2
                          
                          ⁢
                          
                            x
                            2
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  ←
                  
                    
                      L
                      Λ
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      L
                      B
                    
                  
                  ←
                  
                    
                      L
                      B
                    
                    +
                    2
                  
                
              
            
          
        
      
    
    
      
        (
        23
        )
      
    
  
  
    
      
        
          
            Case
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              :
            
            ⁢
            
              
            
            ⁢
            
              
                B
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          =
          
            
              0
              ⋀
              
                
                  
                    Θ
                    _
                  
                  
                    (
                    
                      σ
                      i
                    
                    )
                  
                
                ⁡
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
            
            =
            0
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      (
                      
                        1
                        -
                        
                          
                            X
                            
                              i
                              +
                              1
                            
                            2
                          
                          ⁢
                          
                            x
                            2
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  ←
                  
                    
                      L
                      Λ
                    
                    +
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        L
                        B
                      
                    
                  
                  ←
                  
                    L
                    B
                  
                
              
            
          
        
      
    
    
      
        (
        24
        )
      
    
  
  
    
      
        
          
            Case
            ⁢
            
              
            
            ⁢
            3
            ⁢
            
              :
            
            ⁢
            
              
            
            ⁢
            
              L
              Λ
            
          
          <
          
            
              L
              B
            
            ⋀
            
              
                Λ
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          ≠
          0
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      (
                      
                        1
                        -
                        
                          
                            X
                            
                              i
                              +
                              1
                            
                            2
                          
                          ⁢
                          
                            x
                            2
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    +
                    
                      ax
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                    +
                    
                      
                        bx
                        2
                      
                      ⁢
                      
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  ←
                  
                    
                      L
                      Λ
                    
                    +
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        L
                        B
                      
                    
                  
                  ←
                  
                    L
                    B
                  
                
              
            
          
        
      
    
    
      
        (
        25
        )
      
    
  




where a and b are suitable values to enforce B(σi)(Xi+1−1)=0 and {circumflex over (Θ)}(σi+1)(Xi+1−1)=0, such that





  
    
      
        {
        
          
            
              
                
                  
                    
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                      +
                      
                        
                          a
                          ⁡
                          
                            [
                            
                              x
                              ⁢
                              
                                
                              
                              ⁢
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                            
                            ]
                          
                        
                        ⁢
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                      +
                      
                        
                          b
                          ⁡
                          
                            [
                            
                              
                                x
                                2
                              
                              ⁢
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                            
                            ]
                          
                        
                        ⁢
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                    
                    =
                    0
                  
                
              
              
                
                  
                    
                      
                        
                          
                            Θ
                            _
                          
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                      +
                      
                        
                          a
                          ⁡
                          
                            [
                            
                              x
                              ⁢
                              
                                
                                  Ω
                                  _
                                
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                            
                            ]
                          
                        
                        ⁢
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                      +
                      
                        
                          b
                          ⁡
                          
                            [
                            
                              
                                x
                                2
                              
                              ⁢
                              
                                
                                  Ω
                                  _
                                
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                            
                            ]
                          
                        
                        ⁢
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                    
                    =
                    0
                  
                
              
            
            ⁢
            
              

            
            ⁢
            Case
            ⁢
            
              
            
            ⁢
            4
            ⁢
            
              :
            
            ⁢
            
              
            
            ⁢
            
              L
              Λ
            
          
          >
          
            
              L
              B
            
            ⋀
            
              
                B
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          ≠
          
            0
            ⁢
            
              

            
            ⁢
            
              {
              
                
                  
                    
                      
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                
                                  i
                                  +
                                  1
                                
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                        ←
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          +
                          
                            
                              axB
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          +
                          
                            
                              bx
                              2
                            
                            ⁢
                            
                              
                                B
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                  
                  
                    
                      
                        
                          
                            B
                            
                              (
                              
                                σ
                                
                                  i
                                  +
                                  1
                                
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                        ←
                        
                          
                            (
                            
                              1
                              -
                              
                                
                                  X
                                  
                                    i
                                    +
                                    1
                                  
                                  2
                                
                                ⁢
                                
                                  x
                                  2
                                
                              
                            
                            )
                          
                          ⁢
                          
                            
                              B
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                        
                      
                    
                  
                  
                    
                      
                        
                          L
                          Λ
                        
                        ←
                        
                          
                            L
                            Λ
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            L
                            B
                          
                        
                        ←
                        
                          
                            L
                            B
                          
                          +
                          2
                        
                      
                    
                  
                
                ⁢
                
                  
                    
                      
                        (
                        26
                        )
                      
                    
                  
                  
                    
                      
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        
      
    
  




where a and b are suitable values to enforce Λ(σi+1)(Xi+1−1)=0 and {circumflex over (Ω)}(σi+1)(Xi+1−1)=0, such that





  {
  
    
      
        
          
            
              
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      a
                      ⁡
                      
                        [
                        
                          xB
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      b
                      ⁡
                      
                        [
                        
                          
                            x
                            2
                          
                          ⁢
                          
                            B
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                =
                0
              
            
          
          
            
              
                
                  
                    
                      
                        Ω
                        _
                      
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      a
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                              Θ
                              _
                            
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      b
                      ⁡
                      
                        [
                        
                          
                            x
                            2
                          
                          ⁢
                          
                            
                              Θ
                              _
                            
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                =
                0
              
            
          
        
        ⁢
        
          

        
        ⁢
        Case
        ⁢
        
          
        
        ⁢
        5
        ⁢
        
          :
        
        ⁢
        
          
        
        ⁢
        
          L
          Λ
        
      
      <
      
        
          L
          B
        
        ⋀
        
          
            Λ
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
      
    
    =
    
      
        0
        ⋀
        
          
            
              Ω
              _
            
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
      
      ≠
      
        0
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ←
                    
                      
                        (
                        
                          1
                          -
                          
                            
                              X
                              
                                i
                                +
                                1
                              
                            
                            ⁢
                            x
                          
                        
                        )
                      
                      ⁢
                      
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                  
                
              
              
                
                  
                    
                      
                        B
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ←
                    
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      +
                      
                        ax
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                      
                      +
                      
                        
                          bxB
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                  
                
              
              
                
                  
                    
                      L
                      Λ
                    
                    ←
                    
                      
                        L
                        Λ
                      
                      +
                      
                        1
                        ⁢
                        
                          
                        
                        ⁢
                        
                          L
                          B
                        
                      
                    
                    ←
                    
                      
                        L
                        B
                      
                      +
                      1
                    
                  
                
              
            
            ⁢
            
              
                
                  
                    (
                    27
                    )
                  
                
              
              
                
                  
                    
                  
                
              
            
          
        
      
    
  




where a and b are suitable values to enforce B(σi+1)(Xi+1−1)=0 and {circumflex over (Θ)}(σi+1)(Xi+1−1)=0, such that





  {
  
    
      
        
          
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      a
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      b
                      ⁡
                      
                        [
                        
                          xB
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                =
                0
              
            
          
          
            
              
                
                  
                    
                      
                        Θ
                        _
                      
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      a
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                              Ω
                              _
                            
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      b
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                              Θ
                              _
                            
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                =
                0
              
            
          
        
        ⁢
        
          

        
        ⁢
        Case
        ⁢
        
          
        
        ⁢
        6
        ⁢
        
          :
        
        ⁢
        
          
        
        ⁢
        
          L
          Λ
        
      
      <
      
        
          L
          B
        
        ⋀
        
          
            B
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
      
    
    =
    
      
        0
        ⋀
        
          
            
              Θ
              _
            
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
      
      ≠
      
        0
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ←
                    
                      
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      +
                      
                        
                          axB
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      +
                      
                        bx
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                      
                    
                  
                
              
              
                
                  
                    
                      
                        B
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ←
                    
                      
                        (
                        
                          1
                          -
                          
                            
                              X
                              
                                i
                                +
                                1
                              
                            
                            ⁢
                            x
                          
                        
                        )
                      
                      ⁢
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                  
                
              
              
                
                  
                    
                      L
                      Λ
                    
                    ←
                    
                      
                        L
                        Λ
                      
                      +
                      
                        1
                        ⁢
                        
                          
                        
                        ⁢
                        
                          L
                          B
                        
                      
                    
                    ←
                    
                      
                        L
                        B
                      
                      +
                      1
                    
                  
                
              
            
            ⁢
            
              (
              28
              )
            
          
        
      
    
  




where a and b are suitable values to enforce Λ(σi+1)(Xi+1−1)=0 and {circumflex over (Ω)}(σi+1)(Xi+1−1)=0, such that





  {
  
    
      
        
          
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  
                    a
                    ⁡
                    
                      [
                      
                        x
                        ⁢
                        
                          
                        
                        ⁢
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                      
                      ]
                    
                  
                  ⁢
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  
                    b
                    ⁡
                    
                      [
                      
                        x
                        ⁢
                        
                          
                        
                        ⁢
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                      
                      ]
                    
                  
                  ⁢
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
              
              =
              0
            
          
        
        
          
            
              
                
                  
                    
                      Ω
                      _
                    
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  
                    a
                    ⁡
                    
                      [
                      
                        x
                        ⁢
                        
                          
                            Θ
                            _
                          
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                      
                      ]
                    
                  
                  ⁢
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  
                    b
                    ⁡
                    
                      [
                      
                        x
                        ⁢
                        
                          
                            Ω
                            _
                          
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                      
                      ]
                    
                  
                  ⁢
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
              
              =
              0
            
          
        
      
      ⁢
      
        

      
      ⁢
      Case
      ⁢
      
        
      
      ⁢
      7
      ⁢
      
        :
      
      ⁢
      
        
      
      ⁢
      
        L
        Λ
      
    
    =
    
      
        
          
            L
            B
          
          ⋀
          
            
              B
              
                (
                
                  σ
                  i
                
                )
              
            
            ⁡
            
              (
              
                X
                
                  i
                  +
                  1
                
                
                  -
                  1
                
              
              )
            
          
        
        ⁢
        
          
            
              Ω
              _
            
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
      
      ≠
      
        
          
            Λ
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
        ⁢
        
          
            
              Θ
              _
            
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ←
                    
                      
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      +
                      
                        
                          axB
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      +
                      
                        bx
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                      
                    
                  
                
              
              
                
                  
                    
                      
                        B
                        
                          (
                          
                            σ
                            
                              i
                              +
                              1
                            
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ←
                    
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      +
                      
                        
                          a
                          ′
                        
                        ⁢
                        x
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                      
                      +
                      
                        
                          b
                          ′
                        
                        ⁢
                        
                          
                            xB
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            x
                            )
                          
                        
                      
                    
                  
                
              
              
                
                  
                    
                      L
                      Λ
                    
                    ←
                    
                      
                        L
                        Λ
                      
                      +
                      
                        1
                        ⁢
                        
                          
                        
                        ⁢
                        
                          L
                          B
                        
                      
                    
                    ←
                    
                      
                        L
                        B
                      
                      +
                      1
                    
                  
                
              
            
            ⁢
            
              
                
                  
                    (
                    29
                    )
                  
                
              
              
                
                  
                    
                  
                
              
            
          
        
      
    
  




where a and b are suitable values to enforce Λ(σi+1)(Xi+1−1)=0 and {circumflex over (Ω)}(σi+1)(Xi+1−1)=0, such that





  {
  
    
      
        
          
            
              
                Λ
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
            +
            
              
                a
                ⁡
                
                  [
                  
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                  
                  ]
                
              
              ⁢
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
            +
            
              
                b
                ⁡
                
                  [
                  
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                  
                  ]
                
              
              ⁢
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          =
          0
        
      
    
    
      
        
          
            
              
                
                  Ω
                  _
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
            +
            
              
                a
                ⁡
                
                  [
                  
                    x
                    ⁢
                    
                      
                        Θ
                        _
                      
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                  
                  ]
                
              
              ⁢
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
            +
            
              
                b
                ⁡
                
                  [
                  
                    x
                    ⁢
                    
                      
                        Ω
                        _
                      
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                  
                  ]
                
              
              ⁢
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          =
          0
        
      
    
  




and a′ and b′ are suitable values to enforce B(σi+1)(Xi+1−1)=0 and {circumflex over (Θ)}(σi+1)(Xi+1−1)=0, such that





  {
  
    
      
        
          
            
              
                
                  B
                  
                    (
                    
                      σ
                      i
                    
                    )
                  
                
                ⁡
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
              +
              
                
                  
                    a
                    ′
                  
                  ⁡
                  
                    [
                    
                      x
                      ⁢
                      
                        
                      
                      ⁢
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                    
                    ]
                  
                
                ⁢
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
              +
              
                
                  
                    b
                    ′
                  
                  ⁡
                  
                    [
                    
                      xB
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ]
                  
                
                ⁢
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
            
            =
            0
          
        
      
      
        
          
            
              
                
                  
                    Θ
                    _
                  
                  
                    (
                    
                      σ
                      i
                    
                    )
                  
                
                ⁡
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
              +
              
                
                  
                    a
                    ′
                  
                  ⁡
                  
                    [
                    
                      x
                      ⁢
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                    
                    ]
                  
                
                ⁢
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
              +
              
                
                  
                    b
                    ′
                  
                  ⁡
                  
                    [
                    
                      x
                      ⁢
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                    
                    ]
                  
                
                ⁢
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
            
            =
            0
          
        
      
    
    ⁢
    
      

    
    ⁢
    Case
    ⁢
    
      
    
    ⁢
    8
    ⁢
    
      :
    
    ⁢
    
      
        
          
            
              L
              Λ
            
            =
            
            ⁢
            
              
                
                  L
                  B
                
                ⋀
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
              
              ≠
              
                
                  0
                  ⋀
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                ⁢
                
                  
                    
                      Ω
                      _
                    
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
              
            
          
        
      
      
        
          
            =
            
            ⁢
            
              
                
                  Λ
                  
                    (
                    
                      σ
                      i
                    
                    )
                  
                
                ⁡
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
              ⁢
              
                
                  
                    Θ
                    _
                  
                  
                    (
                    
                      σ
                      i
                    
                    )
                  
                
                ⁡
                
                  (
                  
                    X
                    
                      i
                      +
                      1
                    
                    
                      -
                      1
                    
                  
                  )
                
              
            
          
        
      
    
    ⁢
    
      

    
    ⁢
    
      {
      
        
          
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    (
                    
                      1
                      -
                      
                        
                          X
                          
                            i
                            +
                            1
                          
                          2
                        
                        ⁢
                        
                          x
                          2
                        
                      
                    
                    )
                  
                  ⁢
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                
              
            
          
          
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                    ·
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                    ·
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  L
                  Λ
                
                ←
                
                  
                    L
                    Λ
                  
                  +
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      L
                      B
                    
                  
                
                ←
                
                  L
                  B
                
              
            
          
        
        ⁢
        
          
            
              
                (
                30
                )
              
            
          
          
            
              
                
              
            
          
        
      
    
  




At 506, it is determined whether to save data. For example, the error locator and scratch polynomial generated at 504 are compared to saved polynomials. A metric, such as a minimum distance, can be used in a comparison. In some embodiments, if this is the first iteration (e.g., test pattern 208) then the polynomials generated at 504 are compared to polynomials generating during an initialization process (e.g., associated with initial test pattern 200). If it is decided to save, at 508 the error locator polynomial and scratch polynomial for this iteration are saved. The previously saved polynomials are discarded.
After saving at 508 or if the decision at 506 is to not save, at 510 it is decided whether generation of polynomials is done. In some embodiments, generation concludes when all possible flipped test patterns are processed. For example, when all of branches 1-3 (202-206, respectively) are processed generation concludes. In some embodiments, it is not necessary to process all possible test patterns. For example, the saved polynomials may be the minimal distance and further processing to generate additional polynomials is not necessary. If generation of polynomials is not done, at 500 the syndromes are updated. Otherwise, at 512 a Chien search and error correction is performed using the saved error locator polynomial and scratch polynomial.
In some embodiments, a particular case dominates the rest of the cases. In one example, case 7 occurs more frequently compared to the rest of the cases. In some embodiments, an implementation is optimized or otherwise improved to take advantage of a particular case that occurs more frequently. The particular optimization or improvement can depend upon the statistical distribution associated with the case statements, the particular implementation of a decoder, etc.
In some embodiments, polynomials are incrementally generated in a parallel manner. Two or more test patterns may be processed simultaneously to further reduce the amount of time to generate polynomials for multiple test error patterns. Trade-offs associated with processing speed, size/cost, and/or design complexity of a decoder with parallel processing are evaluated to select an appropriate number of test error patterns to process in parallel.
In various embodiments different techniques are used in addition to or as an alternative to the example described. In some embodiments, case statements are not used. In some embodiments, different linear feedback shift registers and/or different associated conditions are used to incrementally generate polynomials. In some embodiments, a different set of polynomials are compared, generated, and/or saved. For example, in some embodiments less than four polynomials are evaluated at 502.
The following lemmas discuss properties associated with the above embodiment for initialization and incremental generation of error locator polynomials.
Lemma 4 After completion of the example process, the following occurs at the end of the i-th iteration

LΛ+LB=2(t+i).   (31)

Lemma 5 The example process precisely generates the solution for the proposed optimization problem.
Proof: The proof is by induction. Assume that Λ(σi)(x) and B(σi)(x) optimize the proposed problem A[σi] and B[σi], respectively, for the error pattern set σi.
In Case 1, Λ(σi)(x) suffices to accommodate criteria (i), (ii) and (iii) of A[σi] and thus it is the optimal solution. As for B, incorporating Λ is not useful in achieving criteria (ii) and (iii) of B[σi]. It can be verified that the described LFSR satisfies criteria (ii) and (iii) for B[σi] while minimizing the degree (recall that Λ(σi)(x) and B(σi)(x) both cannot divide (1−Xi+1x) as discussed in Lemma 1). Case 2 is analogous to Case 1.
In Case 3, it is noted that LxB>LLΛ+2. Therefore, incorporating xB(σi)(x) into Λ(σi+1)(x) would lead to a degree of at least LΛ+3. Thus, the given form of Λ(σi+1)(x) is the optimal solution. On the other hand, the given form of B(σi+1)(x) does not increase the degree while satisfying all three constraints. Case 4 is analogous to Case 3.
In Case 5, the given form of Λ(σi+1)(x) (which has a lower degree than the one given in Case 3) satisfies all three constraints while securing the minimum degree. On the other hand, the form of B(σi+1)(x) given in Case 3 is unable to meet all three constraints. Thus the given form achieves the minimum degree while meeting all three constraints. Case 6 follows the same arguments as Case 5.
In Case 7, it is impossible to meet the three constraints without increasing the degree of Λ(x) or B(x) while the given form increases the degree by one and satisfies all constraints.
In Case 8, the given form of B(σi+1)(x) meets all three constraints without increasing the degree. However, even increasing the degree LΛ by 1 will not satisfy the three constraints, thus the proposed form minimizes the degree. Note that Λ(σi+1)(x) cannot take the form of B(σi+1)(x) as constraint (i) of A[σi] is not satisfied.
Cases 2, 3 and 5 cover the branch LΛ<LB; Cases 1, 4 and 6 cover the branch LΛ>LB: Cases 1, 7 and 8 cover the branch LΛ=LB. Thus, the above 8 cases cover all possibilities (recall that B and Λ must not share a same root to be interpolated as discussed in Lemma 1 (iii)). Occasionally, some of the cases are overlapping but the solution is congruent when an overlapping condition occurs.
Lemmas 3 and 5 assert that incremental generation of polynomials is a “one-pass” (when implemented in parallel) alternative to straightforward Chase decoding. Consider a given sequential flipping of error patterns (X1, Y1), (X2, Y2), . . . , (Xτ, Yτ) for a received word r. If after flipping the pattern set σi, the modified word is within distance t (where t is the error-correction capability) from a codeword, then Λ(σi)(x) obtained by the described incremental generation process is exactly the error locator polynomial associated with this codeword.
In some embodiments, with an error locator polynomial obtained, Forney's formula is used to determine the corresponding error magnitudes. From a computational point of view, there is a complexity of O(nt) to determine all error locations for a given error locator polynomial. In some embodiments, this is circumvented by translating operations to vector operations, where the vectors Λ, B, {circumflex over (Ω)}, and {circumflex over (Θ)} are the evaluation vectors of the corresponding polynomials at points αi, i=0, 1, 2, . . . , n−1. If vector operations are used, all four polynomials are tracked rather than just Λ and B as described in the example of FIG. 5. The example of FIG. 5 is appropriately modified. Multiplication of a polynomial with x is translated to component-wise multiplication of an evaluation vector with the vector [α0, α1, α2, . . . , αn−1]. Every vector operation has a complexity of O(n) instead of a complexity O(t) associated with the example of FIG. 5. The complexity of one iteration is reduced from a complexity of O(nt) to O(n) .
Thus, one iteration of the incremental generation technique (not using vector operations) has a computational complexity of O(t). In some embodiments, this is performed in “one-pass” using parallel operations. By vectorizing the polynomials Λ, B, {circumflex over (Ω)}, and {circumflex over (Θ)} at points αi, i=0, 1, 2, . . . , n−1, the complete iteration (including polynomial updating and error locating) has a complexity of O(n) . In some embodiments, this is performed in “one-pass” using parallel operations.
Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.

## Claims

1. A method for generating a polynomial, including:
obtaining, at a processor, a first error locator polynomial, associated with locating errors in encoded data;
incrementally generating a second error locator polynomial using the processor, including by:
obtaining a test error pattern; and
flipping those bits in the first error locator polynomial that correspond to the test error pattern to obtain the second error locator polynomial; and

performing error correction decoding on encoded data using the second error locator polynomial.

2. A method as recited in claim 1, wherein incrementally generating excludes performing a Berlekamp-Massey process.

3. A method as recited in claim 1, further including performing a Berlekamp-Massey process to obtain an initial error locator polynomial.

4. A method as recited in claim 1, wherein obtaining includes incrementally generating the first error locator polynomial.

5. A method as recited in claim 1, wherein the test error pattern is associated with a tree structure.

6. A method as recited in claim 1, wherein the encoded data is associated with storage.

7. A method as recited in claim 1, further including incrementally generating a second scratch polynomial, associated with the test error pattern, based at least in part on a first scratch polynomial.

8. A method as recited in claim 1, wherein incrementally generating a second error locator polynomial is further based at least in part on a first scratch polynomial.

9. A method as recited in claim 1, further including evaluating the first error locator polynomial, wherein incrementally generating takes into consideration the evaluation of the first error locator polynomial.

10. A method as recited in claim 1, wherein incrementally generating includes using a plurality of cases.

11. A method as recited in claim 1, wherein incrementally generating includes using a plurality of cases and a probability associated with one or more of the plurality of cases is considered.

12. A method as recited in claim 1, further including determining whether to overwrite a saved error locator polynomial with the second error locator polynomial.

13. A method as recited in claim 1, further including determining at least one error location using a saved error locator polynomial.

14. A system for generating a polynomial, including:
an interface configured to obtain a first error locator polynomial, associated with locating errors in encoded data;
a processor configured to:
incrementally generate a second error locator polynomial, including by:
obtaining a test error pattern; and
flipping those bits in the first error locator polynomial that correspond to the test error pattern to obtain the second error locator polynomial; and

perform error correction decoding on encoded data using the second error locator polynomial.

15. A system as recited in claim 14, wherein the test error pattern is associated with a tree structure.

16. A system as recited in claim 14, wherein the processor is further configured to evaluate the first error locator polynomial, and the processor is configured to incrementally generate the second error locator polynomial by taking into consideration the evaluation of the first error locator polynomial.

17. A system as recited in claim 14, wherein the processor is further configured to determine at least one error location using a saved error locator polynomial.

18. A computer program product for generating a polynomial, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:
obtaining a first error locator polynomial, associated with locating errors in encoded data;
incrementally generating a second error locator polynomial, including by:
obtaining a test error pattern; and
flipping those bits in the first error locator polynomial that correspond to the test error pattern to obtain the second error locator polynomial; and

performing error correction decoding on encoded data using the second error locator polynomial.

19. A computer program product as recited in claim 18, wherein the test error pattern is associated with a tree structure.

20. A computer program product as recited in claim 18, the computer program product further comprising computer instructions for evaluating the first error locator polynomial, wherein incrementally generating takes into consideration the evaluation of the first error locator polynomial.

21. A computer program product as recited in claim 18, the computer program product further comprising computer instructions for determining at least one error location using a saved error locator polynomial.

22. A method as recited in claim 1, wherein incrementally generating a second error locator polynomial (Λ(x)) further includes using one or more of the following cases:




  
    
      
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                1
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  =
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            L
                            Λ
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                2
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  =
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                3
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                >
                
                  
                    L
                    B
                  
                  ⋀
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                ≠
                0
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                4
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                >
                
                  
                    L
                    B
                  
                  ⋀
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                ≠
                0
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                bx
                                2
                              
                              ⁢
                              
                                
                                  B
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            L
                            Λ
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                5
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  <
                  
                    
                      L
                      B
                    
                    ⋀
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                  
                                  ⁢
                                  x
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                6
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  >
                  
                    
                      L
                      B
                    
                    ⋀
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              bx
                              ⁢
                              
                                
                              
                              ⁢
                              
                                
                                  Λ
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                7
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                =
                
                  
                    
                      
                        L
                        B
                      
                      ⋀
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                    
                    ⁢
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                    ⁢
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              bx
                              ⁢
                              
                                
                              
                              ⁢
                              
                                
                                  Λ
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                  
                    
                  
                  ⁢
                  or
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                8
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    
                      
                        L
                        Λ
                      
                      =
                      
                      ⁢
                      
                        
                          
                            L
                            B
                          
                          ⋀
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              
                                X
                                
                                  i
                                  +
                                  1
                                
                                
                                  -
                                  1
                                
                              
                              )
                            
                          
                        
                        ≠
                        
                          
                            0
                            ⋀
                            
                              
                                B
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                
                                  X
                                  
                                    i
                                    +
                                    1
                                  
                                  
                                    -
                                    1
                                  
                                
                                )
                              
                            
                          
                          ⁢
                          
                            
                              
                                Ω
                                _
                              
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              
                                X
                                
                                  i
                                  +
                                  1
                                
                                
                                  -
                                  1
                                
                              
                              )
                            
                          
                        
                      
                    
                  
                
                
                  
                    
                      =
                      
                      ⁢
                      
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                1
                              
                            
                            )
                          
                        
                        ⁢
                        
                          
                            
                              Θ
                              _
                            
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                1
                              
                            
                            )
                          
                        
                      
                    
                  
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  .

23. A system as recited in claim 14, wherein the processor is configured to incrementally generate a second error locator polynomial (Λ(x)) by further using one or more of the following cases:




  
    
      
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                1
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  =
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            L
                            Λ
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                2
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  =
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                3
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                >
                
                  
                    L
                    B
                  
                  ⋀
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                ≠
                0
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                4
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                >
                
                  
                    L
                    B
                  
                  ⋀
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                ≠
                0
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                bx
                                2
                              
                              ⁢
                              
                                
                                  B
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            L
                            Λ
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                5
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  <
                  
                    
                      L
                      B
                    
                    ⋀
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                  
                                  ⁢
                                  x
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                6
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  >
                  
                    
                      L
                      B
                    
                    ⋀
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              bx
                              ⁢
                              
                                
                              
                              ⁢
                              
                                
                                  Λ
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                7
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                =
                
                  
                    
                      
                        L
                        B
                      
                      ⋀
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                    
                    ⁢
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                    ⁢
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              bx
                              ⁢
                              
                                
                              
                              ⁢
                              
                                
                                  Λ
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                  
                    
                  
                  ⁢
                  or
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                8
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    
                      
                        L
                        Λ
                      
                      =
                      
                      ⁢
                      
                        
                          
                            L
                            B
                          
                          ⋀
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              
                                X
                                
                                  i
                                  +
                                  1
                                
                                
                                  -
                                  1
                                
                              
                              )
                            
                          
                        
                        ≠
                        
                          
                            0
                            ⋀
                            
                              
                                B
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                
                                  X
                                  
                                    i
                                    +
                                    1
                                  
                                  
                                    -
                                    1
                                  
                                
                                )
                              
                            
                          
                          ⁢
                          
                            
                              
                                Ω
                                _
                              
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              
                                X
                                
                                  i
                                  +
                                  1
                                
                                
                                  -
                                  1
                                
                              
                              )
                            
                          
                        
                      
                    
                  
                
                
                  
                    
                      =
                      
                      ⁢
                      
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                1
                              
                            
                            )
                          
                        
                        ⁢
                        
                          
                            
                              Θ
                              _
                            
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                1
                              
                            
                            )
                          
                        
                      
                    
                  
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  .

24. A computer program product as recited in claim 18, wherein the computer instructions for incrementally generating a second error locator polynomial (Λ(x)) further include computer instructions for using one or more of the following cases:




  
    
      
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                1
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  =
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            L
                            Λ
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                2
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        i
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    
                      X
                      
                        i
                        +
                        1
                      
                      
                        -
                        1
                      
                    
                    )
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  =
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                3
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                >
                
                  
                    L
                    B
                  
                  ⋀
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                ≠
                0
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                4
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                >
                
                  
                    L
                    B
                  
                  ⋀
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                
                ≠
                0
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                bx
                                2
                              
                              ⁢
                              
                                
                                  B
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            L
                            Λ
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                5
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  <
                  
                    
                      L
                      B
                    
                    ⋀
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                  
                                  ⁢
                                  x
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                6
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  >
                  
                    
                      L
                      B
                    
                    ⋀
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
                =
                
                  
                    0
                    ⋀
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  0
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              bx
                              ⁢
                              
                                
                              
                              ⁢
                              
                                
                                  Λ
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                7
                ⁢
                
                  :
                
              
            
            
              
                
                  L
                  Λ
                
                =
                
                  
                    
                      
                        L
                        B
                      
                      ⋀
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          
                            X
                            
                              i
                              +
                              1
                            
                            
                              -
                              1
                            
                          
                          )
                        
                      
                    
                    ⁢
                    
                      
                        
                          Ω
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                  ≠
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                    ⁢
                    
                      
                        
                          Θ
                          _
                        
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        
                          X
                          
                            i
                            +
                            1
                          
                          
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              
                                axB
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                            +
                            
                              bx
                              ⁢
                              
                                
                              
                              ⁢
                              
                                
                                  Λ
                                  
                                    (
                                    
                                      σ
                                      i
                                    
                                    )
                                  
                                
                                ⁡
                                
                                  (
                                  x
                                  )
                                
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            1
                          
                        
                      
                    
                  
                  ;
                  
                    
                  
                  ⁢
                  or
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                Case
                ⁢
                
                  
                
                ⁢
                8
                ⁢
                
                  :
                
              
            
            
              
                
                  
                    
                      
                        L
                        Λ
                      
                      =
                      
                      ⁢
                      
                        
                          
                            L
                            B
                          
                          ⋀
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              
                                X
                                
                                  i
                                  +
                                  1
                                
                                
                                  -
                                  1
                                
                              
                              )
                            
                          
                        
                        ≠
                        
                          
                            0
                            ⋀
                            
                              
                                B
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                
                                  X
                                  
                                    i
                                    +
                                    1
                                  
                                  
                                    -
                                    1
                                  
                                
                                )
                              
                            
                          
                          ⁢
                          
                            
                              
                                Ω
                                _
                              
                              
                                (
                                
                                  σ
                                  i
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              
                                X
                                
                                  i
                                  +
                                  1
                                
                                
                                  -
                                  1
                                
                              
                              )
                            
                          
                        
                      
                    
                  
                
                
                  
                    
                      =
                      
                      ⁢
                      
                        
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                1
                              
                            
                            )
                          
                        
                        ⁢
                        
                          
                            
                              Θ
                              _
                            
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                          ⁡
                          
                            (
                            
                              X
                              
                                i
                                +
                                1
                              
                              
                                -
                                1
                              
                            
                            )
                          
                        
                      
                    
                  
                
              
            
          
          
            
              
                
              
            
            
              
                {
                
                  
                    
                      
                        
                          
                            
                              Λ
                              
                                (
                                
                                  σ
                                  
                                    i
                                    +
                                    1
                                  
                                
                                )
                              
                            
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                          ←
                          
                            
                              (
                              
                                1
                                -
                                
                                  
                                    X
                                    
                                      i
                                      +
                                      1
                                    
                                    2
                                  
                                  ⁢
                                  
                                    x
                                    2
                                  
                                
                              
                              )
                            
                            ⁢
                            
                              
                                Λ
                                
                                  (
                                  
                                    σ
                                    i
                                  
                                  )
                                
                              
                              ⁡
                              
                                (
                                x
                                )
                              
                            
                          
                        
                      
                    
                    
                      
                        
                          
                            L
                            Λ
                          
                          ←
                          
                            
                              L
                              Λ
                            
                            +
                            2
                          
                        
                      
                    
                  
                  .