Abstract: The k-error linear complexity of a periodic sequence is defined as the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. k-error linear complexity profile of a sequenes is the ordered list of k-error linear complexities. The index reveals how the linear complexity of the sequence varies as an increasing number of the bits of the sequence are changed. A fast algorithm is presented for determining k-error linear complexity profile of a q-ary sequence with a period pⁿ, where p, q is an odd prime and q is a primitive root modulo p². The algorithm generalizes both the Xiao, Wei, Lam, Imamura and Weik Dong, Xiao algorithms, which compute the linear complexity and k-error linear complexity of a q-ary sequence of a period pⁿ, respectively. The algorithm we present computes the k-error linear complexity profile for the q-ary sequence of a period pⁿ using at most Θ(2ⁿ⁺¹) steps.

Key words: period sequences, k-error linear complexity profile, fast algorithm