Bounds on the Linear Complexity and the 1-Error Linear Complexity over F_p of M-ary Sidel'nikov Sequences

摘要

In this paper we derive a lower bound on the linear complexity and an upper bound on the 1-error linear complexity over F_p of M-ary Sidel'nikov sequences of period p~m - 1 when M ≥ 3 and p ≡ ±1 mod M. In particular, we exactly compute the 1-error linear complexity of ternary Sidel'nikov sequences when p ≡ - 1 mod 3 and m ≥ 4. Furthermore, we give a tighter lower bound on the linear complexity of ternary and quaternary Sidel'nikov sequences for p ≡ -1 mod M by a more detailed analysis. Based on these results, we present the ratios of the linear complexity and the 1-error linear complexity to the period asymptotically.