New Results on Periodic Sequences With Large k-Error Linear Complexity

Niederreiter showed that there is a class of periodic sequences which possess large linear complexity and large k-error linear complexity simultaneously. This result disproved the conjecture that there exists a trade-off between the linear complexity and the k-error linear complexity of a periodic sequence by Ding et al. By considering the orders of the divisors of x(N)-1 over F-q, we obtain three main results which hold for much larger k than those of Niederreiter et al.: a) sequences with maximal linear complexity and almost maximal k-error linear complexity with general periods; b) sequences with maximal linear complexity and maximal k-error linear complexity with special periods; c) sequences with maximal linear complexity and almost maximal k-error linear complexity in the asymptotic case with composite periods. Besides, we also construct some periodic sequences with low correlation and large k-error linear complexity.