Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences

Abstract

In this paper, a new constructive approach of determining the first descent point distribution for the k-error linear complexity of 2 n -periodic binary sequences is developed using the sieve method and Games-Chan algorithm. First, the linear complexity for the sum of two sequences with the same linear complexity and minimum Hamming weight is completely characterized and this paves the way for the investigation of the k-error linear complexity. Second we derive a full representation of the first descent point spectrum for the k-error linear complexity. Finally, we obtain the complete counting functions on the number of 2 n -periodic binary sequences with given 2 m -error linear complexity and linear complexity 2 n - (2 i1 + 2 i2 + … + 2 im ), where 0 = i 1 < i 2 < … < i m < n. In summary, we depict a full picture on the first descent point of the k-error linear complexity for 2 n -periodic binary sequences and this will help us construct some sequences with requirements on linear complexity and k-error complexity.