Berlekamp–Massey 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 alternative to the Reed–Solomon Peterson decoder for solving the set of linear equations. It can be summarized as finding the coefficients Λ_j of a polynomial Λ(x) so that for all positions i in an input stream S:

${\displaystyle S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.}$

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:

${\displaystyle C(x)=C_{L}x^{L}+C_{L-1}x^{L-1}+\cdots +C_{2}x^{2}+C_{1}x+1}$

or reversed:

${\displaystyle C(x)=1+C_{1}x+C_{2}x^{2}+\cdots +C_{L-1}x^{L-1}+C_{L}x^{L}.}$

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

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}}$

being equal to 0:

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}=0,\qquad L\leq n\leq N-1.}$

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:

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots +C_{L}S_{k-L}.}$

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:

${\displaystyle C(x)\gets C(x)-(d/b)x^{m}B(x).}$

The x^m 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:

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}S_{j-1}+\cdots ).}$

This would change a recalculated discrepancy to:

${\displaystyle d=d-(d/b)b=d-d=0.}$

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 2L. 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.

Pseudocode[edit]

The algorithm from Massey (1969, p. 124) for an arbitrary field:

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 + ${\displaystyle \sum _{i=1}^{L}c_{i}\cdot 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 ${\displaystyle 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 ${\displaystyle b^{-1}x^{m}}$ B(x);         m = m + 1;     } } return L; 

In the case of binary GF(2) BCH code, the discrepancy d will be zero on all odd steps, so a check can be added to avoid calculating it.

/* ... */ for (n = 0; n < N; n++) {     /* if odd step number, discrepancy == 0, no need to calculate it */     if ((n&1) != 0) {         m = m + 1;         continue;     } /* ... */ 

See also[edit]

• Reed–Solomon error correction
• Reeds–Sloane algorithm, an extension for sequences over integers mod n
• Nonlinear-feedback shift register (NLFSR)

References[edit]

External links[edit]

• "Berlekamp-Massey algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Berlekamp–Massey algorithm at PlanetMath.
• Weisstein, Eric W. "Berlekamp–Massey Algorithm". MathWorld.
• GF(2) implementation in Mathematica
• (in German) Applet Berlekamp–Massey algorithm
• Online GF(2) Berlekamp-Massey calculator