-1
$\begingroup$

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:

https://www.dsprelated.com/thread/2716/semi-blind-ofdm-channel-estimation

Thank you !

$\endgroup$
3
  • $\begingroup$ Can you clarify what is the difference between "bit sequence" and "LFSR sequence"? Do you mean the LFSR that produced the bit sequence? $\endgroup$
    – MBaz
    Commented May 31, 2019 at 14:37
  • $\begingroup$ 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 $\endgroup$ Commented Jun 5, 2019 at 16:03
  • $\begingroup$ 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 ? $\endgroup$ Commented Jun 17, 2019 at 7:55

1 Answer 1

0
$\begingroup$

Yes you can! Given an Nth order polynomial generator, with 2N consecutive samples we can create N equations with N unknowns for the LFSR polynomial which you can then solve as a system of simultaneous equations. This would require matrix inversion in GF(2) to do directly but instead thanks to the Berlekamp-Massey algorithm this can be solved iteratively and very efficiently. For further details of the algorithm including pseudo-code see this Wikipedia page

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Commented May 21, 2022 at 19:02
  • $\begingroup$ 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,..... $\endgroup$ Commented May 21, 2022 at 19:57
  • $\begingroup$ .... 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. $\endgroup$ Commented May 21, 2022 at 20:02
  • $\begingroup$ This would be useful for a (start up)[github.com/nihalpasham/google_pay_ultrasound_tokens/blob/master/…. $\endgroup$
    – Jay Patel
    Commented Jun 20, 2022 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.