Skip to content Skip to navigation

Connexions

You are here: Home » Content » FIR Filter Design by Frequency Sampling or Interpolation

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the author

Recently Viewed

This feature requires Javascript to be enabled.

FIR Filter Design by Frequency Sampling or Interpolation

Module by: C. Sidney Burrus

Since samples of the frequency response of an FIR filter can be calculated by taking the DFT of the impulse response h(n)h(n), one could propose a filter design method consisting of taking the inverse DFT of samples of a desired frequency response. This can indeed be done and is called frequency sampling design. The resulting filter has a frequency response that exactly interpolates the given samples, but there is no explicit control of the behavior between the samples Entry 1, Entry 2.

Three methods for frequency sampling design are:

  1. Take the inverse DFT (perhaps using the FFT) of equally spaced samples of the desired frequency response. Care must be taken to use the correct phase response to obtain a real valued causal h(n)h(n) with reasonable behavior between sample response. This method works for general nonlinear phase design as well as for linear phase.
  2. Derive formulas for the inverse DFT which take the symmetries, phase, and causality into account. It is interesting to notice these analysis and design formulas turn out to be the discrete cosine and sine transforms and their inverses.
  3. Solve the set of simultaneous linear equations that result from calculating the sampled frequency response from the impulse response. This method allows unevenly spaced samples of the desired frequency response but the resulting equations may be ill conditioned.

Frequency Sampling Filter Design by Inverse DFT

The most direct frequency sampling design method is to simply take the inverse DFT of equally spaced samples of the desired complex frequency response Hd(ωk)Hd(ωk). This is done by

h ( n ) = 1 N ∑ k = 0 N - 1 H d ( 2 π N k ) e j 2 π n k / N h ( n ) = 1 N ∑ k = 0 N - 1 H d ( 2 π N k ) e j 2 π n k / N (1)

where care must be taken to insure that the real and imaginary parts (or magnitude and phase) of Hd(ωk)Hd(ωk) satisfy the symmetry conditions that give a real, causal h(n)h(n). This method will allow a general complex H(ω)H(ω) as well as a linear phase. In most cases, it is easier to specify proper and consistent samples if it is the magnitude and phase that are set rather than the real and imaginary parts. For example, it is important that the desired phase be consistent with the specified length being even or odd as is given in ((Reference)) and ((Reference)).

Since the frequency sampling design method will always produce a filter with a frequency response that interpolates the specified samples, the results of inappropriate phase specifications will show up as undesired behavior between the samples.

Frequency Sampling Filter Design by Formulas

When equally spaced samples of the desired frequency response are used, it is possible to derive formulas for the inverse DFT and, therefore, for the filter coefficients. This is because of the orthogonal basis function of the DFT. These formulas can incorporate the various constraints of a real h(n)h(n) and/or linear phase and eliminate the problems of inconsistency in specifying H(ωk)H(ωk).

To develop explicit formulas for frequency-sampling design of linear-phase FIR filters, a direct use of the inverse DFT is most straightforward. When H(ω)H(ω) has linear phase, (Equation 1) may be simplified using the formulas for the four types of linear-phase FIR filters.

Type 1. Odd Sampling

Samples of the frequency response ((Reference))for the filter where NN is odd, L=NL=N, and M=(N-1)/2M=(N-1)/2, and where there is a frequency sample at ω=0ω=0 is given as

A k = ∑ n = 0 M - 1 2 h ( n ) cos ( 2 π ( M - n ) k / N ) + h ( M ) . A k = ∑ n = 0 M - 1 2 h ( n ) cos ( 2 π ( M - n ) k / N ) + h ( M ) . (2)

Using the amplitude function A(ω)A(ω), defined in ((Reference)), of the form (Equation 2) and the IDFT (Equation 1) gives for the impulse response

h ( n ) = 1 N ∑ k = 0 N - 1 e - j 2 π M k / N A k e j 2 π n k / N h ( n ) = 1 N ∑ k = 0 N - 1 e - j 2 π M k / N A k e j 2 π n k / N (3)

or

h ( n ) = 1 N ∑ k = 0 N - 1 A k e j 2 π ( n - M ) k / N . h ( n ) = 1 N ∑ k = 0 N - 1 A k e j 2 π ( n - M ) k / N . (4)

Because h(n)h(n) is real, Ak=AN-kAk=AN-k and (Equation 4) becomes

h ( n ) = 1 N [ A 0 + ∑ k = 1 M - 1 2 A k cos ( 2 π ( n - M ) k / N ) ] . h ( n ) = 1 N [ A 0 + ∑ k = 1 M - 1 2 A k cos ( 2 π ( n - M ) k / N ) ] . (5)

Only M+1M+1 of the h(n)h(n) need be calculated because of the symmetries in ((Reference)).

This formula calculates the impulse response values h(n)h(n) from the desired frequency samples AkAk and requires M2M2 operations rather than N2N2. An interesting observation is that not only are (Equation 2) and (Equation 5) a pair of analysis and design formulas, they are also a transform pair. Indeed, they are of the same form as a discrete cosine transform (DCT).

Type 2. Odd Sampling

A similar development applied to the cases for even NN from ((Reference)) gives the amplitude frequency response samples as

A k = ∑ n = 0 N / 2 - 1 2 h ( n ) cos ( 2 π ( M - n ) k / N ) A k = ∑ n = 0 N / 2 - 1 2 h ( n ) cos ( 2 π ( M - n ) k / N ) (6)

with the design formula of

h ( n ) = 1 N [ A 0 + ∑ k = 1 N / 2 - 1 2 A k cos ( 2 π ( n - M ) k / N ) ] h ( n ) = 1 N [ A 0 + ∑ k = 1 N / 2 - 1 2 A k cos ( 2 π ( n - M ) k / N ) ] (7)

which is of the same form as (Equation 5), except that the upper limit on the summation recognizes NN as even and AN/2AN/2 equals zero.

Even Sampling

The schemes just described use frequency samples at

ω = 2 π k / N , k = 0 , 1 , 2 , . . . , N - 1 ω = 2 π k / N , k = 0 , 1 , 2 , . . . , N - 1 (8)

which are NN equally-spaced samples starting at ω=0ω=0. Another possible pattern for frequency sampling that allows design formulas has no sample at ω=0ω=0, but uses NN equally-spaced samples located at

ω = ( 2 k + 1 ) π / N , k = 0 , 1 , 2 , . . . , N - 1 ω = ( 2 k + 1 ) π / N , k = 0 , 1 , 2 , . . . , N - 1 (9)

This form of frequency sampling is more difficult to relate to the DFT than the sampling of (Equation 8), but it can be done by stretching AkAk and taking a 2N-length DFT Entry 1.

Type 1. Even Sampling

The two cases for odd and even lengths and the two for samples at zero and not at zero frequency give a total of four cases for the frequency-sampling design method applied to linear- phase FIR filters of Types 1 and 2, as defined in (Reference). For the case of an odd length and no zero sample, the analysis and design formulas are derived in a way analogous to (Equation 2) and (Equation 7) to give

A k = ∑ n = 0 M - 1 2 h ( n ) cos ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) + h ( M ) A k = ∑ n = 0 M - 1 2 h ( n ) cos ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) + h ( M ) (10)

The design formula becomes

h ( n ) = 1 N [ ∑ k = 0 M - 1 2 A k cos ( 2 π ( n - M ) ( k + 1 / 2 ) / N ) + A M cos π ( n - M ) ] h ( n ) = 1 N [ ∑ k = 0 M - 1 2 A k cos ( 2 π ( n - M ) ( k + 1 / 2 ) / N ) + A M cos π ( n - M ) ] (11)

Type 2. Even Sampling

The fourth case, for an even length and no zero frequency sample, gives the analysis formula

A k = ∑ n = 0 N / 2 - 1 2 h ( n ) cos ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) A k = ∑ n = 0 N / 2 - 1 2 h ( n ) cos ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) (12)

and the design formula

h ( n ) = 1 N [ ∑ k = 0 N / 2 - 1 2 A k cos ( 2 π ( n - M ) ( k + 1 / 2 ) / N ) ] h ( n ) = 1 N [ ∑ k = 0 N / 2 - 1 2 A k cos ( 2 π ( n - M ) ( k + 1 / 2 ) / N ) ] (13)

These formulas in (Equation 5), (Equation 7), (Equation 11), and (Equation 13) allow a very straightforward design of the four frequency-sampling cases. They and their analysis companions in (Equation 2), (Equation 6), (Equation 10), and (Equation 12) also are the four forms of discrete cosine and inverse-cosine transforms. Matlab programs which implement these four designs are given in the appendix.

Type 3. Odd Sampling

The design of even-symmetric linear-phase FIR filters of Types 1 and 2 in (Reference) have been developed here. A similar development for the odd-symmetric filters, Types 3 and 4, can easily be performed with the results closely related to the discrete sine transform. The Type 3 analysis and design results using the frequency sampling scheme of (Equation 8) are

A k = ∑ b = 0 M - 1 2 h ( n ) sin ( 2 π ( M - n ) k / N ) A k = ∑ b = 0 M - 1 2 h ( n ) sin ( 2 π ( M - n ) k / N ) (14)

and

h ( n ) = 1 N [ ∑ k = 1 M 2 A k sin ( 2 π ( M - n ) k / N ) ] h ( n ) = 1 N [ ∑ k = 1 M 2 A k sin ( 2 π ( M - n ) k / N ) ] (15)

Type 4. Odd Sampling

For Type 4 they are

A k = ∑ n = 0 N / 2 - 1 2 h ( n ) sin ( 2 π ( M - n ) k / N ) A k = ∑ n = 0 N / 2 - 1 2 h ( n ) sin ( 2 π ( M - n ) k / N ) (16)

and

h ( n ) = 1 N [ ∑ k = 1 N / 2 - 1 2 A k sin ( 2 π ( M - n ) k / N ) + A N / 2 sin ( π ( M - n ) ) ] . h ( n ) = 1 N [ ∑ k = 1 N / 2 - 1 2 A k sin ( 2 π ( M - n ) k / N ) + A N / 2 sin ( π ( M - n ) ) ] . (17)

Type 3. Even Sampling

Using the frequency sampling scheme of (Equation 9), the Type 3 equations become

A k = ∑ n = 0 M - 1 2 h ( n ) sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) A k = ∑ n = 0 M - 1 2 h ( n ) sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) (18)

and

h ( n ) = 1 N [ ∑ k = 0 M - 1 2 A k sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) ] h ( n ) = 1 N [ ∑ k = 0 M - 1 2 A k sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) ] (19)

Type 4. Even Sampling

For Type 4 they are

A k = ∑ n = 0 N / 2 - 1 2 h ( n ) sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) A k = ∑ n = 0 N / 2 - 1 2 h ( n ) sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) (20)

and

h ( n ) = 1 N [ ∑ k = 0 N / 2 - 1 2 A k sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) ] . h ( n ) = 1 N [ ∑ k = 0 N / 2 - 1 2 A k sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) ] . (21)

These Type 3 and 4 formulas are useful in the design of differentiators and Hilbert transformers [1,2,9,31] directly and as the base of the discrete least-squared-error methods in (Reference).

Frequency Sampling Design of FIR Filters by Solution of Simultaneous Equations

A direct way of designing FIR filters from samples of a desired amplitude simply takes the sampled definition of the frequency response ((Reference)) as

A ( ω k ) = ∑ n = 0 M - 1 2 h ( n ) cos ω k ( M - n ) + h ( M ) A ( ω k ) = ∑ n = 0 M - 1 2 h ( n ) cos ω k ( M - n ) + h ( M ) (22)

or the reduced form from ((Reference)) as

A ( ω k ) = ∑ n = 0 M a ( n ) cos ( ω k ( M - n ) ) A ( ω k ) = ∑ n = 0 M a ( n ) cos ( ω k ( M - n ) ) (23)

where

a ( n ) = { h(M) 0 2h(n) for n = M otherwise for 0 ≤ n ≤ M - 1 a(n)={ h(M) 0 2h(n) for n = M otherwise for 0 n M - 1 (24)

for k=0,1,2,...,Mk=0,1,2,...,M and solves the M+1M+1 simultaneous equations for a(n)a(n) or equivalently, h(n)h(n). Indeed, this approach can be taken with general non-linear phase design from

Indeed, this approach can be taken with general non-linear phase design from

H ( ω k ) = ∑ n = 0 N - 1 h ( n ) e j ω k n H ( ω k ) = ∑ n = 0 N - 1 h ( n ) e j ω k n (25)

for k=0,1,2,⋯,N-1k=0,1,2,⋯,N-1 which gives NN equations with NN unknowns.

This design by solving simultaneous equations allows non-equally spaced samples of the desired response. The disadvantage comes from the numerical calculations taking considerable time and being subject to inaccuracies if the equations are ill-conditioned.

The frequency sampling design method is interesting but is seldom used for direct design of filters. It is sometimes used as an interpolating method in other design procedures to find h(n)h(n) from calculated A(ωk)A(ωk). It is also used as a basis for a least squares design method discussed in the next section.

Examples of Frequency Sampling FIR Filter Design

To show some of the characteristics of FIR filters designed by frequency sampling, we will design a Type 1., length-15 FIR low pass filter. Desired amplitude response was one in the pass band and zero in the stop band. The cutoff frequency was set at approximately f=0.35f=0.35 normalized. Using the formulas (Equation 5), (Equation 7), (Equation 11), and (Equation 13), we got impulse responses h(n)h(n), which are use to generate the results shown in Figures Figure 1 and Figure 2.

The Type 1, length-15 filter impulse response is:

h 1 = - 0 . 5 0 1 . 1099 0 - 1 . 6039 0 4 . 494 7 4 . 494 0 - 1 . 6039 0 1 . 1099 0 - 0 . 5 h 1 = - 0 . 5 0 1 . 1099 0 - 1 . 6039 0 4 . 494 7 4 . 494 0 - 1 . 6039 0 1 . 1099 0 - 0 . 5 (26)

The amplitude frequency response and zero locations are shown in Fig Figure 1a

Figure 1: Frequency Responses and Zero Locations of Length-15 and 16 FIR Filters Designed by Frequency Sampling
fsFig1.png

We see a good lowpass filter frequency response with the actual amplitude interpolating the desired values at 8 equally spaced points. Notice there is considerable overshoot near the cutoff frequency. This is characteristic of frequency sampling designs and is a sort of “Gibbs phenomenon" but is even worse than that in a Fourier series expansion of a discontinuity. This Gibbs phenomenon could be reduced by using unequally spaced samples and designing by solving simultaneous equations. Imagine sampling in the pass and stop bands of