Linear-Phase FIR Filter Design by Least Squares This module describes the design of linear-phase FIR filters based on the square error criterion. We will see that FIR filters that minimize the square error can be found by solving a linear system of equations. This technique is straight-forward and is applicable to arbitrary desired frequency responses. In addition, linear constraints on the coefficients are easily included. Linear-phase filter design by least squares has several advantages. Optimal with respect to square error criterion. Simple, non-iterative method. Analytic solutions sometimes possible, otherwise solution is obtained via solution to linear system of equations. Allows the use of a frequency dependent weighting function. Suitable for arbitrary D ω and W ω . Easy to include arbitrary linear constraints.

Derivation The weighted integral square error (or " L 2 error") is defined by ε 2 ω 0 W ω A ω D ω 2 where A ω : the actual amplitude response D ω : the ideal amplitude response W ω : nonnegative weighting function The weighting function can be used to assign more importance to specific parts of the frequency response. For example, it is common to weight the stop-band more heavily than the pass-band. Once the length N and the Type of the filter (I, II, III, IV) is chosen, the goal is to find the filter coefficients h n that minimizes ε 2 . To develop this approach, we will consider the design of Type I FIR filters. The design of the other 3 linear-phase FIR filter types can be developed similarly. Recall that for a Type I FIR filter, the amplitude response if given by A ω n 0 M a n n ω where a 0 h M a n 2 h M n 1 n M M N 1 2 To obtain the coefficients a n to minimize ε 2 , we can set the derivatives equal to zero, a k ε 2 0 0 k M The derivatives of ε 2 with respect to a k can be found as: a k ε 2 ω 0 a k W ω A ω D ω 2 2 ω 0 W ω A ω D ω a k A ω 2 ω 0 W ω A ω D ω k ω Therefore, a k ε 2 0 becomes ω 0 W ω A ω k ω ω 0 W ω D ω k ω or ω 0 W ω n 0 M a n n ω k ω ω 0 W ω D ω k ω or n 0 M a n ω 0 W ω n ω k ω ω 0 W ω D ω k ω If we define Q k n 1 ω 0 W ω n ω k ω and b k 1 ω 0 W ω D ω k ω then the derivative conditions can be written as n 0 M Q k n a n b k where 0 k M This is a linear system of equations, and can be written in matrix form as Q 0 0 Q 0 1 … Q 0 M Q 1 0 Q 1 1 … Q 1 M ⋮ ⋮ ⋮ ⋮ Q M 0 Q M 1 … Q M M a 0 a 1 ⋮ a M b 0 b 1 ⋮ b M or Q a b Therefore, the Type 1 FIR filter that minimizes the square error can be obtained by solving this linear system of equations. a Q b

Structure of the Matrix Q It turns out that the matrix Q has a special structure. Note that n ω k ω 1 2 k n ω 1 2 k n ω so that Q k n 1 ω 0 W ω n ω k ω 1 2 ω 0 W ω k n ω 1 2 ω 0 W ω k n ω or Q k n 1 2 Q 1 k n 1 2 Q 2 k n where Q 1 and Q 2 are defined as Q 1 k n 1 ω 0 W ω k n ω and Q 2 k n 1 ω 0 W ω k n ω Accordingly, we can write Q 1 k n q k n Q 2 k n q k n where q n 1 ω 0 W ω n ω With this notation, the matrices Q 1 and Q 2 are written as Q 1 q 0 q 1 … q M q 1 q 0 … q M 1 ⋮ ⋮ ⋮ ⋮ q M q M 1 … q 0 and Q 2 q 0 q 1 … q M q 1 q 2 … q M 1 ⋮ ⋮ ⋮ ⋮ q M q M 1 … q 2 M Note that we have used q n q n here. The matrix Q 1 is a symmetric Toeplitz matrix (constant along its diagonals), and the matrix Q 2 is a Hankel matrix (constant along its anti-diagonals). Consequently, the matrices can be stored with less memory than arbitrary matrices ( 2 M 1 numbers instead of M 1 2 numbers), there are fast algorithms to compute the solution to 'Toeplitz plus Hankel' systems with computational complexity O M 2 instead of O M 3 . (In fact, the complexity can be reduced further, but with higher overhead.)

Relation to the DTFT To express q k and b k using the inverse Fourier transform, extend D ω and W ω symmetrically, so that D ω D ω and W ω W ω . Then we can write q n 1 2 ω W ω n ω As sine is an anti-symmetric function ω W ω n ω 0 so we can write q n 1 2 ω W ω n ω n ω or q n 1 2 ω W ω n ω which we recognize as the inverse discrete-time Fourier transform q n DTFT W ω Similarly, q n DTFT W ω D ω

Low-Pass: Weighted Square Error The weighting function W ω can be used to improve the FIR low-pass filter because it allows you to eliminate Gibbs phenomenon by deleting a neighborhood around the band edge, and it allows you to assign different weights to the pass-band and the stop-band. For example, if the ideal low-pass amplitude response is as shown in .

and if the weighting function is as shown, .

where ω p ω o ω s , then the square error criterion becomes ε 2 ω 0 ω p A ω 1 2 K ω ω s A ω 2 To find the matrix Q and the vector b to this weighting function it is useful to recall 1 ω ω 1 ω 2 n ω ω 2 sinc ω 2 n ω 1 sinc ω 1 n Then q k 1 ω 0 W ω k ω 1 ω 0 ω p k ω K ω ω s k ω ω p K 1 ω s k 0 ω p sinc ω p k K ω s sinc ω s k k 0 Similarly, b k 1 ω 0 W ω D ω k ω 1 ω 0 ω p k ω ω p sinc ω p k

Weighted Low-Pass Example In the following example, we design a Type 1 FIR low-pass filter of length 31, with band-edges ω p 0.26 , ω s 0.34 and a stop-band weight of K 10 . (See )

The second figure shows the pass-band edge detail. Compared to the Impulse Response Truncation (IRT) method the peak error is reduced. The filter was designed using the following Matlab code.