Berlekamp–Massey algorithm: Difference between revisions

Revision as of 17:32, 5 February 2025

Revision as of 12:33, 15 February 2025

Line 95:

The algorithm from {{Harvtxt|Massey|1969|p=124}} for an arbitrary field:

<!-- Notes: notation changes from Massey:

Massey Here

Line 105 ⟶ 106:

-->

polynomial(field ''K'') s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */

<syntaxhighlight lang="c">

polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degreeconnection polynomial) */

polynomial(field K) BC(x) = 1; /* coeffs are c_j */

/* connection polynomial */

polynomial(field K) CB(x) = 1; /* coeffs are c_j */

int mL = m + 10;

polynomial(field K) B(x) = 1;

int Lm = 01;

int m field K b = 1;

field K b = 1int n;

/* steps 2. and 6. */

int n;

for (n = 0; n < N; n++) {

/* stepsstep 2. andcalculate 6.discrepancy */

field K d = s_n + {{math|&sum;{{su|p=L|b=i=1}} c_i s_{n - i}}} <!--∑i=1Lci⋅sn−i;-->

for (n = 0; n < N; n++) {

/* step 2. calculate discrepancy */

field K d = s_nif +(d ∑i=1Lci⋅sn−i;= 0) {

/* step 3. discrepancy is zero; annihilation continues */

if (d m == 0)m + {1;

/*} stepelse 3.if discrepancy(2 is* zero;L annihilation<= continuesn) */{

m = m + 1;/* step 5. */

} else if (2 /* Ltemporary <=copy nof C(x) {*/

/* step 5. */ polynomial(field K) T(x) = C(x);

/* temporary copy of C(x) */

polynomial(field K) T C(x) = C(x) - d b^-1 x^m B(x);

L = n + 1 - L;

C(x) = C B(x) -= d b−1xm BT(x);

L = n + 1b -= Ld;

B(x) m = T(x)1;

b} =else d;{

m = 1; /* step 4. */

C(x) = C(x) - d b^-1 x^m B(x);

} else {

/* step 4. */ m = m + 1;

C(x) = C(x) - d b−1xm B(x);}

m = m + 1;

}

return L;

}

return L;

</syntaxhighlight>

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.

}/* else... {*/

<syntaxhighlight lang="c">

for (n = 0; n < N; n++) {

/* ... */

/* if odd step number, discrepancy == 0, no need to calculate it */

for (n = 0; n < N; n++) {

if ((n&1) != 0) {

/* if odd step number, discrepancy == 0, no need to calculate it */

if ((n&1) ! m = 0)m {+ 1;

m = m + 1continue;

continue;}

}/* ... */

/* ... */

</syntaxhighlight>

==See also==