Linear complexity of a sequence obtained from a periodic sequence by either substituting, inserting, or deleting k symbols within one period

Abstract

A unified derivation of the bounds of the linear complexity is given for a sequence obtained from a periodic sequence over GF(q) by either substituting, inserting, or deleting k symbols within one period. The lower bounds are useful in case of n<N/k, where N and n are the period and the linear complexity of the sequence, respectively. It is shown that all three different cases can be treated very simply in a unified manner. The bounds are useful enough to show how wide the distribution of the linear complexity becomes as k increases, although they are not always tight because their derivations do not use the information about the change values.