How many bits have to be changed to decrease the linear complexity?

Abstract

The k-error linear complexity of periodic binary sequences is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. For the period length p n, where p is an odd prime and 2 is a primitive root modulo p 2, we show a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity. Moreover, we describe an algorithm to determine the k-error linear complexity of a given p n-periodic binary sequence.