The characterization of 2n-periodic binary sequences with fixed 1-error linear complexity

Abstract

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, using fast algorithms for computing the linear complexity and the k-error linear complexity of 2 n-periodic binary sequences, Meidl determined the counting function and expected value for the 1-error linear complexity of 2n-periodic binary sequences. In this paper, we study the linear complexity and the 1-error linear complexity of 2n-periodic binary sequences. Some interesting properties of the linear complexity and the 1-error linear complexity of 2 n-periodic binary sequences are obtained. Using these properties, we characterize the 2n-periodic binary sequences with fixed 1-error linear complexity. Along the way, we obtain a new approach to derive the counting function for the 1-error linear complexity of 2n-periodic binary sequences. Finally, we give new fast algorithms for computing the 1-error linear complexity and locating the error positions for 2n-periodic binary sequences. © Springer-Verlag Berlin Heidelberg 2006.