Among the many characteristics and classifications of discrete-time systems, two of particular importance are linearity and time-invariance [LINKS]. If a system happens to exhibit
both of these qualities, then it is referred to as being an
LTI system (linear time-invariant). These systems are very significant in the study of signal processing, for reasons that will be clear when the concept of the system impulse response is considered.
Consider the systems below. Which are LTI?
Identity: $y[n] = x[n]$
Scaling: $y[n] = 2\, x[n]$
Offset: $y[n] = x[n]+2$
Square signal: $y[n] = (x[n])^2$
Shift: $y[n] = x[n+m]\quad m\in Z$
\]
Decimate: $y[n] = x[2n]$
Square time: $y[n] = x[n^2]$
Moving average (combines shift, sum, scale): $y[n] = \frac{1}{2}(x[n]+x[n-1])$
Recursive average: $y[n] = x[n]+ \alpha\,y[n-1]$
Identity: $y[n] = x[n]$
LTI
Scaling: $y[n] = 2\, x[n]$
LTI
Offset: $y[n] = x[n]+2$
not LTI (time-invariant, but not linear)
Square signal: $y[n] = (x[n])^2$
not LTI (time-invariant, but not linear)
Shift: $y[n] = x[n+m]\quad m\in Z$
LTI
Decimate: $y[n] = x[2n]$
not LTI (linear, but not time-invariant)
Square time: $y[n] = x[n^2]$
not LTI (time-invariant, but not linear)
Moving average (combines shift, sum, scale): $y[n] = \frac{1}{2}(x[n]+x[n-1])$
LTI
We recall that linear systems can be expressed through a matrix multiplication. Suppose that a system is linear; any output $y$ can be expressed as the multiplication of an infinite-dimensional matrix $H$ with the input $x$:
$y ~=~ {\bf H} \, xy[n] ~=~ \sum_m \: [{\bf H}]_{n,m} \, x[m]
$
Now if a linear system is also time-invariant, it turns out the matrix $H$ will have an interesting structure. To see this, we will first express the matrix multiplication in a summation notation, where $h_{n,m} ~=~ [{\bf H}]_{n,m}$ represents the row-$n$, column-$m$ entry of the matrix $\bf H$:$
y[n]~=~ {\cal H}\{ x[n]\} ~=~ \sum_{m=-\infty}^{\infty} h_{n,m} \, x[m], \quad -\infty \lt n \lt \infty
$Supposing the system $H$ is time-invariant, we have:
${\cal H}\{ x[n-q]\} ~=~ \sum_{m=-\infty}^{\infty} h_{n,m} \, x[m-q] ~=~ y[n-q]$
If we apply a simple change of variables ($n' = n-q$ and $m' = m-q$), we then have:${\cal H}\{ x[n']\} ~=~ \sum_{m'=-\infty}^{\infty} h_{n'+q,m'+q} \, x[m']~=~ y[n']$If we compare this final equation with the original one, we see that for an LTI
$h_{n,m} ~=~ h_{n+q,m+q} \quad \forall\: q\in\Integers$
So for LTI systems, the matrix $H$ that defines the system's input/output relationship has a special structure: $h_{n,m} ~=~ h_{n+q,m+q} \quad \forall\: q\in\Integers$ (where $h_{n,m}$ is the value at the nth row and mth column of the matrix $H$). Such matrices are called
Toeplitz Matrices . They have identical values along their diagonals:
Because of that property, all of the information in the matrix is contained in a single row, or column. We'll call the 0th row $h[n]$: $h[n]= h_{n,0}$:
Below is an example of a pictorial representation of a Toeplitz matrix. Note how the diagonals are all the same color:
CAPTION.
Matrix structure of lti systems (finite-length)
For systems operating on finite-length signals, we can apply similar analysis. Linear systems can be expressed as a matrix multiplication $y=Hx$, here shown using summation notation:
$y[n]~=~ {\cal H}\{ x[n]\} ~=~ \sum_{m=0}^{N-1} h_{n,m} \, x[m], \quad 0\leq n \leq N-1$
If we enforce time-invariance on such a system, we then have:${\cal H}\{ x[(n-q)_N]\} ~=~ \sum_{m=0}^{N-1} h_{n,m} \, x[(m-q)_N]~=~ y[(n-q)_N]$A change of variables ($n' = n-q$) then yields:
${\cal H}\{ x[(n')_N]\} ~=~ \sum_{m'=-q}^{M-1-q} h_{(n'+q)_N,(m'+q)_N} \, x[(m')_N] ~=~ y[(n')_N]$
We see, then, that for LTI finite-length systems, $h_{n,m} ~=~ h_{(n+q)_N,(m+q)_N} \quad \forall\: q\in\Integers$. This is similar to the Toeplitz structure for infinite-length systems, but note the circular shifts, how the rows "wrap" around the edges of the matrix:
As with the Toeplitz matrices, all of the information in a circulant matrix is contained in a single row or column, the other rows/columns simply being shifted versions of the original. So we can call the N-length signal $h[n]$ the 0th column of the matrix, and express the whole matrix in terms of it:
Below is a pictorial representation of a circulant matrix. Like Toeplitz matrices, the values along diagonals are equivalent, but in addition to having this property, the values "wrap around" the matrix boundaries:
