Bounds on the linear complexity and the 1-error linear complexity over F-p of M-ary Sidel'nikov sequences

Abstract

In this paper we derive a lower bound on the linear complexity and an upper bound on the I-error linear complexity over F-p of M-ary Sidel'nikov sequences of period p(m) - 1 when M >= 3 and p equivalent to +/- 1 mod M. In particular, we exactly compute the 1-error linear complexity of ternary Sidel'nikov sequences when p equivalent to -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 equivalent to -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.