Berlekamp–Massey Binary Complexity

The Berlekamp–Massey algorithm synthesizes the shortest linear feedback shift register (LFSR) capable of generating a given finite binary sequence. By iteratively processing the sequence one bit at a time, it dynamically updates the discrepancy and connection polynomial, providing the minimal linear recurrence.

Interactive Experiment

Trace the discrepancy and connection shifts dynamically:

1. Open the interactive module at https://riano.app/module/berlekamp-massey-binary-complexity.
2. Select the Sequence control and choose Alternating. Observe the synthesized complexity drop to 2, capturing the simple repeating pattern.
3. Change the Prefix length control to examine how the required minimal complexity grows as more bits are revealed. Notice how the visual trace updates the connection polynomial taps whenever a non-zero discrepancy is found.