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. Reeds and Sloane offer an extension to handle a ring. Shojiro Sakata extended the Berlekamp–Massey algorithm to multidimensional arrays; the resulting Berlekamp–Massey–Sakata (BMS) algorithm is used in decoding some algebraic geometry codes, including one-point algebraic geometry codes, and variants have been developed for multipoint codes from algebraic curves. Elwyn Berlekamp invented an algorithm for decoding Bose–Chaudhuri–Hocquenghem (BCH) codes. James Massey 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.