Editing Finite impulse response (section)

==Filter design==

FIR filters are designed by finding the coefficients and filter order that meet certain specifications, which can be in the time domain (e.g. a [[matched filter]]) or the frequency domain (most common).  Matched filters perform a cross-correlation between the input signal and a known pulse shape.  The FIR convolution is a cross-correlation between the input signal and a time-reversed copy of the impulse response.  Therefore, the matched filter's impulse response is "designed" by sampling the known pulse-shape and using those samples in reverse order as the coefficients of the filter.<ref>Oppenheim, Alan V., Willsky, Alan S., and Young, Ian T.,1983: Signals and Systems, p. 256 (Englewood Cliffs, New Jersey: Prentice-Hall, Inc.)  {{ISBN|0-13-809731-3}}</ref>

When a particular frequency response is desired, several different design methods are common:
# [[#Window design method|Window design method]]
# Frequency sampling method
# Least MSE (mean square error) method
# [[Parks–McClellan method]] (also known as the equiripple, optimal, or minimax method).  The [[Remez algorithm|Remez exchange algorithm]] is commonly used to find an optimal equiripple set of coefficients.  Here the user specifies a desired frequency response, a weighting function for errors from this response, and a filter order ''N''.  The algorithm then finds the set of <math display="inline"> N + 1</math> coefficients that minimize the maximum deviation from the ideal.  Intuitively, this finds the filter that is as close as possible to the desired response given that only <math display="inline"> N + 1</math> coefficients can be used.  This method is particularly easy in practice since at least one text<ref>Rabiner, Lawrence R., and Gold, Bernard, 1975: Theory and Application of Digital Signal Processing (Englewood Cliffs, New Jersey: Prentice-Hall, Inc.)  {{ISBN|0-13-914101-4}}</ref> includes a program that takes the desired filter and ''N'', and returns the optimum coefficients.
# Equiripple FIR filters can be designed using the DFT algorithms as well.<ref>A. E. Cetin, O.N. Gerek, Y. Yardimci, "Equiripple FIR filter design by the FFT algorithm," IEEE Signal Processing Magazine, pp. 60–64, March 1997.</ref> The algorithm is iterative in nature. The DFT of an initial filter design is computed using the FFT algorithm (if an initial estimate is not available, h[n]=delta[n] can be used). In the Fourier domain, or DFT domain, the frequency response is corrected according to the desired specs, and the inverse DFT is then computed. In the time-domain, only the first N coefficients are kept (the other coefficients are set to zero). The process is then repeated iteratively: the DFT is computed once again, correction applied in the frequency domain and so on.

Software packages such as [[MATLAB]], [[GNU Octave]], [[Scilab]], and [[SciPy]] provide convenient ways to apply these different methods.

=== Window design method ===

In the window design method, one first designs an ideal IIR filter and then truncates the infinite impulse response by multiplying it with a finite length [[window function]]. The result is a finite impulse response filter whose frequency response is modified from that of the IIR filter. Multiplying the infinite impulse by the window function in the time domain results in the frequency response of the IIR being [[convolved]] with the Fourier transform (or DTFT) of the window function. If the window's main lobe is narrow, the composite frequency response remains close to that of the ideal IIR filter.

The ideal response is often rectangular, and the corresponding IIR is a [[sinc function]].  The result of the frequency domain convolution is that the edges of the rectangle are tapered, and ripples appear in the passband and stopband.  Working backward, one can specify the slope (or width) of the tapered region (''[[transition band]]'') and the height of the ripples, and thereby derive the frequency-domain parameters of an appropriate window function.  Continuing backward to an impulse response can be done by iterating a filter design program to find the minimum filter order.  Another method is to restrict the solution set to the parametric family of [[Kaiser window]]s, which provides closed form relationships between the time-domain and frequency domain parameters.  In general, that method will not achieve the minimum possible filter order, but it is particularly convenient for automated applications that require dynamic, on-the-fly, filter design.

The window design method is also advantageous for creating efficient [[half-band filter]]s, because the corresponding sinc function is zero at every other sample point (except the center one).  The product with the window function does not alter the zeros, so almost half of the coefficients of the final impulse response are zero.  An appropriate implementation of the FIR calculations can exploit that property to double the filter's efficiency.

=== Least mean square error (MSE) method ===
'''Goal:'''
:To design FIR filter in the MSE sense, we minimize the mean square error between the filter we obtained and the desired filter.
::<math>\text{MSE}=f_s^{-1} \int_{-f_s/2}^{f_s/2} |H(f)-H_d(f)|^2\,df </math> , where <math>f_s\,</math> is sampling frequency, <math>H(f)\,</math> is the spectrum of the filter we obtained, and  <math>H_d(f)\,</math> is the spectrum of the desired filter.

'''Method:'''
:Given an ''N''-point FIR filter <math> h[n] </math>, and <math>r[n] = h[n+k], k = \frac{(N-1)}{2}</math>.
:Step 1: Suppose <math> h[n] </math>even symmetric. Then, the discrete time Fourier transform of <math>r[n]</math> is defined as 
::<math>R(F) = e^{j2 \pi Fk}H(F) = \sum_{n=0}^k s[n] \cos (2 \pi nF) </math> 
:Step 2: Calculate mean square error.
::<math>\text{MSE}=\int_{-1/2}^{1/2} |R(F)-H_d(F)|^2\,dF </math>
::Therefore,
::<math>\text{MSE}= \int_{-1/2}^{1/2} \sum_{n=0}^k s[n] \cos (2 \pi nF) \sum_{\tau=0}^k s[\tau] \cos (2 \pi \tau F)\,dF -2\int_{-1/2}^{1/2} \sum_{n=0}^k s[n] \cos (2 \pi nF) H_d\,dF + \int_{-1/2}^{1/2} H_d(F)^2\,dF</math> 
:Step 3: Minimize the mean square error by doing partial derivative of MSE with respect to <math>s[n]</math>
::<math> \frac{\partial \text{MSE}}{\partial s[n]} = 2\sum_{\tau=0}^k s[\tau]  \int_{-1/2}^{1/2} \cos (2 \pi nF) \cos (2 \pi \tau F) \,dF - 2\int_{-1/2}^{1/2} H_d(F)^2 \cos (2 \pi nF)\,dF = 0</math>
::After organization, we have
::<math> s[0] = \int_{-1/2}^{1/2} H_d(F)\, dF </math>
::<math> s[n] = \int_{-1/2}^{1/2} \cos (2 \pi nF) H_d(F) \,dF, \ \text{ for } n \ne 0</math> 
:Step 4: Change <math> s[n] </math> back to the presentation of <math> h[n] </math>
::<math>h[k] = s[0], h[k+n] = s[n]/2, h[k-n]=s[n]/2, \; for \; n=1,2,3, \ldots, k, \text{ where } k = (N-1)/2 </math> and <math> h[n] =0 \text{ for } n < 0 \text{ and } n \ge N</math>

In addition, we can treat the importance of passband and stopband differently according to our needs by adding a weighted function, <math>W(f)</math>
Then, the MSE error becomes
:<math> \text{MSE} =\int_{-1/2}^{1/2} W(F)|R(F)-H_d(F)|^2\,dF </math>