Berlekamp–Massey Binary Complexity

Worked Example

Consider the LFSR sequence prefix of length 4: 1001. We apply the Berlekamp-Massey algorithm over the finite field GF(2).

1. Initialize: Sequence s = [1, 0, 0, 1], Connection polynomial C = [1], Previous polynomial B = [1], Linear complexity L = 0, shift m = 1.
2. Step 1 (t=0): Read s[0] = 1.
   Discrepancy d = s[0] = 1.
   Update C: C_new = C ^ (B shifted by m) = [1] ^ [0, 1] = [1, 1].
   Since 2L <= t (0 <= 0), update L = t + 1 - L = 1, B = old_C = [1], m = 1.
3. Step 2 (t=1): Read s[1] = 0.
   Discrepancy d = s[1] ^ (C[1]*s[0]) = 0 ^ (1*1) = 1.
   Update C: C_new = [1, 1] ^ ([0, 1] shifted by 1) = [1, 1] ^ [0, 1] = [1, 0].
   Here 2L <= t is false (2 <= 1 is false). Increment m = 2.
4. Step 3 (t=2): Read s[2] = 0.
   Discrepancy d = s[2] ^ (C[1]*s[1]) = 0 ^ (0*0) = 0.
   Since d = 0, C remains [1, 0]. Increment m = 3.
5. Step 4 (t=3): Read s[3] = 1.
   Discrepancy d = s[3] ^ (C[1]*s[2]) = 1 ^ (0*0) = 1.
   Update C: C_new = [1, 0] ^ ([1] shifted by 3) = [1, 0] ^ [0, 0, 0, 1] = [1, 0, 0, 1].
   Since 2L <= t (2 <= 3 is true), update L = 3 + 1 - 1 = 3, B = [1, 0], m = 1.

The final linear complexity is L = 3 with connection coefficients 1, 0, 0, 1.

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.

Model Limitations

This implementation operates exclusively over the finite field GF(2), utilizing XOR arithmetic. It is specifically designed for binary sequences and does not generalize to real numbers or arbitrary finite fields. Furthermore, requesting a prefix length that exceeds the available sequence data (such as asking for length 1 from an empty sequence) constitutes an invalid bound, and the algorithm correctly refuses to compute a result for such undefined states.

References

The Berlekamp-Massey algorithm and its role in determining the minimal linear complexity of shift registers are covered extensively in modern coding theory literature. For foundational material on finite fields and linear feedback shift registers, refer to the Stanford CS250 course materials, which detail sequence generation and error-correcting codes.