New Results on the Linear Complexity of Binary Sequences

The complexity of binary sequences generated by state-space systems is studied in this paper via utilization of system theoretic concepts. Application of controllability and observability conditions lead to a new block-trace representation of binary sequences enabling the efficient generation of sequences with maximum period and linear complexity. These arguments are also used to study nonlinearly filtered m-sequences, resulting in a new type of filters that achieve the same lower bound for the linear complexity as Rueppel´s equidistant filters