3.10 Parks-mcclellan fir filter design  (Page 2/2)

Optimality conditions for even-length symmetric linear-phase filters

For $M$ even, $$A(\omega )=\sum_{n=0}^L h(L-n)\cos (\omega (n+\frac{1}{2}))$$ where $L=\frac{M}{2}-1$ Using the trigonometric identity $\cos (\alpha +\beta )=\cos (\alpha -\beta )+2\cos \alpha \cos \beta$ to pull out the $\frac{\omega }{2}$ term and then using the other trig identities , it can be shown that $A(\omega )$ can be written as $$A(\omega )=\cos \left(\frac{\omega }{2}\right)\sum_{k=0}^L {\alpha }_k\cos \omega ^k$$ Again, this is a polynomial in $x=\cos \omega$ , except for a weighting function out in front.

The prototypical filter design problem: $$W=\begin{cases}1 & \text{if $\left|\omega \right|\le {\omega }_p$}\\ \frac{{\delta }_s}{{\delta }_p} & \text{if $\left|{\omega }_s\right|\le \left|\omega \right|$}\end{cases}$$ See .

L-∞ optimal lowpass filter design lemma

• The maximum possible number of alternations for a lowpass filter is $L+3$ : The proof is that the extrema of a polynomial occur only where the derivative is zero: $\frac{\partial^{1}P(x)}{\partial x}=0$ . Since $\frac{d P(x)}{d }$ is an $(L-1)$ th-order polynomial, it can have at most $L-1$ zeros. However , the mapping $x=\cos \omega$ implies that $\frac{\partial^{1}A(\omega )}{\partial \omega }=0$ at $\omega =0$ and $\omega =\pi$ , for two more possible alternation points. Finally , the band edges can also be alternations, for a total of $L-1+2+2=L+3$ possible alternations.
• There must be an alternation at either $\omega =0$ or $\omega =\pi$ .
• Alternations must occur at ${\omega }_p$ and ${\omega }_s$ . See .
• The filter must be equiripple except at possibly $\omega =0$ or $\omega =\pi$ . Again see .

Computational cost

$O(L^3)$ for the matrix inverse and $N\log_{2}N$ for the FFT ( $N\ge 32L$ , typically), per iteration !

This method is expensive computationally due to the matrix inverse.

A more efficient variation of this method was developed by Parks and McClellan (1972), and is based on theRemez exchange algorithm. To understand the Remez exchange algorithm, we first need to understand Lagrange Interpoloation .

Now $A(\omega )$ is an $L$ th-order polynomial in $x=\cos \omega$ , so Lagrange interpolation can be used to exactly compute $A(\omega )$ from $L+1$ samples of $A({\omega }_k)$ , $k$

0 1 2 ... L

Thus, given a set of extremal frequencies and knowing $\delta$ , samples of the amplitude response $A(\omega )$ can be computed directly from the

This leads to computational savings!

Note that is a set of $L+2$ simultaneous equations, which can be solved for $\delta$ to obtain (Rabiner, 1975)

The cost per iteration is $O(16L^2)$ , as opposed to $O(L^3)$ ; much more efficient for large $L$ . Can also interpolate to DFT sample frequencies, take inverse FFT to get corresponding filter coefficients, andzeropad and take longer FFT to efficiently interpolate.