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
- Recursive average: $y[n] = x[n]+ \alpha\,y[n-1]$ LTI
Matrix structure of lti systems (infinite-length)
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: