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:
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 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.
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 + ;
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(x);
L = n + 1 - L;
B(x) = T(x);
b = d;
m = 1;
} else {
/* step 4. */
C(x) = C(x) - d 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;
}
/* ... */