This jupyter notebook is part of a collection of notebooks on various topics of Digital Signal Processing. Please direct questions and suggestions to Sascha.Spors@uni-rostock.de.
Computing the output $y[k] = \mathcal{H} \{ x[k] \}$ of a linear time-invariant (LTI) system is of central importance in digital signal processing. This is often referred to as filtering of the input signal $x[k]$. The methods for this purpose are typically classified into
techniques. This section focuses on the realization of non-recursive filters.
An LTI system can be characterized completely by its impulse response $h[k]$
The output signal $y[k]$ is given by (linear) convolution of the input signal $x[k]$ with the impulse response $h[k]$
\begin{equation} y[k] = x[k] * h[k] = \sum_{\kappa = -\infty}^{\infty} x[\kappa] \; h[k-\kappa] \end{equation}Two aspects of this representation become evident when inspecting above equation:
The output signal $y[k]$ is a linear combination of the input signal $x[k]$. There is no feedback of the output signal of past time-instants. Therefore, such filters are termed as non-recursive filters.
In order to compute the output signal at one particular time-instant $k$, the input signal needs to be known for all past and future time-instants.
The second aspect prohibits a practical realization. In order to be able to realize a non-recursive filter by convolution, the output at time-instant $k$ should only depend on the input signal $x[k]$ up to time-index $k$
\begin{equation} y[k] = \sum_{\kappa = -\infty}^{k} x[\kappa] \; h[k-\kappa] \end{equation}This is the case when the impulse response is causal, hence when $h[k] = 0$ for $k<0$. However, this still requires knowledge of the input signal for all past time-instants. If we further assume that the input signal is causal, $x[k] = 0$ for $k<0$, we get
\begin{equation} y[k] = \sum_{\kappa = 0}^{k} x[\kappa] \; h[k-\kappa] \end{equation}Many practical systems have an impulse response of finite length $N$ or can be approximated by an impulse response of finite length
\begin{equation} h_N[k] = \begin{cases} h[k] & \text{ for } 0 \leq k < N \\ 0 & \text{ otherwise} \end{cases} \end{equation}Such an impulse response is denoted as finite impulse response (FIR). Introducing $h_N[k]$ into above sum and rearranging terms yields
\begin{equation} y[k] = \sum_{\kappa = 0}^{k} x[\kappa] \; h_N[k-\kappa] = \sum_{\kappa = 0}^{N-1} h_N[\kappa] \; x[k-\kappa] \end{equation}Hence for a causal input signal $x[k]$ and a FIR the output of the system can be computed by a finite number of operations.
The evaluation of the convolution for a FIR of length $N$ requires $N$ multiplications and $N-1$ additions per time index $k$. For the real-time convolution of an audio signal with a sampling rate of $f_\text{S} = 48$ kHz with a FIR of length $N = 48000$ we have to compute around $2 \times 2.3 \cdot 10^9$ numerical operations per second. This is a considerable numerical complexity, especially on embedded or mobile platforms. Therefore, various techniques have been developed to lower the computational complexity.
Copyright
This notebook is provided as Open Educational Resource. Feel free to use the notebook for your own purposes. The text is licensed under Creative Commons Attribution 4.0, the code of the IPython examples under the MIT license. Please attribute the work as follows: Sascha Spors, Digital Signal Processing - Lecture notes featuring computational examples.