I want to see and mathematically verify how PN sequence generated by LFSR or maximum length codes would correlate (auto-correlation and cross correlation) for seeds of varying correlation.

Say I want to generate 512 bits of PN sequence on two sides (A and B). To hide the possible output from eavesdropper I choose some seeds (which can be generated by both A and B simultaneously). The issue is the seeds(sequence of 512 bits) generated at various instants of time are correlated with previous time instants.

I want to:

  1. See how correlation in input seed affects correlation in output

Is there any paper or reference literature survey for same?


My research efforts...

As of now I am studying properties of PN sequence generators. In my research I have a source which generates correlated sequences of various degrees. I want to analyse what happens to PN sequence generated using those seeds.

  • $\begingroup$ How do you define correlation in the seeds? How are the seeds themselves generated? $\endgroup$ – kodlu Oct 12 '16 at 5:19

Caveat: LFSRs outputs are vulnerable to known plaintext attacks using the Berlekamp Massey algorithm.

Given a maximal length sequence $s(t)$ of period $2^n-1$ generated by a primitive LFSR, all its windows of length $\ell \geq n$ are unique so partial period correlation of such lengths can uniquely determine the phase, thus the seed.

All primitive LFSR sequences of this length are obtainable by regular decimations of this sequence, i.e., $s(dt)$ where $gcd(2^n-1,d)=1.$

So this is an exploitable correlation.

Another relevant property is the shift and add property

$$s(t+k)\oplus s(t)=s(t+z(k))$$

that comes from the fact that the maximal length sequence and its cyclic shifts together with the all zero vector form a linear code. This is another source of correlation.Here $$a^{z(k)} =1+ a^k$$ defines the so called Zech logarithm $z(\cdot)$, if we use the trace representation $$s(t)=Tr(a^t)$$ with $a \in GF(2^n).$

The book by Golomb and Gong and a survey by Sarwate and Pursley in the Proceedings of the IEEE are good places to start.

  • $\begingroup$ What is obvious is that a correlated seed just makes the output shifted since every possible permutations out of $2^n-1$ will be in state of the LFSR some time or other. $\endgroup$ – Jay Dec 9 '16 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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