The Berlekamp-Massey algorithm finds the shortest linear recurrence satisfied by a finite sequence over a field. It processes symbols incrementally, updating the connection polynomial whenever the current recurrence has a nonzero discrepancy.
The shortest binary linear recurrence producing the prefix has length three:Its connection polynomial is .
Articles by others on the same topic
The Berlekamp–Massey algorithm is a fundamental algorithm in coding theory and information theory used to find the shortest linear feedback shift register (LFSR) that can generate a given finite sequence of output. It is particularly useful for determining the linear recurrence relations for a sequence, which is essential in applications such as error correction coding, cryptography, and sequence analysis.