Period, correlation and auto-correlation of non-linear feedback shift registers based sequences 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:


Auto-Correlation- low
Cross-Correlation- Very low
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?
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.