Sequences with good correlation property based on depth and interleaving techniques

A well-known operator of sequences over finite field is the derivative, which is used to investigate the complexity of sequences in game theory, communication theory and cryptography. According to the operator, a corresponding complexity of the sequence is called (the first) depth, which also contributes to another two definitions (the second and third depths) by using polynomial factor and high order difference, respectively. For a sequence of period \(n\) over \(F_q\) (a finite field with \(q\) elements and characteristic \(p\)), the three depths are the same as its linear complexity if \(n=p^r \ (r\ge 0)\). This paper focuses on sequence s of period \(n\) with infinite third depth. For cyclic-left-shift-difference operator \(L-1\) on \({\varvec{s}}\), we generally depict circulant matrix structure of the operator \((L-1)^i\) for all \(i>0\) and determine its rank. Furthermore, our results show that the interleaving technique really works with difference operator on producing sequences with good correlation property and long period, which are constructed from 2-level autocorrelation sequences of period \(2^r-1\) except \(m\)-sequences. The method is lightweight since the computation complexity is \(\Theta (N)\) and only the XOR logical operator is used. In addition, ultimate period of a sequence \(\{(L -1)^{i}({\varvec{s}})\}_{i\ge 0}\) is investigated systematically. Some upper bounds on the ultimate period and a formula to determine the least ultimate period are presented.