Berlekamp–Massey algorithm: Difference between revisions

Revision as of 17:32, 5 February 2025

Latest revision as of 06:47, 3 May 2025

(5 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Algorithm on linear-feedback shift registers}}

{{distinguish|Berlekamp's algorithm}}

[[File:Berlekamp–Massey_algorithmBerlekamp–Massey algorithm.png | thumb | right | 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 (field theory)|minimal polynomial]] of a linearly [[Recurrence relation|recurrent sequence]] in an arbitrary [[field (mathematics)|field]]. The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse.<ref>{{Harvnb|Reeds|Sloane|1985|p=2}}</ref> Reeds and Sloane offer an extension to handle a [[ring (mathematics)|ring]].<ref>{{Citation |last1=Reeds |first1=J. A. |last2=Sloane |first2=N. J. A. |author-link2=N. J. A. Sloane |journal=SIAM Journal on Computing |volume=14 |issue=3 |pages=505–513 |year=1985 |title=Shift-Register Synthesis (Modulo n) |url=http://neilsloane.com/doc/Me111.pdf |doi=10.1137/0214038 |citeseerx=10.1.1.48.4652 }}</ref>

Line 104:

T(D) T(x) polynomial

-->

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr">

polynomial(field ''K'') s(x) = ... <span class="cm">/* coeffs are s_js_j; output sequence as N-1 degree polynomial) */</span>

<syntaxhighlight lang="c">

<span class="cm">/* connection polynomial */</span>

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

polynomial(field K) C(x) = 1; <span class="cm">/* coeffs are c_j */</span>

/* 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;

<span class="cm">/* steps 2. and 6. */</span>

int n;

<span class="k">for</span> (n = 0; n < N; n++) {

<span class="cm">/* step 2. calculate discrepancy */</span>

/* steps 2. and 6. */

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 */

<span class="k">if</span> (d == 0) {

field K d = s_n + ∑i=1Lci⋅sn−i;

<span class="cm">/* step 3. discrepancy is zero; annihilation continues */</span>

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

} <span class="k">else</span> <span class="k">if</span> (2 * L <= n) {

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

m <span class="cm">/* mstep +5. 1;*/</span>

} else if (2 * L <span class="cm">/* ntemporary copy of C(x) {*/</span>

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

/* temporary copy of C(x) */

polynomial(field K) T C(x) = C(x) - d b⁻¹ 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} <span class="k">else</span> d;{

m <span class="cm">/* step 4. 1;*/</span>

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

} else {

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

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

m = m + 1;

}

<span class="k">return</span> L;

}

</div>

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.

{{sxhl|2=c|1=<nowiki/>

}/* 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==

Line 165 ⟶ 162:

==External links==

* {{springer|title=Berlekamp-Massey algorithm|id=p/b120140}}

* [https://web.archive.org/web/20120716181541/http://planetmath.org/encyclopedia/{{PlanetMath|BerlekampMasseyAlgorithm.html |Berlekamp–Massey algorithm] at [[PlanetMath]].}}

* {{MathWorld|urlname=Berlekamp-MasseyAlgorithm|title=Berlekamp–Massey Algorithm}}

* [https://code.google.com/p/lfsr/ GF(2) implementation in Mathematica]