<< Chapter < Page Chapter >> Page >

What does this have to do with linear-phase filter design?

It's the same problem! To show that, consider an odd-length, symmetric linear phase filter.

H ω n M 1 0 h n ω n ω M 1 2 h M 1 2 2 n L 1 h M 1 2 n ω n
A ω h L 2 n L 1 h L n ω n

Where L M 1 2 .

Using trigonometric identities (such as n α 2 n 1 α α n 2 α ), we can rewrite A ω as A ω h L 2 n L 1 h L n ω n k L 0 α k ω k where the α k are related to the h n by a linear transformation. Now, let x ω . This is a one-to-one mapping from x -1 1 onto ω 0 . Thus A ω is an L th-order polynomial in x ω !

The alternation theorem holds for the L filter design problem, too!
Therefore, to determine whether or not a length- M , odd-length, symmetric linear-phase filter is optimal in an L sense, simply count the alternations in E ω W ω A d ω A ω in the pass and stop bands.If there are L 2 M 3 2 or more alternations, h n , 0 n M 1 is the optimal filter!

Got questions? Get instant answers now!

Optimality conditions for even-length symmetric linear-phase filters

For M even, A ω n 0 L h L n ω n 1 2 where L M 2 1 Using the trigonometric identity α β α β 2 α β to pull out the ω 2 term and then using the other trig identities , it can be shown that A ω can be written as A ω ω 2 k 0 L α k ω k Again, this is a polynomial in x ω , except for a weighting function out in front.

E ω W ω A d ω A ω W ω A d ω ω 2 P ω W ω ω 2 A d ω ω 2 P ω
which implies
E x W ' x A d ' x P x
where W ' x W x 1 2 x and A d ' x A d x 1 2 x Again, this is a polynomial approximation problem, so the alternation theorem holds. If E ω has at least L 2 M 2 1 alternations, the even-length symmetric filter is optimal in an L sense.

The prototypical filter design problem: W 1 ω ω p δ s δ p ω s ω 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: x P x 0 . Since P x is an ( L - 1 ) th-order polynomial, it can have at most L - 1 zeros. However , the mapping x ω implies that ω A ω 0 at ω 0 and ω , 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 ω 0 or ω .
  • Alternations must occur at ω p and ω s . See .
  • The filter must be equiripple except at possibly ω 0 or ω . Again see .
The alternation theorem doesn't directly suggest a method for computing the optimal filter. It simply tells ushow to recognize that a filter is optimal, or isn't optimal. What we need is an intelligent way of guessing the optimal filtercoefficients.
In matrix form, these L 2 simultaneous equations become 1 ω 0 2 ω 0 ... L ω 0 1 W ω 0 1 ω 1 2 ω 1 ... L ω 1 -1 W ω 1 ... ... 1 ω L + 1 2 ω L + 1 ... L ω L + 1 ± 1 W ω L + 1 h L h L 1 h 1 h 0 δ A d ω 0 A d ω 1 A d ω L + 1 or W h δ A d So, for the given set of L 2 extremal frequencies, we can solve for h and δ via h δ W A d . Using the FFT, we can compute A ω of h n , on a dense set of frequencies. If the old ω k are, in fact the extremal locations of A ω , then the alternation theorem is satisfied and h n is optimal . If not, repeat the process with the new extremal locations.

Computational cost

O L 3 for the matrix inverse and N 2 logbase --> N for the FFT ( N 32 L , 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 ω is an L th-order polynomial in x ω , so Lagrange interpolation can be used to exactly compute A ω from L 1 samples of A ω k , k

    0 1 2 ... L
.

Thus, given a set of extremal frequencies and knowing δ , samples of the amplitude response A ω can be computed directly from the

A ω k 1 k 1 W ω k δ A d ω k
without solving for the filter coefficients!

This leads to computational savings!

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

δ k 0 L 1 γ k A d ω k k 0 L 1 1 k 1 γ k W ω k
where γ k i i k 0 L 1 1 ω k ω i The result is the Parks-McClellan FIR filter design method, which is simply an application of the Remez exchange algorithmto the filter design problem. See .

The initial guess of extremal frequencies is usually equally spaced in the band. Computing δ costs O L 2 . Using Lagrange interpolation costs O 16 L L O 16 L 2 . Computing h n costs O L 3 , but it is only done once!

The cost per iteration is O 16 L 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.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital filter design. OpenStax CNX. Jun 09, 2005 Download for free at http://cnx.org/content/col10285/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital filter design' conversation and receive update notifications?

Ask