Berlekamp–Massey algorithm

<p>The Berlekamp–Massey algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that will find the shortest <a href="/facts/Linear-feedback_shift_register/22pktBbX">linear-feedback shift register</a> (LFSR) for a given binary output sequence. The algorithm will also find the <a href="/facts/Minimal_polynomial_(field_theory)/dJv9Q0Kh">minimal polynomial</a> of a linearly <a href="/facts/Recurrence_relation/JolXC71M">recurrent sequence</a> in an arbitrary <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a>.  The field requirement means that the Berlekamp–Massey algorithm requires all non-zero elements to have a multiplicative inverse.  Reeds and Sloane offer an extension to handle a <a href="/facts/Ring_(mathematics)/JnCUXz63">ring</a>.
</p><p><a href="/facts/Elwyn_Berlekamp/zUTTIlF6">Elwyn Berlekamp</a> invented an algorithm for decoding <a href="/facts/BCH_code/1KelJGxF">Bose–Chaudhuri–Hocquenghem (BCH) codes</a>. <a href="/facts/James_Massey/qyfqKnQH">James Massey</a> recognized its application to linear feedback shift registers and simplified the algorithm. Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm), but it is now known as the Berlekamp–Massey algorithm.
</p>

Berlekamp–Massey algorithm open-in-new

Berlekamp–Massey algorithm