A relationship between linear complexity and k-error linear complexity
Kaoru Kurosawa, Fumio Sato, T. Sakata, Wataru Kishimoto · IEEE Transactions on Information Theory · 2000
Linear complexity is an important cryptographic criterion of stream ciphers. The k-error linear complexity of a periodic sequence of period N is defined as the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. This article shows 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.