The Berlekamp-Massey Algorithm

The Berlekamp-Massey algorithm computes the error location polynomial s(X). The main steps involved in the algorithm are:

    Initialize the following values:

s(X) = 1

       l = 0

      b(X) = 0

    For m =1 to 2t, do the following:

Compute the discrepancy :

d = siSm-i

Where si is the co-efficient corresponding to X i in s(X)

If   d 0, do the following:
             s (X)  = s(X) dXb(X)

        If  2l <m , do the following:

                    b(X) = d-1s(X)

                     l = m - l

         Else (2l m), do the following:
                     b(X) = X b(X)
                    s (X) = s(X)

Else (d = 0), do the following:

          b(X) = X b(X)

    If the degree of  s(X) l, then more than t errors have occurred and they cannot be corrected.