Linear complexity and 2-adic complexity of binary interleaved sequences with optimal autocorrelation magnitude

Abstract

A construction of binary sequences with period 4N and optimal autocorrelation magnitude has been investigated based on sampling and interleaving technique. We determine the exact value of the linear complexity of the constructed sequences according to the deep relationship among the characteristic polynomials, and show it is 2N+2. Moreover, we determine the 2-adic complexity of these sequences by the autocorrelation function, and show it can attain the maximum value. Results show that such sequences can resist both the Berlekamp-Massey attack and the Rational Approximation Algorithm, in addition are good for communication.

Keywords

• binary sequences
• interleaved sequences
• linear complexity
• 2-adic complexity
• autocorrelation