Berlekamp–Massey algorithm

From Wikipedia, the free encyclopedia
  (Redirected from Berlekamp-Massey algorithm)
Jump to: navigation, search
Not to be confused with Berlekamp's algorithm.

The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse.[1] Reeds and Sloane offer an extension to handle a ring.[2]

Elwyn Berlekamp invented an algorithm for decoding Bose–Chaudhuri–Hocquenghem (BCH) codes.[3][4] James Massey recognized its application to linear feedback shift registers and simplified the algorithm.[5][6] Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm),[7] but it is now known as the Berlekamp–Massey algorithm.

Description of algorithm[edit]

The Berlekamp–Massey algorithm is an alternate method to solve the set of linear equations described in Reed–Solomon Peterson decoder, which can be summarized as:

In the code examples below, C(x) is a potential instance of Λ(x). The error locator polynomial C(x) for L errors is defined as:

or reversed:

The goal of the algorithm is to determine the minimal degree L and C(x) which results in all syndromes

being equal to 0:

Algorithm: C(x) is initialized to 1, L is the current number of assumed errors, and initialized to zero. N is the total number of syndromes. n is used as the main iterator and to index the syndromes from 0 to (N-1). B(x) is a copy of the last C(x) since L was updated and initialized to 1. b is a copy of the last discrepancy d (explained below) since L was updated and initialized to 1. m is the number of iterations since L, B(x), and b were updated and initialized to 1.

Each iteration of the algorithm calculates a discrepancy d. At iteration k this would be:

If d is zero, the algorithm assumes that C(x) and L are correct for the moment, increments m, and continues.

If d is not zero, the algorithm adjusts C(x) so that a recalculation of d would be zero:

The xm term shifts B(x) so it follows the syndromes corresponding to 'b'. If the previous update of L occurred on iteration j, then m = k - j, and a recalculated discrepancy would be:

This would change a recalculated discrepancy to:

The algorithm also needs to increase L (number of errors) as needed. If L equals the actual number of errors, then during the iteration process, the discrepancies will become zero before n becomes greater than or equal to (2 L). Otherwise L is updated and algorithm will update B(x), b, increase L, and reset m = 1. The formula L = (n + 1 - L) limits L to the number of available syndromes used to calculate discrepancies, and also handles the case where L increases by more than 1.

Code sample[edit]

The algorithm from Massey (1969, p. 124).

  polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */
  /* connection polynomial */
  polynomial(field K) C(x) = 1;  /* coeffs are c_j */
  polynomial(field K) B(x) = 1;
  int L = 0;
  int m = 1;
  field K b = 1;
  int n;

  /* steps 2. and 6. */
  for (n = 0; n < N; n++)
    {
      /* step 2. calculate discrepancy */
      field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i};

      if (d == 0)
        {
          /* step 3. discrepancy is zero; annihilation continues */
          m = m + 1;
        }
      else if (2 * L <= n)
        {
          /* step 5. */
          /* temporary copy of C(x) */
          polynomial(field K) T(x) = C(x);

          C(x) = C(x) - d b^{-1} x^m B(x);
          L = n + 1 - L;
          B(x) = T(x);
          b = d;
          m = 1;
        }
      else
        {
          /* step 4. */
          C(x) = C(x) - d b^{-1} x^m B(x);
          m = m + 1;
        }
    }
  return L;

The algorithm for the binary field[edit]

The following is the Berlekamp–Massey algorithm specialized for the typical binary finite field F2 (also written GF(2)). The field elements are '0' and '1'. The field operations '+' and '−' are identical and are equivalent to the 'exclusive or' operation, XOR. The multiplication operator '*' becomes the logical AND operation. The division operator reduces to the identity operation (i.e., field division is only defined for dividing by 1, and x/1 = x).

  1. Let be the bits of the stream.
  2. Initialise two arrays and each of length to be zeroes, except
  3. assign .
  4. For step 1 while :
    • Let be .
    • if , then is already a polynomial which annihilates the portion of the stream from to .
    • else:
      • Let be a copy of .
      • Set up to (where is the Exclusive or operator).
      • If , set , set , and let ; otherwise leave , and alone.

At the end of the algorithm, is the length of the minimal LFSR for the stream, and we have for all .

Code sample for the binary field in Java[edit]

The following code sample is for a binary field.

    public static int runTest(int[] array) {
        final int N = array.length;
        int[] b = new int[N];
        int[] c = new int[N];
        int[] t = new int[N];
        b[0] = 1;
        c[0] = 1;
        int l = 0;
        int m = -1;
        for (int n = 0; n < N; n++) {
            int d = 0;
            for (int i = 0; i <= l; i++) {
                d ^= c[i] * array[n - i];
            }
            if (d == 1) {
                System.arraycopy(c, 0, t, 0, N);
                int N_M = n - m;
                for (int j = 0; j < N - N_M; j++) {
                    c[N_M + j] ^= b[j];
                }
                if (l <= n / 2) {
                    l = n + 1 - l;
                    m = n;
                    System.arraycopy(t, 0, b, 0, N);
                }
            }
        }
        return l;
    }

See also[edit]

References[edit]

  1. ^ Reeds & Sloane 1985, p. 2
  2. ^ Reeds, J. A.; Sloane, N. J. A. (1985), "Shift-Register Synthesis (Modulo n)" (PDF), SIAM Journal on Computing 14 (3): 505–513, doi:10.1137/0214038 
  3. ^ Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy 
  4. ^ Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory (Revised ed.), Laguna Hills, CA: Aegean Park Press, ISBN 0-89412-063-8 . Previous publisher McGraw-Hill, New York, NY.
  5. ^ Massey, J. L. (1969), "Shift-register synthesis and BCH decoding" (PDF), IEEE Trans. Information Theory, IT-15 (1): 122–127 
  6. ^ Ben Atti, Nadia; Diaz-Toca, Gema M.; Lombardi, Henri, The Berlekamp–Massey Algorithm revisited, CiteSeerX: 10.1.1.96.2743 
  7. ^ Massey 1969, p. 124

External links[edit]