The Characterization of 2~n-Periodic Binary Sequences with Fixed 1-Error Linear Complexity

摘要

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 2~n-periodic binary sequences. In this paper, we study the linear complexity and the 1-error linear complexity of 2~n-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 2~n-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 2~n-periodic binary sequences. Finally, we give new fast algorithms for computing the 1-error linear complexity and locating the error positions for 2~n-periodic binary sequences.