Abstract

In this paper coding theory is used to study complexity of periodic sequences. We consider sequences of period n=2ml and use the correspondence between periodic sequences and vectors to define the complexity of vectors and give alternative expressions for the linear complexity of the sequences. We prove that the complexity of vectors of cyclic subsets of Vn is constant but that of an element of a cyclic subspace is only upperbounded and the only cyclic subspaces of constant linear complexity are minimal cyclic codes. An important result of this approach is a generalisation of Rueppel's result on the decomposition of sequences. We prove that a periodic sequence of period n=2k+l can always be decomposed into basic linear feedback shift register (LFSR) generated sequences whose length and feedback polynomials are obtained from irreducible factors of x +1. Extension of the results on the complexity structure of V.,n., to this general case follows from this theorem.