4
$\begingroup$

Use of Linear Feedback Shift Registers(LFSR) is discouraged due to complexity of order of it's length.

Recently Non-Linear LFSR has been talked about.

I am curious how the properties of LFSR based m-sequence generators hold in this case:

  1. Auto-Correlation- low
  2. Cross-Correlation- Very low
  3. Periodicity $~ 2^n-1$

How NLFSR performs on these metrics? Are they suitable to be used for multiple access systems or say in spreading sequences.

How difficult is it to hack into these systems compared to Berkelamp-Massey algorithm?

Improve this question
$\endgroup$
3
  • $\begingroup$ There won't be an answer valid for all NLFSRs. In particular, from any LFSR of periodicity $2^n-1$ we can make a NLFSR of periodicity $2^n$ (by inserting an extra zero in the sequence where it contains $n-1$ consecutive zeros); we get something very similar to the original, and amenable to variants of the Berkelamp-Massey algorithm. $\endgroup$
    – fgrieu ♦
    Commented Dec 28, 2016 at 9:43
  • $\begingroup$ Agree! But it's said that NLFSR are more secure. My interest in mainly in knowing properties Auto Correlation and Cross Correlation as I am exploring replacements of LFSR as spreading sequences. $\endgroup$
    – Jay
    Commented Dec 28, 2016 at 10:32
  • $\begingroup$ A side issue, but do know that if you have a "preferred pair" of m-sequences of the same period (basically one is a primitive decimation of the other) the cross correlation is $-1$ or $-1\pm 2^{(n+1)/2}$ for $n$ odd, otherwise the cross correlation of two m-sequences is worse? So property 2 does not hold for m sequences. Autocorrelation is very low. $\endgroup$
    – kodlu
    Commented Dec 29, 2016 at 0:22

1 Answer 1

Reset to default
4
$\begingroup$

The reason such generators are used is to avoid the Berlekamp Massey attack by introducing high linear complexity. However, even though there are many publications on these, the theory is far from complete.

One line of research is finding NLFSRs that generate de Bruijn sequences, this goes back to the 1970s.

For your specific question, there is an almost tailor made solution in terms of autocorrelations. The GMW sequences (Gordon Mills Welch) are nonlinear with high linear complexity and autocorrelation same as m-sequences. They are constructed by using an intermediate field and a power function as a permutation of the intermediate field. So instead of $$s(t)=tr^n_1(\alpha^t)$$ as in m-sequences take $n=km,$ with $k\geq 2$ an integer and consider the sequence $$s(t)=tr^n_m([tr^m_1(\alpha^t)]^u)$$ which is your basic GMW sequence, provided $gcd(2^n-1,u)=1$ so that the power map is a permutation.

Cross correlations are a bit harder to control, depending on how many sequences you want, but there are some results in the third reference which may make it easier (beyond experimentation).

The Spread Spectrum Handbook covers GMW sequences from an engineering point of view. J-S. No generalized GMW designs, Klapper et al introduced Generalized GMW sequences, etc. The talk slides by Helleseth here are a good point to start in terms of general background.

Some references:

R. A. Scholtz and L. R. Welch, GMW Sequences, IEEE Trans. on Inform. Theory, 30(3):548-553, 1984

H. Fredricksen. A Survey of Full Length Nonlinear Shift Register Cycle Algorithms. SIAM Review, 24(2):195–221, 1982.

Li, Hu and Zeng, A Criterion for Determining the Crosscorrelation of Binary Sequences from GMW Constructions, IEEE International Workshop on Signal Design and Applications.

Improve this answer
$\endgroup$

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.