On the k-error linear complexity of sequences with period 2pn over GF(q)

In this paper, we first optimize the structure of the Wei–Xiao–Chen algorithm for the linear complexity of sequences over GF(q) with period N =  2p ⁿ , where p and q are odd primes, and q is a primitive root modulo p ². The second, an union cost is proposed, so that an efficient algorithm for computing the k-error linear complexity of a sequence with period 2p ⁿ over GF(q) is derived, where p and q are odd primes, and q is a primitive root modulo p ². The third, we give a validity of the proposed algorithm, and also prove that there exists an error sequence e ^N , where the Hamming weight of e ^N is not greater than k, such that the linear complexity of (s + e) ^N reaches the k-error linear complexity c. We also present a numerical example to illustrate the algorithm. Finally, we present the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.