Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Digital Signal Processing and Digital Filter Design (Draft) » FIR Filter Design by Frequency Sampling or Interpolation

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Click the "Featured Content" link to see all content affiliated with them.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

FIR Filter Design by Frequency Sampling or Interpolation

Module by: C. Sidney Burrus. E-mail the author

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 [1], [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 Equation 28 from FIR Digital Filters and Equation 24 from FIR Digital Filters.

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 Equation 29 from FIR Digital Filters 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 Equation 28 from FIR Digital Filters, 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 Equation 27 from FIR Digital Filters.

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 Equation 36 from FIR Digital Filters 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 [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 the section Linear-Phase FIR Filters. 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 the section Linear-Phase FIR Filters 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 the section Discrete Frequency Samples of Error.

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 Equation 29 from FIR Digital Filters 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 Equation 37 from FIR Digital Filters 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 ) = { 2 h ( n ) for 0 n M - 1 h ( M ) for n = M 0 otherwise a ( n ) ={ 2 h ( n ) for 0 n M - 1 h ( M ) for n = M 0 otherwise
(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 Figure 1a

Figure 1: Frequency Responses and Zero Locations of Length-15 and 16 FIR Filters Designed by Frequency Sampling
This image consist of 4 sets of parallel graphs. The left column of graphs are frequency responses and the right column of graphs are Zero locations. For all of the left column graphs the x axis is labeled Normalized Frequency and the y axis is labeled Amplitude Response, A. For all of the right column of graphs the x axis labeled the real part of z and the y axis is labeled the Imaginary part of z. The first Row of graphs is labeled Type 1. Frequency sample with odd spacing. The graph on the left consist of a right angle formed by a line extending from the y axis at 1 to the right where in intersects a line rising from the x axis at about .3. There is also a wave form with smaller hollow circles at points along it. This line begins at the same point as the line from the y axis. This line falls below the line from the y axis and then goes above it and the takes a more negative slope before reaching the right angle formed by the two lines. The line falls below the x axis and then archs above and below the axis until it runs off the graph. The first graph in the right column consists of  circle centered at the origin, with 10 smaller hollow circles around the left two-thirds of the circumference of the circle, two inside the circle on the inner right and two outside and to the right of the larger circle. The second row of graphs is very similar to the first row; these graphs are labeled Type 2.Frequency samples with odd spacing. The left graph is the same as the first in this column except that the line forming the right angle are a little smaller which in turn causes the waveform to reach the x axis a little earlier than the first graph. The graph in the right column looks exactly the same as the first one in the right column except that there are 11 hollow circle along the circumference of the circle. The third row of graphs is similar to the other graphs, but these are labeled Type 1. Frequency Sample with even spacing. The lines forming the right angle are a little larger and the waveform line starts above the line extending out from the y axis. Also once the wave intersects the x axis the wave amplitude is much less pronounced and almost looks like a straight line. The graph in the right column looks the same as the previous ones in the column except that there are only 9 hollow circles on the circumference of the circle. The graphs on the fourth and final row look exactly the same as the previous row, except that the organization of the hollow circles on the graph on the right is a little different. There are 11 hollow circles around the circumference of the larger circle. The middle three are tighly compressed together on the far left of the circumference whereas the remaining four on both the top and bottom are spread out at equal distances from one another.

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 Figure 8c from FIR Digital Filters but not in the transitionband. The other responses and zero locations show the results of different interpolation locations and lengths. Note the zero at -1 for the even filters.

Examples of longer filters and of highpass and bandpass frequency sampling designs are shown in Figure 2. Note the difference of even and odd distributions of samples with with or without an interpolation point at zero frequency. Note the results of different ideal filters and Type 1 or 2. Also note the relationship of the amplitude response and zero locations.

Figure 2: Frequency Response and Zero Locations of FIR Filters Designed by Frequency Sampling
This image consist of 4 sets of parallel graphs. The left column of graphs are frequency responses and the right column of graphs are Zero locations. For all of the left column graphs the x axis is labeled Normalized Frequency and the y axis is labeled Amplitude Response, A. For all of the right column of graphs the x axis labeled the real part of z and the y axis is labeled the Imaginary part of z. The first row of graphs are labeled Type 1. Length-21 Lowpass FIR Filter. The graph on the left hand column is comprised of a right angle formed by a line extending for the y axis at 1 to the right and another line extending up from the x axis at around .3. The waveform starts at (0,1) proceeding with a slight curve upward above the top line of the right angle and then curves under the line and again above the line. After this last curve the wave takes on a negative slope just before reaching the corner of the right angle. The line then progresses down to the y axis curves down and then undulates above and below the axis until the form runs off the graph. The graph in the right hand column is comprised of a circle centered around the origin 14 hollow circles around the left hand side of circumference of the larger circle, three hollow circles on the right inside area of the larger circle, and also three hollow circles to the right side outside the larger circle. The second row labeled Type 2. Length-20 Lowpass FIR Filter is very similar to the first row. The graph in the left column is exactly the same except that the lines creating the right angle are larger and thus the waveform proceeds a little bit earlier than the previous graph. The graph in the right column looks exactly the same except that there are only 13 small hollow circles around the circumference. The third row is labeled Type 1. FIR Length-21 Highpass FIR Filter is exactly the same as the previous two except that the graphs appear to be reversed horizontally. The fourth row of graphs is labeled Type 2. Length-20 Bandpass FIR Filter and is completely different from the previous graphs. The graph on the left hand side consists of a box formed by a two lines extending up from the x axis around .2 and .6 and then a line between the tops of these lines at 1. The waveform begins on the x axis undulating above and below the axis and then the waveform takes on a positive slope and restarts its undulation on the line between the two vertical lines and then the wave takes on a negative slope at the end of the line between the  vertical lines and the waveform then returns back to the x axis where the undulation above and below the axis. The graph on the right column is also completely different. There is a circle centered around the origin. On the circumference of this circle there are 7 small hollow circles on the left side and then 5 small hollow circles on the right side of the circumference. There is another hollow circle to the just to the left of the origin. There are also two hollow circles present on the inside of the larger circle. The bottom circle is at the bottom inside of the circle a little to the right of the x=0 and then there is another circle there on the top inside of the circle. Outside the circle there are also two circles, one above or below the larger circle. These circles are present to the right of x=0.

References

  1. Parks, T. W. and Burrus, C. S. (1987). Digital Filter Design. New York: John Wiley & Sons.
  2. Smith, L. M. and Bomar, B. W. (1995). Least Squares and Related Techniques. In Chen, Wai-Kai (Ed.), The Circuits and Filters Handbook. (p. 2562–2572). Boca Raton: CRC Press and IEEE Press.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks