The k-error linear complexity distribution for 2n-periodic binary sequences

Abstract

The linear complexity and the k-error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, we investigate the k-error linear complexity distribution of 2 n-periodic binary sequences in this paper based on Games–Chan algorithm. First, for k=2,3, the complete counting functions for the k-error linear complexity of 2 n-periodic binary sequences (with linear complexity less than 2n) are characterized. Second, for k=3,4, the complete counting functions for the k-error linear complexity of 2 n-periodic binary sequences with linear complexity 2n are presented. Third, as a consequence of these results, the counting functions for the number of 2 n-periodic binary sequences with the k-error linear complexity for k=2 and 3 are obtained.