THE GARDEN

Berlekamp-Massey Algorithm

Updated 13 Sep 2026

• •

  What it is

  • •

    Given a finite bit sequence, Berlekamp–Massey finds a shortest linear recurrence consistent with it. For a sequence of linear complexity L, 2L consecutive bits suffice to recover its minimal recurrence under the usual linear-sequence assumptions. This need not identify the physical register’s exact taps or make a nonlinear filtered sequence easy to predict.

• •

  When to apply

  • •

    You have a sufficiently long bit sequence (at least $\sim2n$ bits if you suspect an $n$-bit LFSR) believed to come from an LFSR with unknown feedback taps.

• •

  Symbols and assumptions

  • •

    $s_0,s_1,\ldots$ are observed bits. A connection polynomial $C(X)=1+c_1X+\cdots+c_LX^L$ represents $s_i=\bigoplus_{j=1}^L c_j s_{i-j}$. L is the minimal recurrence length for the sequence.

• •

  Math — step by step

  • •
    1. At position i, compute discrepancy $d=s_i\oplus\bigoplus_{j=1}^L c_j s_{i-j}$. Zero means the current recurrence predicts this bit correctly.
  • •
    2. For nonzero discrepancy, XOR a shifted saved connection polynomial into C to cancel it. If $2L\le i$, increase L to $i+1-L$ and save the previous C as the next correction reference.
  • •
    3. For a sequence of linear complexity L, 2L consecutive bits suffice to recover its minimal recurrence. The physical register may be longer or use a nonminimal realization; the algorithm does not uniquely identify that hardware.
  • •
    4. Connection-polynomial coefficients describe delays. Translate delays into the implementation’s shift direction and tap convention before generating bits. Test on held-out output. Nonlinear filtering can make the visible complexity far exceed the register length.
• •

  Worked example

  • •

    Take $s=1,0,0,1,0,1,1,1,0,0$. Scan with initial $C=1,L=0$. The successive (C,L) after indexes 0,1,2,3 are $(1+X,1)$, $(1,1)$, $(1,1)$, $(1+X^3,3)$.

  • •

    At index 4 the discrepancy is zero. At index 5 the prediction from $1+X^3$ is $s_2=0$, but $s_5=1$; the correction gives $C=1+X^2+X^3$, L=3.

  • •

    Thus $s_i=s_{i-2}\oplus s_{i-3}$. Check held-out indexes 6–9: $0\oplus1=1$, $1\oplus0=1$, $1\oplus1=0$, $1\oplus1=0$. The next bit is $s_{10}=s_8\oplus s_7=1$.

• •

  Python

  • •

    def berlekamp_massey(seq):
            n = len(seq)
            C, B = [1]+[0]*n, [1]+[0]*n
            L, m, b = 0, 1, 1
            for i in range(n):
                d = seq[i] ^ sum(C[j] & seq[i-j] for j in range(1, L+1)) % 2
                if d == 0:
                    m += 1
                elif 2*L <= i:
                    T = C[:]
                    for j in range(n+1-m):
                        C[j+m] ^= d & B[j]
                    L, B, m, b = i+1-L, T, 1, d
                else:
                    for j in range(n+1-m):
                        C[j+m] ^= d & B[j]
                    m += 1
            return C[:L+1], L
    

• •

  SageMath

  • •

    berlekamp_massey() is available directly, operating over a sequence of GF(2) elements

  • •

    from sage.matrix.berlekamp_massey import berlekamp_massey
    poly = berlekamp_massey([GF(2)(b) for b in bits])
    # Translate the returned polynomial convention to your shift/tap indexing.
    # Regenerate held-out bits before accepting the recurrence.
    

• •

  Related

  • •

    Linear Feedback Shift Register (LFSR)

  • •

    Extended Euclidean Algorithm

• •

  Cards

  • •

    What does the usual 2L-bit recovery statement identify?

    • •

      The minimal recurrence of a sequence of linear complexity L. A physical register can be longer, nonminimal, or hidden behind a nonlinear filter.

  • •

    What does the algorithm actually compute?

    • •

      The shortest LFSR (its exact feedback polynomial) capable of producing the given bit sequence — the sequence's linear complexity.

◌ Explore connections in Graph view