DESIGN OF FIR FILTERS BY DFT-BASED INTERPOLATION One approach to the design of FIR filters is to ask that A ω pass through a specified set of values. If the number of specified interpolation points is the same as the number of filter parameters, then the filter is totally determined by the interpolation conditions, and the filter can be found by solving a system of linear equations. When the interpolation points are equally spaced between 0 and 2 , then this interpolation problem can be solved very efficiently using the DFT. To derive the DFT solution to the interpolation problem, recall the formula relating the samples of the frequency response to the DFT. In the case we are interested here, the number of samples is to be the same as the length of the filter ( L N ). H 2 N k n 0 N 1 h n 2 N n k DFT N h n

Types I and II Recall the relation between A ω and H f ω for a Type I and II filter, to obtain A 2 N k H 2 N k M 2 N k DFT N h n W N M k Now we can related the N-point DFT of h n to the samples of A ω : DFT N h n A 2 N k W N − M k Finally, we can solve for the filter coefficients h n . h n DFT N A 2 N k W N − M k Therefore, if the values A 2 N k are specified, we can then obtain the filter coefficients h n that satisfies the interpolation conditions by using the inverse DFT. It is important to note however, that the specified values A 2 N k must possess the appropriate symmetry in order for the result of the inverse DFT to be a real Type I or II FIR filter.

Types III and IV For Type III and IV filters, we have A 2 N k H 2 N k M 2 N k DFT N h n W N M k Then we can related the N-point DFT of h n to the samples of A ω : DFT N h n A 2 N k W N M k Solving for the filter coefficients h n gives: h n DFT N A 2 N k W N − M k

EXAMPLE: DFT-INTERPOLATION (TYPE I) The following Matlab code fragment illustrates how to use this approach to design a length 11 Type I FIR filter for which k 0 k N 1 N 11 A 2 N k 1 1 1 0 0 0 0 0 0 1 1 .



	>> N = 11;
	>> M = (N-1)/2;
	>> Ak = [1 1 1 0 0 0 0 0 0 1 1};   % samples of A(w)
	>> k = 0:N-1;
	>> W = exp(j*2*pi/N);
	>> h = ifft(Ak.*W.^(-M*k));
	>> h'

	ans = 

	   0.0694 - 0.0000i
	  -0.0540 - 0.0000i
	  -0.1094 + 0.0000i
	   0.0474 + 0.0000i
	   0.3194 + 0.0000i
	   0.4545 + 0.0000i
	   0.3194 + 0.0000i
	   0.0474 + 0.0000i
	  -0.1094 + 0.0000i
	  -0.0540 - 0.0000i
	   0.0694 - 0.0000i

Observe that the filter coefficients h are real and symmetric; that a Type I filter is obtained as desired. The plot of A ω for this filter illustrates the interpolation points.



	L = 512;
	H = fft([h zeros(1,L-N)]);
	W = exp(j*2*pi/L);
	k = 0:L-1;
	A = H .* W.^(M*k);
	A = real(A);
	w = k*2*pi/L;
	plot(w/pi,A,2*[0:N-1]/N,Ak,'o')
	xlabel('\omega/\pi')
	title('A(\omega)')

An exercise for the student: develop this DFT-based interpolation approach for Type II, III, and IV FIR filters. Modify the Matlab code above for each case.

SUMMARY: IMPULSE AND AMP RESPONSE For an N-point linear-phase FIR filter h n , we summarize: The formulas for evaluating the amplitude response A ω at L equally spaced points from 0 to 2 ( L N ). The formulas for the DFT-based interpolation design of h n . TYPE I and II: A 2 L k DFT L h n 0 L - N W L M k h n DFT N A 2 N k W N − M k TYPE III and IV: A 2 L k DFT L h n 0 L - N W L M k h n DFT N A 2 N k W N − M k