New Results on Periodic Sequences With Large $k$-Error Linear Complexity
Honggang Hu, Guang Gong, Dengguo Feng · IEEE Transactions on Information Theory · 2009
Niederreiter showed that there is a class of periodic sequences which possess large linear complexity and largek-error linear complexity simultaneously. This result disproved the conjecture that there exists a trade-off between the linear complexity and thek-error linear complexity of a periodic sequence by Ding By considering the orders of the divisors ofxN-1 over\BBFq, we obtain three main results which hold for much largerkthan those of Niederreiter : a) sequences with maximal linear complexity and almost maximalk-error linear complexity with general periods; b) sequences with maximal linear complexity and maximalk-error linear complexity with special periods; c) sequences with maximal linear complexity and almost maximalk-error linear complexity in the asymptotic case with composite periods. Besides, we also construct some periodic sequences with low correlation and largek-error linear complexity.