On the Linear Complexity of Sequences Obtained by State Space Generators

摘要

Binary sequences generated from finite state automata are studied in this correspondence by utilizing system theoretic concepts. We develop a new unified approach for analyzing the linear complexity of such sequences, via controllability and observability conditions. A vectorial trace representation of sequences with arbitrary period is provided, which leads to a new generalized discrete Fourier transform allowing the generation of sequences with prescribed linear complexity. Furthermore, we introduce new classes of nonlinear filters, using the proposed approach, which generalize currently known classes and guarantee the same lower bound on the linear complexity.