On the stability of 2^n-periodic binary sequences

Official URL: http://dx.doi.org/10.1109/TIT.2004.842709

The k-error linear complexity of a periodic binary sequence is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits per period. This contribution focuses on the case of 2(n)-periodic binary sequences. For k = 1, 2, the exact formula for the expected k-error linear complexity of a sequence having maximal possible linear complexity 2(n), and the exact formula of the expected 1-error linear complexity of a random 2(n)-periodic binary sequence are provided. For k greater than or equal to 2, lower and upper bounds on the expected value of the k-error linear complexity of a random 2(n)-periodic binary sequence are established.