Linear time invariant

Screencast video [⯈]

The FIR filter, as described in the previous sections, belongs to a general class of systems that is used very often in practice: The so called Linear Time Invariant (LTI) systems. In the first subsections the definitions Linearity and Time Invariance are given. In the last subsection it will be shown that the convolution sum operator is a result of LTI.

In this section the new symbol $x\left[n\right]\mapsto y\left[n\right]$ will be used with the following interpretation: The system maps the sequence of input signal samples $x\left[n\right]$ to the sequence of output signal samples $y\left[n\right]$.

Linear systems

When a system results into the following mappings: $x_1\left[n\right]\mapsto y_1\left[n\right]$ and $x_2\left[n\right]\mapsto y_2\left[n\right]$, then such a system is Linear if for any linear combination of input sequences $x_1\left[n\right]$ and $x_2\left[n\right]$ the system maps this linear combination to the same linear combination of output sequences $y_1\left[n\right]$ and $y_2\left[n\right]$. With scalars $\alpha$ and $\beta$, this definition can mathematically be described as follows: $$x\left[n\right]=\alpha x_1\left[n\right]+\beta x_2\left[n\right]\mapsto y\left[n\right]=\alpha y_1\left[n\right]+\beta y_2\left[n\right]$$ A visualisation of this definition is depicted in Fig. 1.

Time Invariant systems

When a system results into the following mapping: $x\left[n\right]\mapsto y\left[n\right]$ then a system is Time Invariant if a delayed sequence of input samples $x[n-n_0]$ is mapped by the system to a sequence of output samples $y[n-n_0]$, which is delayed by the same amount of samples. With integer delay $n_0$, this definition can mathematically be described as follows: $$x\left[n\right]\mapsto y\left[n\right]\Rightarrow x[n-n_0]\mapsto y[n-n_0]$$ A visualisation of this definition is depicted in Fig. 2.

Convolution sum as result of LTI

When a system is LTI then the sequence of output samples $y\left[n\right]$ can be expressed as a convolution sum of the sequence of input samples $x\left[n\right]$ with the impulse response $h\left[n\right]$ of the LTI system, thus $y\left[n\right]=x\left[n\right]\star h\left[n\right]$. The proof of this property is as follows: $$\begin{array}{ccc}\delta \left[n\right]\mapsto h\left[n\right]& \Rightarrow & \delta [n-k]\stackrel{\text{TI}}{\mapsto }h[n-k]\text{for any}k\\ & \Rightarrow & x\left[k\right]\delta [n-k]\stackrel{\text{L}}{\mapsto }x\left[k\right]h[n-k]\text{for any}k\\ & \Rightarrow & \sum _{k}x\left[k\right]\delta [n-k]\stackrel{\text{L}}{\mapsto }y\left[n\right]=\sum _{k}x\left[k\right]h[n-k]=x\left[n\right]\star h\left[n\right]\end{array}$$ Note that in general for an LTI system the summation index $k$ of the convolution sum runs from $k=-\infty$ to $k=+\infty$, while for an FIR filter this range is automatically limited because of the finite length of the impulse response.

Cascading LTI systems

In the first subsection it is shown that the convolution sum operator has the commutative property. As a result it is sown in the next subsection that the cascading of two LTI systems can be combined to one LTI system, while above that the order of the cascaded LTI systems can be interchanged.

Commutative property convolution sum operator

The convolution sum operator is a commutative operation. This implies that the result $y\left[n\right]$ of the convolution sum operator can be obtained by either convolving $h\left[n\right]$ by $x\left[n\right]$ or the other way around: $$y\left[n\right]=h\left[n\right]\star x\left[n\right]=x\left[n\right]\star h\left[n\right]$$ Proof: $$\begin{array}{ccc}y\left[n\right]& =& h\left[n\right]\star x\left[n\right]=\sum _{k=-\infty }^{\infty }h\left[k\right]x[n-k]\\ & \stackrel{p=n-k}{=}& \sum _{p=+\infty }^{-\infty }h[n-p]x\left[p\right]=\sum _{p=-\infty }^{\infty }x\left[p\right]h[n-p]=x\left[n\right]\star h\left[n\right]\end{array}$$

Note that for an FIR filter the range of the convolution sum is automatically limited by the finite length of the impulse response. Thus in case of an FIR filter the commutative property of the convolution sum operator results on the one hand into: $$y\left[n\right]=h\left[n\right]\star x\left[n\right]=\sum _{k=-\infty }^{\infty }h\left[k\right]x[n-k]\stackrel{\text{FIR}}{=}\sum _{k=0}^{M-1}h\left[k\right]x[n-k]$$ where we used the fact that $h\left[n\right]=0$ for $n<0$ and $n>M$. On the other hand we have: $$y\left[n\right]=x\left[n\right]\star h\left[n\right]=\sum _{k=-\infty }^{\infty }x\left[k\right]h[n-k]\stackrel{\text{FIR}}{=}\sum _{k=n-(M-1)}^{n}x\left[k\right]h[n-k]$$ where we used the finite length of an FIR as follows: $$h[n-k]=0\text{for}\{\begin{array}{c}n-k<0\Rightarrow k>n\\ n-k>M\Rightarrow k<n-M\end{array}$$

Cascade equivalences

The upper left hand figure of Fig. 3 shows the cascading of two LTI systems, one with impulse response $h_1\left[n\right]$ and the other one with impulse response $h_2\left[n\right]$. When applying a delta pulse $\delta \left[n\right]$ to the first LTI system, the output equals the impulse response $h_1\left[n\right]$. When applying this sequence to the second LTI system, the result is the convolution sum result $h_1\left[n\right]\star h_2\left[n\right]$.

The lower left hand figure shows one LTI system with impulse response $h\left[n\right]=h_1\left[n\right]\star h_2\left[n\right]$. When applying a delta pulse $\delta \left[n\right]$ to this system the result is the same as above.

Finally it follows from the commutative property of the convolution sum operator that: $$h\left[n\right]=h_1\left[n\right]\star h_2\left[n\right]=h_2\left[n\right]\star h_1\left[n\right]$$ which is shown in the lower right part of Fig. 3. This combined impulse response can be split again into the cascading of two LTI systems, as shown in the upper right figure. In this last step however the LTI systems with impulse response $h_1\left[n\right]$ and $h_2\left[n\right]$ have interchanged from order.