BerlekampMassey

Berlekamp–Massey is an algorithm for determining the shortest linear feedback shift register (LFSR) that generates a given finite sequence over a finite field. It is named after Elwyn Berlekamp and James Massey and plays a central role in coding theory and sequence analysis. The output is the minimal connection polynomial and the corresponding linear complexity, the smallest L such that the sequence satisfies a linear recurrence of order L.

In processing a sequence s0, s1, ..., s_{N-1} over a field F, the algorithm maintains a current connection polynomial C(x) of degree L, a copy B(x) of a previous C, the current length L, and a gap counter m. For each n, it computes the discrepancy d = s_n + sum_{i=1..L} c_i s_{n-i} (with s_j defined as zero for j < 0). If the discrepancy d is zero, the algorithm increments m and proceeds. If d is nonzero, it updates C by C(x) <- C(x) - (d/b) x^m B(x), where b is the last nonzero discrepancy and B is the previous C. If 2L <= n, it also sets B := C (before the update), L := n+1 - L, b := d, and resets m to 1; otherwise it increments m. Over GF(2) the division by b reduces to 1 and the update can be written as C(x) <- C(x) + x^m B(x).

Complexity and variants: the algorithm runs in O(n^2) field operations and uses O(L) memory, with L the final linear complexity. It generalizes to any finite field and is widely used in decoding BCH and Reed–Solomon codes, as well as in analysis and design of pseudo-random sequences and certain stream ciphers.

---