Z transform Let $x=\lbrace x_n\rbrace_{n\in\mathbb{Z}}$ be a numerical signal (i.e. a sequence). The $z$ transform of $s$ is the series $$ X(z) = \sum_{n=-\infty}^{+\infty} x_nz^{-n},\ z\in\mathbb{CC} $$ defined in a crown of convergence $r_1<|z|< r_2$ .
Causality and disk of convergency A signal $x[n]$ is causal if its $z$ transform $X(z)$ is defined outside of a disk of radius $r_1$, ie if $r_2 = +\infty$. Likewise, $x$ is anti-causal if $r_1=0$, ie. if $X(z)$ is defined inside of a disk of radius $r_2$.
Stability Let $x[n]$ be a numerical signal and $X(z)$ its Z transform defined on $r_1<|z|< r_2$. x is stable iff the unit disk is inside the region of convergence, i.e. $X(z)$ is defined for all $z$ such that $|z|=1$.
If $|z|=1$, we can write $z=e^{i2\pi\nu}$. If the signal $x$ is stable, then its Fourier transform $\hat x$ exists and $$ \hat x(\nu) = X(e^{i2\pi\nu}) $$ The converse is true: if the Fourier transform exists, then the signal is stable.
Propeties Let $x$ a numerical signal and $\mathcal{Z} (x_n) = X(z)$ its $z$ transform. The $z$ transform is linear Translation: $\mathcal{Z}(x_{n-k}) = z^{-k} X(z)$ Scaling change $\mathcal{Z}(a^n x_n) = X(\frac{z}{a})$ Derivation: $\mathcal{Z}(n^kx_n)) = \left(-z\frac{\mathrm{d} }{\mathrm{d}z}\right)^k X(z)$ Convolution: $\mathcal{Z}(x*y)(z) = X(z)Y(z)$ Link with the Discrete Time Fourier transform: $\hat x(\nu) = X(e^{i2\pi \nu})$ only if $r_1 < 1 < r_2$ ! Otherwise the TFD is not defined.
Let a discrete filter with an impulse response $h$. Then, if $y$ is the response of the system with the input $x$, we have $$ y[n] = (h\star x) [n] = \sum_{k=-\infty}^{+\infty} h[k] x[n-k] $$ By taking the Z-transform, we get $$ Y(z) = H(z)X(z) $$ H is called the transfert function of the system.
transfert function The transfer function of a numerical filter is the $z$ transform of its impulse response. For a filter with impulse response $h$, we denote its transfer function by $H(z)$.
If the system and the input are stable , we can write: $$ Y(e^{i2\pi\nu}) = H(e^{i2\pi\nu})X(e^{i2\pi\nu}) $$ i.e. $$ \hat y(\nu) = \hat h(\nu)\hat x(\nu) $$ $\hat h$, the Fourier transform of the impulse response, is called the complex gain of the system. The spectrum of the impulse response $|\hat h|^2$ is called the frequency response of the system.
Ideal filters allow one to vanish some frequencies of the input signal.
The complex gain of an ideal discret time low pass filter is given by $$ \hat h_{\nu_0}^{Low}(\nu) = \begin{cases} 1 & \text{ if } |\nu| < \nu_0 \\ 0 & \text{ otherwise}\end{cases} $$ where $0\leq \nu_0 \leq 1$ is the cutting frequency of the filter: all the high frequencies above are vanished in the filtered signal by the ideal low pass filter.
The impulse response of this filter is given by taking the invert Fourier transform: $$ \begin{aligned} h_{\nu_0}^{Low}[n] & = \int_{-\frac{1}{2}}^{\frac{1}{2}} \hat h(\nu) e^{i2\pi\nu n} \mathrm{d}\nu\\ &= \int_{-\nu_0}^{\nu_0} e^{i2\pi\nu n} \mathrm{d}\nu \\& = \frac{\sin[2\pi\nu_0 n]}{\pi n}\\ & = 2\nu_0\text{sinc}[2\nu_0 n] \end{aligned} $$ This filter is then clearly not causal, and is then not realizable.
The complex gain of an ideal discret time high pass filter is given by $$ \hat h_{\nu_0}^{High}(\nu) = \begin{cases} 1 & \text{ if } |\nu| > \nu_0 \\ 0 & \text{ otherwise}\end{cases} $$ where $0\leq \nu_0 \leq 1$ is the cutting frequency of the filter: all the low frequencies below $\nu_0$ are vanished in the filtered signal by the ideal high pass filter.
The ideal high pass filter with the cutting frequency $\nu_0$ can be written in function of the ideal low pass filter with he cutting frequency $\nu_0$: $$ \hat h_{\nu_0}^{High}(\nu) = 1 - \hat h_{\nu_0}^{Low}(\nu) $$
In the discret time case, the complex gain of the high pass filter can be inverted to recover the numerical impulse response.
By remarking that we have $$ \int_{-\frac{1}{2}}^{\frac{1}{2}} e^{i2\pi\nu n}\mathrm{d}\nu = \delta[n] $$ then $$ h_{\nu_0}^{High}[n] = \delta[n] - 2\nu_0\text{sinc}[2\nu_0 n] $$
The complex gain of an ideal discret time band pass filter is given by $$ \hat h_{[\nu_0,\nu_1]}^{Band}(\nu) = \begin{cases} 1 & \text{ if } \nu_0 < |\nu| < \nu_1 \\ 0 & \text{ otherwise}\end{cases} $$ where $0\leq \nu_0\leq 1$ and $0\leq \nu_1\leq 1$ are the two cutting frequencies of the filter: all the low frequencies below $\nu_0$ and above $\nu_1$ are vanished in the filtered signal by the ideal band pass filter.
The ideal band pass filter can be expressed as the difference of two ideal low pass filters with cutting frequencies $\nu_0$ and $\nu_1$: $$ \hat h_{[\nu_0,\nu_1]}^{Band}(\nu) = \hat h_{\nu_1}^{Low}(\nu) - \hat h_{\nu_0}^{Low}(\nu) $$
The complex gain of an ideal discret time band cut filter is given by $$ \hat h_{[\nu_0,\nu_1]}^{Cut}(\nu) = \begin{cases} 0 & \text{ if } \nu_0 < |\nu| < \nu_1 \\ 1 & \text{ otherwise}\end{cases} $$ where $\nu_0$ and $\nu_1$ are the two cutting frequencies of the filter: all the low frequencies between $\nu_0$ and $\nu_1$ are vanished in the filtered signal by the ideal band pass filter.
The ideal band cut filter can be expressed as the difference of two ideal low pass filters with cutting frequencies $\nu_0$ and $\nu_1$: $$ \hat h_{[\nu_0,\nu_1]}^{Cut}(\nu) = \hat h_{\nu_0}^{Low}(\nu) - \hat h_{\nu_1}^{Low}(\nu) $$
FIR Filter Let a filter with an impulse response $h$. The filter is said to be with a “Finite impulse response” (FIR) if $h$ is finite: $h={h_{-k_1},\ldots,h_0,\ldots,h_{k_2}}$ The filtering equation can then be written: $$ y[n] = \sum_{k=-k_1}^{k_2} h[k] x[n-k] $$ The _order_ of the filter is the number of samples of its impulse response.
A few remarks
A FIR filter is necessary stable A FIR filter is not necessary causal A FIR filter is realizable iff it is causal.
Let an ideal filter with an impulse response $h^{\text{ideal}}$ (unknown) defined thanks to its transfer function $H^{\text{ideal}}$. It can be approximated by a realizable FIR filter of order $N+1$ by the following:
While this approach is simple, the main shortcomming is that the truncation (i.e. the multiplication by a rectangular window) make appears a Gibbs phenomenon. A solution is to apply a “smooth” window to avoid hard truncation, responsible of the Gibbs phenomenon. The previous algorithm becomes:
We present next some classical windows with their spectrum
Bartlett (or triangular) $$ w[n] = \begin{cases} \frac{2}{N-1} & 0\leq n \leq \frac{N-1}{2}\\ 2 - \frac{2n}{N-1} & \frac{N-1}{2} \leq n \leq N-1\\ 0 & \text{otherwise}\end{cases} $$
Hann
$$ w[n] = \begin{cases} 0.5 - 0.5\cos\left(\frac{2\pi n}{N-1}\right) & 0 \leq n \leq N-1 \\ 0 & \text{otherwise}\end{cases} $$
Hamming
$$ w[n] = \begin{cases} 0.54 - 0.46\cos\left(\frac{2\pi n}{N-1}\right) & 0 \leq n \leq N-1 \\ 0 & \text{otherwise}\end{cases} $$
Blackman
$$ w(n) = \begin{cases} 0.42 - 0.5\cos\left(\frac{2\pi n}{N-1}\right) + 0.08\cos\left(\frac{4\pi n}{N-1}\right) & 0 \leq n \leq N-1 \\ 0 & \text{otherwise}\end{cases} $$
Let an approximation of an ideal low pass filter by a FIR filter $$ y[n] = \sum_{k=-\infty}^{+\infty} h^{ideal}[k] x[n-k] \simeq \sum_{k=0}^{K-1} h^{FIR}[k] x[n-k] $$ The impulse response of the ideal low pass filter is $$ h^{ideal}[n] = \frac{\sin(2\pi\xi_0 n)}{\pi n}\ . $$ The coefficients of such an ideal filter decrease in $\matchal{O}(\frac{1}{N}). Then, for an error in order of $10^{-6}$, we need one million coefficients. In such a case, we need ten billion of operations per second to process a speech signal sampled at 10 kHz.
The filtering equation with an infinite impulse response causal filter reads $$ y[n] = \sum_{k=0}^{+\infty} h[n]x[n-k] $$ The main idea to overcome the previous limitation is to use recursive filters. We look for $y$ like
$$ y[n] = \sum_{k=0}^M b[k] x[n-k] - \sum_{k=1}^N a[k] y[n-k] $$
A few remarks:
- The output coefficient $y[n]$ depends of the previous (already computed) ones !
- The coefficient $y[n]$ is obtained by filtering of $\mathbf{x[m]}$ with $m\leq n$ and filtering of $\mathbf{y[m]}$ with $m\leq n$ by using {\bf two} FIR filters of impulse response $\lbrace b[0],\ldots,b[M]\rbrace$ and $\lbrace a[1],\ldots,a[N]\rbrace$.
- If this equation has a unique solution, then it is a recursive filter.
- We suppose that $M\leq N$. $N$ is called the order of the filter.
The filtering equation can be rewritten, with $a[0] = 1$ $$ \begin{aligned} y[n] & = \sum_{k=0}^M b[k] x[n-k] - \sum_{k=1}^N a[k] y[n-k] \\ \Leftrightarrow \sum_{k=0}^N a[k] y[n-k] & = \sum_{k=0}^M b[k] x[n-k] \end{aligned} $$ By taking the Z-transform, we get $$ \begin{aligned} Y(z) \left( \sum_{k=0}^N a[k] z^{-k}\right) &= X(z) \left( \sum_{k=0}^M b[k] z^{-k}\right) \\ \Leftrightarrow Y(z) &= H(z) X(z)\ . \end{aligned} $$ with $$ H(z) = \frac{\sum_{k=0}^M b[k] z^{-k}}{\sum_{k=0}^N a[k] z^{-k}}\ . $$ the transfert function of the filter. This transfert function is a _rational fraction_. The filter exists iff *the denominator never vanish*
Thanks to the transfert function $H$, we can say that
Synthesis of IIR filters is a bit more complex than FIR filters. The main steps are
The template will obey some specifications
In practice, it is convenient to choose an IIR filter in the folowing families. For each family, we give its frequency response and its main characteristics/parameters.
$$ \left| H(\nu)\right|^2 = \frac{1}{1+\left(\frac{\nu}{\nu_c}\right)^{2N}} $$
Main characteristics:
$$ \left| H(\nu)\right|^2 = \frac{1}{1+\varepsilon^2T_N^2\left(\frac{\nu}{\nu_p}\right)} $$ with $T_N$ Tchebychev polynomial of degree $N$
Main characteristics:
$$ \left| H(\nu)\right|^2 =1- \frac{1}{1+\varepsilon^2T_N^2\left(\frac{\nu_s}{\nu}\right)} $$
Main characteristics:
$$ \left| H(\nu)\right|^2 =1- \frac{1}{1+\varepsilon^2R_N^2\left(\frac{\nu}{\sqrt{\nu_p\nu_s}}\right)} $$
Main characteristics:
Properties of the FIR filters:
Properties of the IIR filters: