# Patent

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

## Abstract

An error locator polynomial is incrementally generated by flipping a bit pattern Yi at a symbol Xi an initial dataword to obtain a first test error pattern. A bit pattern Yj at a symbol Xj within the first test error pattern is flipped to obtain a second test error pattern, wherein i≠j.

## Background
CROSS REFERENCE TO OTHER APPLICATIONS
This application is a continuation of U.S. patent application Ser. No. 11/433,645, entitled INCREMENTAL GENERATION OF POLYNOMIALS FOR DECODING REED-SOLOMON CODES filed May 11, 2006 now U.S. Pat. No. 7,793,195 which is incorporated herein by reference for all purposes.


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 X 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(σ0)≠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)S(σ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; 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
                        +
                        
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          
                            a
                            ⁡
                            
                              (
                              x
                              )
                            
                          
                        
                      
                      )
                    
                    ·
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
                +
                
                  
                    
                      b
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    ·
                    x
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      B
                      
                        (
                        
                          σ
                          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
                +
                
                  x
                  ⁢
                  
                    
                  
                  ⁢
                  
                    a
                    ⁡
                    
                      (
                      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
                            
                          
                        
                        )
                      
                    
                  
                
                )
              
            
          
        
      
    
    
      
        (
        12
        )
      
    
  
  
    
      
        
          
        
        ⁢
        
          =
          
          ⁢
          
            
              
                
                  Ω
                  ^
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                x
                )
              
            
            +
            
              
                ∑
                
                  l
                  =
                  1
                
                i
              
              ⁢
              
                
                  Y
                  l
                
                ⁢
                
                  X
                  l
                
                ⁢
                
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    
                      1
                      -
                      
                        
                          X
                          l
                        
                        ⁢
                        x
                      
                    
                  
                  .
                
              
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




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)+x2tf(x).

where f(x) is a polynomial. Since both Λ(σi)(x) and {circumflex over (Ω)}(σi)(x) divide the term Πj=1i(1−Xjx), f(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=1i(1−{tilde over (X)}jx). This concludes the lemma.
The computation can be simplified

{circumflex over (Ω)}(σi+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)(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
                  
                  
                    f
                    -
                    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.




  
    
      
        
          
            
              
                
                  Ω
                  _
                
                ⁢
                
                  
                
              
              
                (
                
                  σ
                  i
                
                )
              
            
            ⁢
            
              (
              
                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
        )
      
    
  
  
    
      
        
          
            
              
                Θ
                _
              
              ⁢
              
                
              
            
            
              (
              
                σ
                i
              
              )
            
          
          ⁢
          
            (
            
              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 is 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)+δ1Yi+1Xi+1B(σi)(Xi+1−1))  (22)

The above equation is valid for Ω(σ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+1j=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 Sy+τ(σ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+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
                      ⁡
                      
                        [
                        
                          
                            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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                            ⁡
                            
                              [
                              
                                x
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  B
                                  
                                    (
                                    
                                      σ
                                      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
                        )
                      
                    
                  
                  +
                  
                    bx
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    bx
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    
                      a
                      ′
                    
                    ⁢
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    
                      b
                      ′
                    
                    ⁢
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                          ′
                        
                        ⁡
                        
                          [
                          
                            
                              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
          ⁢
          
            
          
          ⁢
          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>LΛ+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), . . . , (X1,Y1) 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 incrementally generating an error locator polynomial, including:
obtaining an initial dataword which includes: (1) a first symbol Xi which includes a first bit pattern of Yi and (2) a second symbol Xj which includes a second bit pattern Yj;
obtaining an initial error locator polynomial associated with the initial dataword; and
using a processor to:
modify the initial dataword to obtain a first test error pattern, including by flipping the first bit pattern of Yi in the first symbol Xi in the initial dataword;
modify the first test error pattern to obtain a second test error pattern, including by flipping the second bit pattern of Yj in the second symbol Xj in the first test error pattern;
generate a first error locator polynomial associated with the first test error pattern based at least in part on an initial error locator polynomial associated with the initial dataword; and
generate a second error locator polynomial associated with the second test error pattern based at least in part on the first error locator polynomial associated with the first test error pattern.

2. The method of claim 1, wherein using the processor further includes:
modifying the initial dataword to obtain a third test error pattern, including by including by flipping the second bit pattern of Yj in the second symbol Xj in the initial dataword;
modifying the third test error pattern to obtain a fourth test error pattern, including by flipping a third bit pattern of Yk in a third symbol Xk in the third test error pattern;
generating a third error locator polynomial associated with the third test error pattern based at least in part on the initial error locator polynomial associated with the initial dataword; and
generating a fourth error locator polynomial associated with the fourth test error pattern based at least in part on the third error locator polynomial associated with the third test error pattern.

3. The method of claim 2, wherein using the processor further includes:
modifying the initial dataword to obtain a fifth test error pattern, including by flipping the third bit pattern of Yk in the third symbol Xk in the initial dataword; and
generating a fifth error locator polynomial associated with the fifth test error pattern based at least in part on the initial error locator polynomial associated with the initial dataword.

4. The method of claim 1 further comprising:
performing soft-output Viterbi decoding to obtain a received dataword, r=[rn−1, rn−2, . . . , r1, r0] and a list of error events, (X1,Y1), (X2,Y2), . . . , (Xτ,Yτ), which corresponds to bit patterns and symbols used in flipping to obtain the first test error pattern and the second test error pattern;
performing error correction decoding using the received dataword and the list of error events; and
determining whether the error correction decoding is successful, wherein using the processor to incrementally generate the error locator polynomial is skipped in the event the error correction decoding is successful.

5. The method of claim 1 further comprising:
generating a plurality of test error patterns that includes the first test error pattern and the second test error pattern; and
selecting one of the plurality of test error patterns.

6. The method of claim 5, wherein selecting one of the plurality of test error patterns includes:
comparing a first minimum distance associated with the first test error pattern with a second minimum distance associated with the second test error pattern;
determining whether to keep information associated with the first test error pattern or the second test error pattern based at least in part on the comparison of the first minimum distance and the second minimum distance;
keeping the first error locator polynomial and a first scratch polynomial associated with the first test error pattern and discarding the second error locator polynomial and a second scratch polynomial associated with the second test error pattern in the event it is determined to keep information associated with the first test error pattern; and
keeping the second error locator polynomial and the second scratch polynomial associated with the second test error pattern and discarding the first error locator polynomial and the first scratch polynomial associated with the first test error pattern in the event it is determined to keep information associated with the second test error pattern.

7. The method of claim 1, wherein at least one of generating the first error locator polynomial or generating the second error locator polynomial includes using the following case statement:




  
    
      
        
          
            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
                  
                
              
            
          
        
      
    
    
      
        
      
    
  
  
    
      
        
          
            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
                  
                
              
            
          
        
      
    
    
      
        
      
    
  
  
    
      
        
          
            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
                  
                
              
            
          
        
      
    
    
      
        
      
    
  



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
                    ⁡
                    
                      [
                      
                        
                          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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                
              
            
          
        
      
    
  



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





  {
  
    
      
        
          
            
              
                
                  
                    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
      ⁢
      
        
      
      ⁢
      5
      ⁢
      
        :
      
      ⁢
      
        
      
      ⁢
      
        L
        Λ
      
    
    >
    
      
        L
        B
      
      ⋀
      
        
          B
          
            (
            
              σ
              i
            
            )
          
        
        ⁡
        
          (
          
            X
            
              i
              +
              1
            
            
              -
              1
            
          
          )
        
      
    
    ≠
    
      0
      ⁢
      
        

      
      ⁢
      
        {
        
          
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                
              
            
          
        
      
    
  



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





  {
  
    
      
        
          
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      a
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          
                            Λ
                            
                              (
                              
                                σ
                                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
        ⁢
        
          
        
        ⁢
        6
        ⁢
        
          :
        
        ⁢
        
          
        
        ⁢
        
          L
          Λ
        
      
      >
      
        
          L
          B
        
        ⋀
        
          
            B
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
      
    
    =
    
      
        0
        ⋀
        
          
            
              Θ
              _
            
            
              (
              
                σ
                i
              
              )
            
          
          ⁡
          
            (
            
              X
              
                i
                +
                1
              
              
                -
                1
              
            
            )
          
        
      
      ≠
      
        0
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                    +
                    
                      ax
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          B
                          
                            (
                            
                              σ
                              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
                  
                
              
            
          
        
      
    
  



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
                        )
                      
                    
                    +
                    
                      ax
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                    +
                    
                      bx
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          
                            i
                            +
                            1
                          
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  ←
                  
                    
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                      ⁢
                      
                        a
                        ′
                      
                      ⁢
                      x
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          Λ
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                    +
                    
                      
                        b
                        ′
                      
                      ⁢
                      x
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          B
                          
                            (
                            
                              σ
                              i
                            
                            )
                          
                        
                        ⁡
                        
                          (
                          x
                          )
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    L
                    Λ
                  
                  ←
                  
                    
                      L
                      Λ
                    
                    +
                    
                      1
                      ⁢
                      
                        
                      
                      ⁢
                      
                        L
                        B
                      
                    
                  
                  ←
                  
                    
                      L
                      B
                    
                    +
                    1
                  
                
              
            
          
        
      
    
  



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
                    ′
                  
                  ⁡
                  
                    [
                    
                      x
                      ⁢
                      
                        
                      
                      ⁢
                      
                        B
                        
                          (
                          
                            σ
                            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
                
              
            
          
        
        .

8. A system for incrementally generating an error locator polynomial, including:
a processor; and
a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to:
obtain an initial dataword which includes: (1) a first symbol Xi which includes a first bit pattern of Yi and (2) a second symbol Xj which includes a second bit pattern Yj;
obtain an initial error locator polynomial associated with the initial dataword; and
modify the initial dataword to obtain a first test error pattern, including by flipping the first bit pattern of Yi in the first symbol Xi in the initial dataword;
modify the first test error pattern to obtain a second test error pattern, including by flipping the second bit pattern of Yj in the second symbol Xj in the first test error pattern;
generate a first error locator polynomial associated with the first test error pattern based at least in part on an initial error locator polynomial associated with the initial dataword; and
generate a second error locator polynomial associated with the second test error pattern based at least in part on the first error locator polynomial associated with the first test error pattern.

9. The system of claim 8, wherein the memory is further configured to provide the processor with further instructions to:
modify the initial dataword to obtain a third test error pattern, including by including by flipping the second bit pattern of Yj in the second symbol Xj in the initial dataword;
modify the third test error pattern to obtain a fourth test error pattern, including by flipping a third bit pattern of Yk in a third symbol Xk in the third test error pattern;
generate a third error locator polynomial associated with the third test error pattern based at least in part on the initial error locator polynomial associated with the initial dataword; and
generate a fourth error locator polynomial associated with the fourth test error pattern based at least in part on the third error locator polynomial associated with the third test error pattern.

10. The system of claim 9, wherein the memory is further configured to provide the processor with further instructions to:
modify the initial dataword to obtain a fifth test error pattern, including by flipping the third bit pattern of Yk in the third symbol Xk in the initial dataword; and
generating a fifth error locator polynomial associated with the fifth test error pattern based at least in part on the initial error locator polynomial associated with the initial dataword.

11. The system of claim 8, wherein the memory is further configured to provide the processor with further instructions to:
perform soft-output Viterbi decoding to obtain a received dataword, r=[rn−1, rn−2, . . . , r1, r0], and a list of error events, (X1,Y1), (X2,Y2), . . . , (Xτ,Yτ), which corresponds to bit patterns and symbols used in flipping to obtain the first test error pattern and the second test error pattern;
perform error correction decoding using the received dataword and the list of error events; and
determine whether the error correction decoding is successful, wherein using the processor to incrementally generate the error locator polynomial is skipped in the event the error correction decoding is successful.

12. The system of claim 8, wherein the memory is further configured to provide the processor with further instructions to:
generated plurality of test error patterns that includes the first test error pattern and the second test error pattern; and
select one of the plurality of test error patterns.

13. The system of claim 12, wherein the instructions for selecting one of the plurality of test error patterns include instructions to:
compare a first minimum distance associated with the first test error pattern with a second minimum distance associated with the second test error pattern;
determine whether to keep information associated with the first test error pattern or the second test error pattern based at least in part on the comparison of the first minimum distance and the second minimum distance;
keep the first error locator polynomial and a first scratch polynomial associated with the first test error pattern and discard the second error locator polynomial and a second scratch polynomial associated with the second test error pattern in the event it is determined to keep information associated with the first test error pattern; and
keep the second error locator polynomial and the second scratch polynomial associated with the second test error pattern and discard the first error locator polynomial and the first scratch polynomial associated with the first test error pattern in the event it is determined to keep information associated with the second test error pattern.

14. The system of claim 8, wherein the instructions for at least one of generating the first error locator polynomial or generating the second error locator polynomial include instructions for using the following case statement:




  
    
      
        
          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
                
              
            
          
        
      
    
  
  
    
      
        
          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
                
              
            
          
        
      
    
  
  
    
      
        
          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
                
              
            
          
        
      
    
  



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
                      ⁡
                      
                        [
                        
                          
                            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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                
              
            
          
        
      
    
  



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
                            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
                        )
                      
                    
                  
                  +
                  
                    bx
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    L
                    Λ
                  
                  ←
                  
                    
                      L
                      Λ
                    
                    +
                    
                      1
                      ⁢
                      
                        
                      
                      ⁢
                      
                        L
                        B
                      
                    
                  
                  ←
                  
                    
                      L
                      B
                    
                    +
                    1
                  
                
                ⁢
                
                  
                
              
            
          
        
      
    
    
      
        
      
    
  



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





  
    
      
        {
        
          
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      a
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          
                            Λ
                            
                              (
                              
                                σ
                                i
                              
                              )
                            
                          
                        
                        ]
                      
                    
                    ⁢
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      b
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          
                            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
            ⁢
            
              
            
            ⁢
            6
            ⁢
            
              :
            
            ⁢
            
              
            
            ⁢
            
              L
              Λ
            
          
          >
          
            
              L
              B
            
            ⋀
            
              
                B
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
        
        =
        
          
            0
            ⋀
            
              
                
                  Θ
                  _
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          ≠
          0
        
      
    
    
      
        
      
    
  
  
    
      
        {
        
          
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                
              
            
          
        
      
    
    
      
        
      
    
  



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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        V
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    bx
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    
                      a
                      ′
                    
                    ⁢
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    
                      b
                      ′
                    
                    ⁢
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  L
                  Λ
                
                ←
                
                  
                    L
                    Λ
                  
                  +
                  
                    1
                    ⁢
                    
                      
                    
                    ⁢
                    
                      L
                      B
                    
                  
                
                ←
                
                  
                    L
                    B
                  
                  +
                  1
                
              
            
          
        
      
    
  



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
                          ′
                        
                        ⁡
                        
                          [
                          
                            x
                            ⁢
                            
                              
                            
                            ⁢
                            
                              B
                              
                                (
                                
                                  σ
                                  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
                    
                  
                
              
            
            .

15. A computer program product for incrementally generating an error locator polynomial, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
obtaining an initial dataword which includes: (1) a first symbol Xi which includes a first bit pattern of Yi and (2) a second symbol Xj which includes a second bit pattern Yj;
obtaining an initial error locator polynomial associated with the initial dataword; and
modifying the initial dataword to obtain a first test error pattern, including by flipping the first bit pattern of Yi in the first symbol Xi in the initial dataword;
modifying the first test error pattern to obtain a second test error pattern, including by flipping the second bit pattern of Yj in the second symbol Xj in the first test error pattern;
generating a first error locator polynomial associated with the first test error pattern based at least in part on an initial error locator polynomial associated with the initial dataword; and
generating a second error locator polynomial associated with the second test error pattern based at least in part on the first error locator polynomial associated with the first test error pattern.

16. The computer program product of claim 15 further comprising computer instructions for:
modifying the initial dataword to obtain a third test error pattern, including by including by flipping the second bit pattern of Yj in the second symbol Xj in the initial dataword;
modifying the third test error pattern to obtain a fourth test error pattern, including by flipping a third bit pattern of Yk in a third symbol Xk in the third test error pattern;
generating a third error locator polynomial associated with the third test error pattern based at least in part on the initial error locator polynomial associated with the initial dataword; and
generating a fourth error locator polynomial associated with the fourth test error pattern based at least in part on the third error locator polynomial associated with the third test error pattern.

17. The computer program product of claim 16 further comprising computer instructions for:
modifying the initial dataword to obtain a fifth test error pattern, including by flipping the third bit pattern of Yk in the third symbol Xk in the initial dataword; and
generating a fifth error locator polynomial associated with the fifth test error pattern based at least in part on the initial error locator polynomial associated with the initial dataword.

18. The computer program product of claim 15 further comprising computer instructions for:
performing soft-output Viterbi decoding to obtain a received dataword, r=[rn−1, rn−2, . . . , r1, r0], and a list of error events, (X1,Y1), (X2,Y2), . . . , Xτ,Yτ), which corresponds to bit patterns and symbols used in flipping to obtain the first test error pattern and the second test error pattern;
performing error correction decoding using the received dataword and the list of error events; and
determining whether the error correction decoding is successful, wherein using the processor to incrementally generate the error locator polynomial is skipped in the event the error correction decoding is successful.

19. The computer program product of claim 15 further comprising computer instructions for:
generating a plurality of test error patterns that includes the first test error pattern and the second test error pattern; and
selecting one of the plurality of test error patterns.

20. The computer program product of claim 19, wherein the computer instructions for selecting one of the plurality of test error patterns include computer instructions for:
comparing a first minimum distance associated with the first test error pattern with a second minimum distance associated with the second test error pattern;
determining whether to keep information associated with the first test error pattern or the second test error pattern based at least in part on the comparison of the first minimum distance and the second minimum distance;
keeping the first error locator polynomial and a first scratch polynomial associated with the first test error pattern and discarding the second error locator polynomial and a second scratch polynomial associated with the second test error pattern in the event it is determined to keep information associated with the first test error pattern; and
keeping the second error locator polynomial and the second scratch polynomial associated with the second test error pattern and discarding the first error locator polynomial and the first scratch polynomial associated with the first test error pattern in the event it is determined to keep information associated with the second test error pattern.

21. The computer program product of claim 15, wherein the computer instructions for at least one of generating the first error locator polynomial or generating the second error locator polynomial include computer instructions for using the following case statement:




  
    
      
        
          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
                
              
            
          
        
      
    
  
  
    
      
        
          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
                
              
            
          
        
      
    
  
  
    
      
        
          Cast
          ⁢
          
            
          
          ⁢
          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
                
              
            
          
        
      
    
  



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
                      ⁡
                      
                        [
                        
                          
                            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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                
              
            
          
        
      
    
    
      
        
      
    
  



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
                            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
                          
                          2
                        
                        ⁢
                        x
                      
                    
                    )
                  
                  ⁢
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                
              
            
          
          
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    bx
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  L
                  Λ
                
                ←
                
                  
                    L
                    Λ
                  
                  +
                  
                    1
                    ⁢
                    
                      
                    
                    ⁢
                    
                      L
                      B
                    
                  
                
                ←
                
                  
                    L
                    B
                  
                  +
                  1
                
              
            
          
        
      
    
    
      
        
      
    
  



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





  
    
      
        {
        
          
            
              
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      
                        X
                        
                          i
                          +
                          1
                        
                        
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    
                      a
                      ⁡
                      
                        [
                        
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          
                            Λ
                            
                              (
                              
                                σ
                                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
            ⁢
            
              
            
            ⁢
            6
            ⁢
            
              :
            
            ⁢
            
              
            
            ⁢
            
              L
              Λ
            
          
          <
          
            
              L
              B
            
            ⋀
            
              
                B
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
        
        =
        
          
            0
            ⋀
            
              
                
                  Θ
                  _
                
                
                  (
                  
                    σ
                    i
                  
                  )
                
              
              ⁡
              
                (
                
                  X
                  
                    i
                    +
                    1
                  
                  
                    -
                    1
                  
                
                )
              
            
          
          ≠
          0
        
      
    
    
      
        
      
    
  
  
    
      
        {
        
          
            
              
                
                  
                    Λ
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      Λ
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            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
                
              
            
          
        
      
    
    
      
        
      
    
  



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
                      )
                    
                  
                  +
                  
                    ax
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        V
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    bx
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    B
                    
                      (
                      
                        σ
                        
                          i
                          +
                          1
                        
                      
                      )
                    
                  
                  ⁡
                  
                    (
                    x
                    )
                  
                
                ←
                
                  
                    
                      B
                      
                        (
                        
                          σ
                          i
                        
                        )
                      
                    
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                  +
                  
                    
                      a
                      ′
                    
                    ⁢
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        Λ
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                  +
                  
                    
                      b
                      ′
                    
                    ⁢
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        B
                        
                          (
                          
                            σ
                            i
                          
                          )
                        
                      
                      ⁡
                      
                        (
                        x
                        )
                      
                    
                  
                
              
            
          
          
            
              
                
                  L
                  Λ
                
                ←
                
                  
                    L
                    Λ
                  
                  +
                  
                    1
                    ⁢
                    
                      
                    
                    ⁢
                    
                      L
                      B
                    
                  
                
                ←
                
                  
                    L
                    B
                  
                  +
                  1
                
              
            
          
        
      
    
  



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
                          ′
                        
                        ⁡
                        
                          [
                          
                            x
                            ⁢
                            
                              
                            
                            ⁢
                            
                              B
                              
                                (
                                
                                  σ
                                  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
                    
                  
                
              
            
            .