Skip to main content
placeholder image

On the complexity structure of binary sequences of odd length

Conference Paper


Abstract


  • In this paper coding theory is used to study complexity of periodic sequences. We consider sequences of period n=2m-l 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.

Publication Date


  • 1991

Citation


  • Safavi-Naini, R., & Seberry, J. (1991). On the complexity structure of binary sequences of odd length. In IEEE International Symposium on Information Theory - Proceedings (pp. 122). doi:10.1109/ISIT.1991.695178

Scopus Eid


  • 2-s2.0-85067462968

Web Of Science Accession Number


Start Page


  • 122

Abstract


  • In this paper coding theory is used to study complexity of periodic sequences. We consider sequences of period n=2m-l 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.

Publication Date


  • 1991

Citation


  • Safavi-Naini, R., & Seberry, J. (1991). On the complexity structure of binary sequences of odd length. In IEEE International Symposium on Information Theory - Proceedings (pp. 122). doi:10.1109/ISIT.1991.695178

Scopus Eid


  • 2-s2.0-85067462968

Web Of Science Accession Number


Start Page


  • 122