Since samples of the frequency response of an FIR filter can be calculated by taking the DFT of the impulse response 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 , . Three methods for frequency sampling design are: 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) with reasonable behavior between sample response. This method works for general nonlinear phase design as well as for linear phase. 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. 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). This is done by h ( n ) = 1 N ∑ k = 0 N - 1 H d ( 2 π N k ) e j 2 π n k / N where care must be taken to insure that the real and imaginary parts (or magnitude and phase) of Hd(ωk) satisfy the symmetry conditions that give a real, causal h(n). This method will allow a general complex 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 () and (). 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) and/or linear phase and eliminate the problems of inconsistency in specifying 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(ω) has linear phase, () may be simplified using the formulas for the four types of linear-phase FIR filters.

Type 1. Odd Sampling Samples of the frequency response ()for the filter where N is odd, L=N, and M=(N-1)/2, and where there is a frequency sample at ω=0 is given as A k = ∑ n = 0 M - 1 2 h ( n ) cos ( 2 π ( M - n ) k / N ) + h ( M ) . Using the amplitude function A(ω), defined in (), of the form () and the IDFT () 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 or h ( n ) = 1 N ∑ k = 0 N - 1 A k e j 2 π ( n - M ) k / N . Because h(n) is real, Ak=AN-k and () becomes h ( n ) = 1 N [ A 0 + ∑ k = 1 M - 1 2 A k cos ( 2 π ( n - M ) k / N ) ] . Only M+1 of the h(n) need be calculated because of the symmetries in (). This formula calculates the impulse response values h(n) from the desired frequency samples Ak and requires M2 operations rather than N2. An interesting observation is that not only are () and () 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 N from () gives the amplitude frequency response samples as A k = ∑ n = 0 N / 2 - 1 2 h ( n ) cos ( 2 π ( M - n ) k / N ) 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 ) ] which is of the same form as (), except that the upper limit on the summation recognizes N as even and AN/2 equals zero.

Even Sampling The schemes just described use frequency samples at ω = 2 π k / N , k = 0 , 1 , 2 , . . . , N - 1 which are N equally-spaced samples starting at ω=0. Another possible pattern for frequency sampling that allows design formulas has no sample at ω=0, but uses N equally-spaced samples located at ω = ( 2 k + 1 ) π / N , k = 0 , 1 , 2 , . . . , N - 1 This form of frequency sampling is more difficult to relate to the DFT than the sampling of (), but it can be done by stretching Ak and taking a 2N-length DFT .

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 . For the case of an odd length and no zero sample, the analysis and design formulas are derived in a way analogous to () and () to give A k = ∑ n = 0 M - 1 2 h ( n ) cos ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) + h ( M ) 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 ) ]

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 ) and the design formula h ( n ) = 1 N [ ∑ k = 0 N / 2 - 1 2 A k cos ( 2 π ( n - M ) ( k + 1 / 2 ) / N ) ] These formulas in (), (), (), and () allow a very straightforward design of the four frequency-sampling cases. They and their analysis companions in (), (), (), and () 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 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 () are A k = ∑ b = 0 M - 1 2 h ( n ) sin ( 2 π ( M - n ) k / N ) and h ( n ) = 1 N [ ∑ k = 1 M 2 A k sin ( 2 π ( M - n ) k / N ) ]

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 ) 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 ) ) ] .

Type 3. Even Sampling Using the frequency sampling scheme of (), the Type 3 equations become A k = ∑ n = 0 M - 1 2 h ( n ) sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) and h ( n ) = 1 N [ ∑ k = 0 M - 1 2 A k sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) ]

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 ) and h ( n ) = 1 N [ ∑ k = 0 N / 2 - 1 2 A k sin ( 2 π ( M - n ) ( k + 1 / 2 ) / N ) ] . 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 .

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 () as A ( ω k ) = ∑ n = 0 M - 1 2 h ( n ) cos ω k ( M - n ) + h ( M ) or the reduced form from () as A ( ω k ) = ∑ n = 0 M a ( n ) cos ( ω k ( M - n ) ) where a ( n ) = { h(M) 0 2h(n) for n = M otherwise for 0 n M - 1 for k=0,1,2,...,M and solves the M+1 simultaneous equations for a(n) or equivalently, h(n). Indeed, this approach can be taken with general non-linear phase design fromIndeed, this approach can be taken with general non-linear phase design from H ( ω k ) = ∑ n = 0 N - 1 h ( n ) e j ω k n for k=0,1,2,⋯,N-1 which gives N equations with N 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) from calculated 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.35 normalized. Using the formulas (), (), (), and (), we got impulse responses h(n), which are use to generate the results shown in Figures and . 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 The amplitude frequency response and zero locations are shown in Fig a

Frequency Responses and Zero Locations of Length-15 and 16 FIR Filters Designed by Frequency Sampling 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 c 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 . 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.

Frequency Response and Zero Locations of FIR Filters Designed by Frequency Sampling