On the stability of 2n-periodic binary sequences

Abstract

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