# Derive the LFSR sequence from demodulated bitstream

I'm new here and hope to have good feedback from you.

I'm trying to blindly demodulate an RF signal and managed to get a sequence of bits for a preamble. After some research, I'm in fact exactly in the same situation as this guy:

OFDM Preamble Ripple Structure in Frequency Domain

My question is: given a bit sequence, how can you derive the LFSR sequence (and initial seed) like he seems to have done here:

Thank you !

• Can you clarify what is the difference between "bit sequence" and "LFSR sequence"? Do you mean the LFSR that produced the bit sequence?
– MBaz
Commented May 31, 2019 at 14:37
• Sorry for the late answer, I'm off for a few days. Yes I wanted to say: how to find the generating LFSR polynom and seed given a demodulated bitstream Commented Jun 5, 2019 at 16:03
• Dear all, I'm still stuck with that. I've derived a similar sequence than the one described in the referenced post but I still don't see how to find the corresponding generating polynom (apart from brute force ?). Is that even possible ? Commented Jun 17, 2019 at 7:55

• Just a minor comment: If we know that the LFSR has degree $N$, then there are only $N-1$ coefficients that need to be determined ($x_0$ and $x_{N}$ are known to have value $1$). The advantage of the Berlekamp-Massey algorithm is that it finds the shortest LFSR that generates the given bitstream. If the unknown LFSR that actually generated the bit stream is of length $N$, then the B-M algorithm finds it after examining $2N$ bits of the bitstream. If more bits are available, further iterations of the algorithm merely confirm the result. Commented May 21, 2022 at 19:02
• To continue my previous comment, if the number of bits $2s$ in the bitstream is less than twice the length of the LFSR that actually generated the bitstream, then the Berlekamp-Massey algorithm finds the shortest LFSR that can generate these $2s$ bits. This synthesized LFSR rarely has any similarity to the actual LFSR; in particular, the length of the synthesized LFSR is often close to $2s$. This is in accordance with complexity theory which says that the shortest program to print an arbitrary sequence of length $M$ is of length $M+c$ where $c$ is a constant. In other words,..... Commented May 21, 2022 at 19:57
• .... for arbitrary sequences of length $M$, it is easiest to just store the sequence and print it out (the $c$ is the length of the printf command or equivalent) than to write an elaborate C++ program to somehow calculate the sequence and then print it out. Commented May 21, 2022 at 20:02