This mostly tutorial presentation will review the definition of the linear complexity of a sequence over a field or a commutative ring, give an elementary proof that the linear complexity is the smallest dimension of a single-output linear system that can produce the sequence as its zero-input response, present a simple necessary and sufficient condition for the existence of a generalized discrete Fourier Transform of a prescribed length N, and show the connection between the linear complexity of a periodic sequence and the generalized Discrete Fourier Transform of its first period.

Back to Codes, Systems and Graphical Models