Special structures

Screencast video [⯈]

Linear-phase filter

The most important property of a linear phase filter is that its phase response is linear proportional with the relative frequency $\theta$ plus a possible offset, as shown in the following equation: \begin{eqnarray*} H(e^{j\theta}) &=&|H(e^{j\theta})| \cdot e^{j\varphi \{ H(e^{j\theta}) \}} \newline \varphi \{ H(e^{j\theta}) \} &=& \color{red}{c} \cdot \theta + \color{blue}{\alpha} \cdot \frac{\pi}{2}\newline \text{with constant } \color{red}{c } &\text{ and }& \color{blue}{\alpha} \in \{ 0, \pm 1\}. \end{eqnarray*} A linear phase filter will preserve the waveform of the signal or component of the input signal to the extent that's possible, given that some frequencies will be changed in amplitude by the action of the filter. This could be important in several domains: For example in radar signal processing, where the wave shape of a returned radar signal might contain important information about the target's properties. It is also important in coherent signal processing and demodulation, where the wave shape is important because a thresholding decision must be made on the wave shape (possibly in quadrature space, and with many thresholds, e.g. 128 QAM modulation), in order to decide whether a received signal represented a “1” or “0”. Therefore, preserving or recovering the originally transmitted wave shape is of utmost importance, else wrong thresholding decisions will be made, which would represent a bit error in the communications system. Another example where linear phase is important is audio processing, where some believe (although many dispute the importance) that “time aligning” the different components of a complex wave shape is important for reproducing or maintaining subtle qualities of the listening experience (like the “stereo image”, and the like).

In the following subsections we will show the following properties of a linear phase filters:

• $\color{blue}{\text{Exact linear phase only with even/odd symmetry FIR:}}$
  In order for a causal system with a rational system function to have linear phase, exact linear phase can only be achieved with FIR filters. For an FIR filter with a real valued impulse response a sufficient condition for this filter to have linear phase is that the impulse response is either even-symmetric or odd-symmetric.
• $\color{blue}{\text{Only complex conjugated mirrored or on unit circle:}}$
  As a result of the symmetry property of the FIR filter, it follows that the zeros of the system function appear in complex conjugated mirrored pairs or complex conjugated on the unit circle.

Four different symmetries

In order for a causal system with rational system function to have linear phase, the impulse response must be finite in length. Therefore, IIR filters cannot have exact linear phase.

Assume the length $M$ FIR filter from which $h[n]$ is real valued and $h[0]$ is the first nonzero value of $h[n]$. A sufficient condition for this FIR filter to have a linear phase is that the impulse response is even-symmetric or odd-symmetric.

This implies that linear phase filters may be classified into four types depending on whether the impulse response is even- or odd-symmetric and whether the length $M$ is even or odd. For even-symmetry filters Type I has odd length and type II has even length filters, while for odd-symmetric filters type III has odd length and type IV has even length filters. A visual impression of the impulse responses of these four types is depicted in Fig. 1.

Frequency response of linear phase filters

In general the frequency response of a length $M$ FIR filter is given by the following equation: \begin{eqnarray*} h[n] = \sum_{k=0}^{M-1} h_k \delta[n-k] &\overset{\text{FTD}}{\circ \hspace{-1.3mm} - \hspace{-1.3mm} \circ} & H(e^{j\theta})= \sum_{k=0}^{M-1} h_k e^{-jk \theta} \end{eqnarray*} The frequency response expressions for each of the four linear filter types is as follows:

Even symmetry $h_k=h_{M-1-k}$; Odd $M$ $\Rightarrow$ $L=\frac{M-1}{2}$: \begin{eqnarray*} \color{red}{\textit{Type I}} &:& H_{I}(e^{j\theta}) =\left (h_L + 2\sum_{i=1}^{L} h_{L-i} \cos(i \cdot \theta) \right ) \cdot e^{-jL \cdot \theta} \end{eqnarray*} Even symmetry $h[=h_{M-1-k}$; Even $M$ $\Rightarrow$ $L=\frac{M}{2}$: \begin{eqnarray*} \color{red}{\textit{Type II}} &:& H_{II}(e^{j\theta}) =\left ( 2\sum_{i=1}^{L} h_{L-i} \cos((i - \frac{1}{2}) \cdot \theta) \right ) \cdot e^{-j(L- \frac{1}{2}) \cdot \theta} \end{eqnarray*} Odd symmetry $hk=-h-{M-1-k}$; Odd $M$ $\Rightarrow$ $L=\frac{M-1}{2}$: \begin{eqnarray*} \color{red}{\textit{Type III}} &:& H_{III}(e^{j\theta}) =\left (2\sum_{i=1}^{L} h_{L-i} \sin(i \cdot \theta) \right ) \cdot e^{-j(L \cdot \theta - \frac{\pi}{2}) } \end{eqnarray*} Odd symmetry $h_k=-h-{M-1-k}$; Even $M$ $\Rightarrow$ $L=\frac{M}{2}$: \begin{eqnarray*} \color{red}{\textit{Type IV}} &:& H_{IV}(e^{j\theta}) =\left ( 2 \sum_{i=1}^{L} h_{L-i} \sin((i-\frac{1}{2})\theta) \right ) \cdot e^{-j((L - \frac{1}{2}) \cdot \theta - \frac{\pi}{2})} \end{eqnarray*} Finally we have the following general expressions for the FIR frequency response $H(e^{j\theta})=\sum_{k=0}^{M-1} h_k e^{-jk \theta}$ evaluated at $\theta=0$ and $\theta=\pm \pi$ $$ H(e^{j0})=\sum_{k=0}^{M-1} h_k \hspace{2mm} \text{and} \hspace{2mm} H(e^{j\pm \pi})= \sum_{k=0}^{M-1} (-1)^k h_k $$ The frequencies $\theta=0$ and $\theta=\pm \pi$ deserve special attention. For example evaluating the Type III frequency response $H_{III}(e^{j\theta})$ for $\theta=0$ results in: \begin{eqnarray*} H_{III}(e^{j\theta})\vert_{\theta=0} &=& \sum_{k=0}^{M-1} h_k \overset{\text{odd } M}{=}0 \end{eqnarray*} In a similar way we can derive the following results:

Type	$\theta=0$	$\theta=\pm \pi$
I	-	-
II	-	$H_{II}(\text{e}^{\pm j \pi})=0$
III	$H_{III}(e^{j0})=0$	$H_{III}(\text{e}^{\pm j \pi})=0$
IV	$H_{IV}(e^{j0})=0$	-

In a follow up video we will use these zero crossings, or phase jumps of $\pi$, of the linear phase filters to design certain specific filter characteristics as denoted in the following table:

Type	Phase jump of $\pi$ at		Comment
	$\theta=0$	$\theta=\pm \pi$
I	-	-	-
II	-	Yes	No HPF possible
III	Yes	Yes	Only Bandpass possible
IV	Yes	-	No LPF possible

$Z$-transform of linear phase filters

In general the system function of a length $M$ FIR filter is given by the following equation: \begin{eqnarray*} h[n] = \sum_{k=0}^{M-1} h_k \delta[n-k] &\overset{\text{ZT}}{\circ \hspace{-1.3mm} - \hspace{-1.3mm} \circ} & H(z)= \sum_{k=0}^{M-1} h_k z^{-k} \end{eqnarray*} The symmetry in the coefficients of the impulse response of a linear phase FIR filter impose constraints on the system function $H(z)$. For even-symmetric Type I and Type II filters, thus with $h_k=h_{M-1-k}$, we have: \begin{eqnarray*} z^{-(M-1)}H(z^{-1})&=& z^{-(M-1)} \sum_{k=0}^{M-1}h_k z^{k} =\sum_{k=0}^{M-1} h_k z^{k-(M-1)}\newline &\overset{l=-k+M-1}{=} & \sum_{l=M-1}^{0} h_{M-1-l} z^{-l} \newline &\overset{h_{M-1-l}=h_l}{=}& \sum_{l=0}^{M-1} h_l z^{-l} = H(z). \end{eqnarray*} Thus for even-symmetric Type I and Type II filters we have the following property: \begin{equation}\label{Eq:Sym1} H(z)=z^{-(M-1)}H(z^{-1}) \end{equation} Similarly, for odd-symmetric filters Type III and Type IV filters, thus with $h_k=-h_{M-1-k}$, we have: \begin{equation}\label{Eq:Sym2} H(z)=-z^{-(M-1)}H(z^{-1}) \end{equation} From both equations (\ref{Eq:Sym1}) and (\ref{Eq:Sym2}) it follows that if the system function $H(z)$ of a linear phase filter is equal to zero for $z=z_0$, $H(z)$ must also be zero for $z=1/z_0$. Therefor the zeros occur in reciprocal pairs. Furthermore, in case of real coefficients, if $H(z)$ is equal to zero for $z=z_0$, $H(z)$ will also have a zero at $z=z^\ast_0$. Thus in general the zeros of the linear phase system $H(z)$ will appear in groups of four zeros in conjugate reciprocal pairs, $z_0, 1/z_0, z^\ast_0, 1/z^\ast_0$, as illustrated in Fig. 2.

This figure also shows some special cases when the zeros coincide: $H(z)$ may have complex conjugate zeros on the unit circle at $z=\color{red}{z_1}$ and $z=\color{red}{z^\ast_1}$. Or $H(z)$ may have one or more zeros at $z=\color{yellow}{1}$ or $z=\color{green}{-1}$. Finally $H(z)$ may have reciprocal zeros on the real axis at $z=\color{blue}{z_2}$ and $z=\color{blue}{1/z_2}$.

Another consequence of equations (\ref{Eq:Sym1}) and (\ref{Eq:Sym2}) is that the cases $z=1$ and $z=-1$ deserve special attention. For example evaluating the Type II system function $H_{II}(z)$ for $z=-1$ results in: \begin{eqnarray*} H_{II}(z)\vert_{z=-1} &=& \left \{ z^{-(M-1)} H_{II}(z^{-1}) \right \} \bigg\vert_{z=-1} \newline H_{II}(-1) &=& (-1)^{-(M-1)} H_{II}(-1) \overset{\text{even } M}{=} -H_{II}(-1) \text{ } \Rightarrow \text{ } H_{II}(-1)=0 \end{eqnarray*} In a similar we can derive the following results:

Type	$z=1$	$z=-1$
I	--	--
II	--	$H_{II}(-1)=0$
III	$H_{III}(1)=0$	$H_{III}(-1)=0$
IV	$H_{IV}(1)=0$	--

From the fact that $z=1$ coincides with $\theta=0$ and $z=-1$ with $\theta=\pm \pi$, it follows that these results are a generalized representation of the results as found in the previous subsection.

Examples of linear phase filters

In order to show the validity of the linear phase properties try to solve the following two odd length 5 FIR filter examples: The first example is an FIR filter with a even-symmetric impulse response and the second one with an odd-symmetric impulse response.

Reduced complexity

The symmetry of the impulse response coefficients of a linear-phase FIR filter can be exploited to reduce the complexity of the realization of such a structure.

All-pass filter

An all-pass filter passes all frequency with the same magnification factor, that is the magnitude of the frequency response is constant $$ | H_{ap}(e^{j\theta})| = 1 \hspace{3mm} \forall \theta $$ This unit magnitude constraint constrains poles and zeros of a rational system function to occur in mirrored pairs. Thus if $H(z)$ has a pole $z=\alpha_k$, $H(z)$ must also have a zero at the mirrored location $z=1/\alpha^\ast_k$. \begin{eqnarray*} \text{Complex } h[n] &:& H_{ap}(z) = \prod_{k=1}^{p} \frac{z^{-1}-\alpha_k^\ast}{1 - \alpha_k z^{-1}} \newline \text{Real } h[n] &:& H_{ap}(z) = \prod_{k=1}^{N_s} \frac{|\alpha_{k}|^2 - 2 \Re e \{ \alpha_k \} z^{-1}+ z^{-2}}{1 - 2 \Re e \{ \alpha_k \} z^{-1}+ |\alpha_{k}|^2 z^{-2}} \end{eqnarray*} The poles of a stable and causal all pass filter $H(z)$ lie inside the unit circle, that is all $|\alpha_k|<1$. If the impulse response $h[n]$ is real-valued, the complex roots occur in conjugate pairs, and these conjugate pairs can be combined to form second-order factors from which all coefficients are real, as shown in the equation.

Minimum and maximum phase system

A stable and causal LTI system has all its poles inside the unit circle. The zeros, however may lie anywhere in the $z$-plane. In some applications, it is necessary to constraint a system $H(z)$ so that its inverse $G(z)=1/H(z)$ is also stable and causal. This requires that the zeros of $H(z)$ lie also inside the unit circle. A stable and causal filter that has a stable and causal inverse is said to have minimum phase and so a minimum phase system has all of its poles and zeros inside the unit circle, as shown in Fig. 3.

The magnitude and phase response of a minimum phase system with three zeros inside the unit circle is depicted in Fig. 3.

When mirroring all zeros of a stable and causal minimum phase system we obtain a maximum phase system and so a maximum phase system has all of its poles inside and its zeros outside the unit circle, as shown in Fig. 4.

Fig. 4. shows the magnitude and phase response of a maximum phase system with three zeros outside the unit circle as depicted in the pole zero plot. These zeros are obtained by mirroring all three zeros of the previous minimum phase system.

Factoring: Product All pass and Minimum Phase filter

Stable causal filter with system function $H(z)$, can always be factored as a product of a minimum phase filter and an all-pass filter. The procedure is as follows:

1. First mirror the zeros which are outside $|z|=1$ into new zeros inside $|z|=1$.
2. Then cancel the new zeros by new poles.
3. Combine the old and new zeros that are inside $|z|=1$ and the old poles together which results in a minimum phase system.
4. The combination of the old zeros that are outside $|z|=1$ and the new poles results in an all pass system.

Comb filter

A comb filter is obtained by replacing each delay of an original filter structure by $N$ delays in a new filter structure. In terms of the system function, the function variable $z$ of the original system function $H(z)$ is replaced by $z^N$ in the new system function $G(z)$: $$ G(z)=H(z^N) $$

Averaging filter

An $M$ point averaging filter can be realized with the following non recursive direct form I structure as a transversal FIR with unit weights as depicted in Fig. 5.

In a previous module we have seen that the frequency response of this $N$ point averaging filter can be described by the following Dirichlet function \begin{eqnarray*} h[n]= \frac{1}{M} \sum_{k=0}^{M-1} \delta[n-k] & \circ \hspace{-1.3mm} - \hspace{-1.3mm} \circ & H(e^{j\theta}) = \frac{1}{M} \frac{\sin (\frac{M}{2} \theta)}{\sin (\frac{1}{2} \theta)} \cdot e^{-j\frac{M-1}{2}\theta} \end{eqnarray*} from which the magnitude response has its main lobe around frequency zero and the phase response is linear as shown in Fig. 6. An alternative recursive structure can be found by rewriting the system function as a rational function that can be interpreted as the cascading of the non recursive structure of the numerator (in red) and the recursive structure of the denominator (in blue). \begin{eqnarray*} H(z)&=&\frac{1}{M} \sum_{k=0}^{M-1} z^{-k} = \frac{1}{M} \cdot \frac{1 - z^{-M}}{1 - z^{-1}} =\color{red}{\frac{1}{M} \cdot (1 -z^{-M})} \cdot \color{blue}{ \frac{1}{1-z^{-1}}}\newline &=& \color{red}{\frac{1}{M} \prod_{n=0}^{M-1} ( 1- \alpha_n z^{-1})} \cdot \color{blue}{\frac{1}{1 - z^{-1}}} \hspace{3mm} \text{with zeros } \color{red}{\alpha_n=e^{jn \frac{2\pi}{M}}} \end{eqnarray*} The non recursive structure of the numerator can be expanded as the product of $M$ first order terms, each with one zero at $z=\alpha_n=e^{jn \frac{2\pi}{M}}$ and one pole in $z=0$. The recursive structure of the denominator has one pole in $z=1$ and one zero in $z=0$. Concluding it follows that the pole zero plot of the $M$ point averaging filter contains, except poles at $z=0$, $M$ zeros that are equally distributed over the unit circle and one pole at $z=1$, which cancels the zero at $z=1$.

Frequency sampling filter

The previously discussed philosophy of the averaging filter can be extended to an $M$ point transversal FIR filter with weights $h_k$ as shown in Fig. 7

This results in the so called frequency sampling filter which is a filter structure from which the system function $H(z)$, or equivalently its frequency response $H(e^{j\theta})$, can be parameterized in terms of the $M$ DFT weights $H[l]$ of the impulse response $h[n]$.

Starting with the system function $H(z)$ of non recursive $M$ point transversal FIR filter with weights $h_k$, the derivation of the frequency sampling structure goes as follows: With the $M$-point Inverse DFT relation \begin{eqnarray*} h[n]= \sum_{k=0}^{M-1} h_k \delta[n-k] &\overset{\text{IDFT}}{\circ \hspace{-1.3mm} - \hspace{-1.3mm} \circ} & \frac{1}{M} \sum_{l=0}^{M-1} \color{blue}{H[l]} e^{j(2 \pi/M)l k} \end{eqnarray*} we can substitute this IDFT equation for the impulse response weights. \begin{eqnarray*} H(z)&=& \sum_{k=0}^{M-1} h_k z^{-k} = \sum_{k=0}^{M-1} \left \{ \frac{1}{M} \sum_{l=0}^{M-1} \color{blue}{H[l]} e^{j(2 \pi/M)l k} \right \} z^{-k} \end{eqnarray*} Then change the order of the summations and write the internal summation as a rational function. \begin{eqnarray*} H(z)&=& \frac{1}{M} \sum_{l=0}^{M-1} \color{blue}{H[l]} \left \{ \sum_{k=0}^{M-1} \left ( e^{j(2 \pi/M)l } z^{-1} \right )^{k} \right \}\newline &=& \frac{1}{M} \sum_{l=0}^{M-1} \color{blue}{H[l]} \cdot \left \{ \frac{1-\color{green}{e^{j(2 \pi/M)l M }} z^{-M}}{1-e^{j(2 \pi /M)l } z^{-1}} \right \} \end{eqnarray*} The exponent (in green) of the numerator polynomial is equal to 1. \begin{eqnarray*} H(z)&=& \frac{1}{M} \sum_{l=0}^{M-1} {\color{blue}H[l]} \cdot \left \{ \frac{1-z^{-M}}{1-e^{j(2 \pi /M)l } z^{-1}} \right \} \end{eqnarray*} As a last step the system function can be written as a product (cascading) of a non recursive structure of the numerator (in red) and the recursive structure of the denominator (in blue), representing the $M$ parallel first order terms. \begin{eqnarray*} H(z)&=& \left \{ \color{red}{\frac{1}{M} \cdot (1-z^{-M}) }\right \} \cdot \left \{ \color{blue}{\sum_{l=0}^{M-1} \frac{H[l]}{\left ( 1-\alpha_l z^{-1} \right )}} \right \} \hspace{3mm} \text{with } \color{red}{\alpha_l=e^{jl \frac{2 \pi}{M}}} \end{eqnarray*} A realization scheme of this frequency sampling filter structure is depicted in Fig. 8.

The recursive part consists of $M$ parallel weighted first order terms, each with a pole at $z=\alpha_l=e^{jl \frac{2\pi}{M}}$, a zero at $z=0$ and weight $H[l]$. These $M$ poles cancel the $M$ equally distributed zeros of the non recursive part (in red) and the value of the frequency response at each of these $M$ equally distributed frequencies is equal to the $M$ different values of the $M$-point DFT weights $H[l]$ of the $M$ point impulse response $h[n]$.

In a follow up module, we will see that the frequency sampling filter structure is typically used for the realization of narrow band filters. In such a case most weights of the parallel terms are equal to zero and need not to be implemented, which results in a very efficient structure.

Lattice filter

A lattice filter has a modular structure. That means that a lattice consists of a number of cascaded modules and each module has the same structure. For example, the top of Fig. 9 shows a typical module of a lattice filter, which is a two port, with two inputs, two outputs, one delay and two multipliers with a factor $\Gamma_k$.

In most literature these parameters are denoted by reflection coefficients. Since the module does not contain a feedback path the cascading of $p$ of such modules represent a $p^{th}$ order FIR filter, as shown at the bottom of Fig. 9.

In a similar way lattice filters can be used to implement All pole structures or structures with poles and zeros, as depicted in Fig. 10.

Lattice filters have a number of interesting and important properties that make them popular in a number of different applications. Besides the modularity property, the structure has low sensitivity to parameter quantization effects, and a simple criterion for ensuring filter stability.

Example Lattice FIR filter

The following equations show the, coupled, difference equation of section $k$ of a lattice FIR filter: \begin{eqnarray*} f_k[n] &=& f_{k-1}[n] + \Gamma_k g_{k-1}[n-1] \newline g_k[n] &=& g_{k-1}[n-1] + \Gamma_k f_{k-1}[n] \end{eqnarray*} When connecting the input $x[n]$ to both inputs of the first module, thus $F_0(z)=G_0(z)=X(z)$, the system function $A_k(z)$ relates the input $x[n]$ to the intermediate output $f_k[n]$. With $A_0(z)=1$, the system function $A_k(z)$ may be solved the given recurrence equation: $$ F_k(z) = A_k(z) \cdot X(z) \hspace{3mm} \text{with } A_k(z)= A_{k-1}(z) + \Gamma_k z^{-k} A_{k-1}(z^{-1}) $$ As an example of the second order Lattice FIR filter with reflection coefficients $\Gamma_1= \frac{1}{2}$ and $\Gamma_1= \frac{1}{4}$. The system function relating $x[n]$ to $f_1[n]$ is $A_1(z)$ and the second order system function relating $x[n]$ to $f_2[n]$ is $A_2(z)$: \begin{eqnarray*} A_1(z) &=& A_0(z) + \Gamma_1 z^{-1} A_0(z^{-1}) = 1 + \frac{1}{2} z^{-1} \newline A_2(z) &=& A_1(z) + \Gamma_2 z^{-2} A_1(z^{-1}) = 1 + \frac{5}{5} z^{-1} + \frac{1}{4} z^{-2} \end{eqnarray*} which represents the non recursive second order transversal structure as depicted in Fig. 11.