MAXIMUM ORDER COMPLEXITY FOR THE MINIMUM CHANGES OF AN M-SEQUENCE

The maximum order complexity (MOC) of a sequence is a very natural gen eralization of the well-known linear complexity (LC) by allowing nonli near feedback functions for the feedback shift register which generate s a given sequence. It is expected that MOC is effective to reduce suc h an instability of LC as an extreme increase caused by the minimum ch anges of a periodic sequence, i.e., one-symbol substitution, one-symbo l insertion or one-symbol deletion per each period. In this paper we w ill give the bounds (lower and upper bounds) of MOC for the minimum ch anges of an m-sequence over GF(q) with period q(n) - 1, which shows th at MOC is much more natural than LC as a measure for the randomness of sequences in this case.