Lower bounds on error complexity measures for periodic LFSR and FCSR sequences

Non-trivial lower bounds on the linear complexity are derived for a sequence obtained by performing a combination of up to k substitutions, insertions, and deletions. The bounds derived are similar to those previously established for either k substitutions, k insertions or k deletions within a single period. The bounds are useful when T/2k < λ < T/k, where λ is the linear complexity of the original sequence and T is its period. It is shown that similar bounds hold for the joint linear complexity of periodic multisequences. Similar results are obtained for the N-adic complexity of periodic sequences over {0,... , N - 1}. New non-trivial lower bounds on the minimum number of operations needed to decrease the complexity are also given. The derivations are simpler compared to those in previous work on these problems.