Finite impulse response

Short description: Type of filter in signal processing

In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response (or response to any finite length input) is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response (IIR) filters, which may have internal feedback and may continue to respond indefinitely (usually decaying).

The impulse response (that is, the output in response to a Kronecker delta input) of an N^th-order discrete-time FIR filter lasts exactly [math]\displaystyle{ N+1 }[/math] samples (from first nonzero element through last nonzero element) before it then settles to zero.

FIR filters can be discrete-time or continuous-time, and digital or analog.

Definition

A direct form discrete-time FIR filter of order N. The top part is an N-stage delay line with N + 1 taps. Each unit delay is a z⁻¹ operator in Z-transform notation.

A lattice-form discrete-time FIR filter of order N. Each unit delay is a z⁻¹ operator in Z-transform notation.

For a causal discrete-time FIR filter of order N, each value of the output sequence is a weighted sum of the most recent input values:

[math]\displaystyle{ \begin{align} y[n] &= b_0 x[n] + b_1 x[n-1] + \cdots + b_N x[n-N] \\ &= \sum_{i=0}^N b_i\cdot x[n-i], \end{align} }[/math]

where:

• [math]\displaystyle{ x[n] }[/math] is the input signal,
• [math]\displaystyle{ y[n] }[/math] is the output signal,
• [math]\displaystyle{ N }[/math] is the filter order; an [math]\displaystyle{ N }[/math]^th-order filter has [math]\displaystyle{ N + 1 }[/math] terms on the right-hand side
• [math]\displaystyle{ b_i }[/math] is the value of the impulse response at the i'th instant for [math]\displaystyle{ 0 \le i \le N }[/math] of an [math]\displaystyle{ N^\text{th} }[/math]-order FIR filter. If the filter is a direct form FIR filter then [math]\displaystyle{ b_i }[/math] is also a coefficient of the filter.

This computation is also known as discrete convolution.

The [math]\displaystyle{ x[n-i] }[/math] in these terms are commonly referred to as taps, based on the structure of a tapped delay line that in many implementations or block diagrams provides the delayed inputs to the multiplication operations. One may speak of a 5th order/6-tap filter, for instance.

The impulse response of the filter as defined is nonzero over a finite duration. Including zeros, the impulse response is the infinite sequence:

[math]\displaystyle{ h[n] = \sum_{i=0}^N b_i\cdot \delta[n-i] = \begin{cases} b_n & 0 \le n \le N\\ 0 & \text{otherwise}. \end{cases} }[/math]

If an FIR filter is non-causal, the range of nonzero values in its impulse response can start before [math]\displaystyle{ n=0 }[/math], with the defining formula appropriately generalized.

Properties

An FIR filter has a number of useful properties which sometimes make it preferable to an infinite impulse response (IIR) filter. FIR filters:

• Require no feedback. This means that any rounding errors are not compounded by summed iterations. The same relative error occurs in each calculation. This also makes implementation simpler.
• Are inherently stable, since the output is a sum of a finite number of finite multiples of the input values, so can be no greater than [math]\displaystyle{ \sum |b_i| }[/math] times the largest value appearing in the input.
• Can easily be designed to be linear phase by making the coefficient sequence symmetric. This property is sometimes desired for phase-sensitive applications, for example data communications, seismology, crossover filters, and mastering.

The main disadvantage of FIR filters is that considerably more computation power in a general purpose processor is required compared to an IIR filter with similar sharpness or selectivity, especially when low frequency (relative to the sample rate) cutoffs are needed. However, many digital signal processors provide specialized hardware features to make FIR filters approximately as efficient as IIR for many applications.

Frequency response

The filter's effect on the sequence [math]\displaystyle{ x[n] }[/math] is described in the frequency domain by the convolution theorem:

[math]\displaystyle{ \underbrace{\mathcal{F}\{x*h\}}_{Y(\omega)} = \underbrace{\mathcal{F}\{x\}}_{X(\omega)} \cdot \underbrace{\mathcal{F}\{h\}}_{H(\omega)} }[/math]     and     [math]\displaystyle{ y[n] = x[n]*h[n]= \mathcal{F}^{-1}\big\{X(\omega)\cdot H(\omega)\big\}, }[/math]

where operators [math]\displaystyle{ \mathcal{F} }[/math] and [math]\displaystyle{ \mathcal{F}^{-1} }[/math] respectively denote the discrete-time Fourier transform (DTFT) and its inverse. Therefore, the complex-valued, multiplicative function [math]\displaystyle{ H(\omega) }[/math] is the filter's frequency response. It is defined by a Fourier series:

[math]\displaystyle{ H_{2\pi}(\omega)\ \triangleq \sum_{n=-\infty}^{\infty} h[n]\cdot \left({e^{i \omega}}\right)^{-n} = \sum_{n=0}^{N}b_n\cdot \left({e^{i \omega}}\right)^{-n}, }[/math]

where the added subscript denotes 2π-periodicity. Here [math]\displaystyle{ \omega }[/math] represents frequency in normalized units (radians/sample). The substitution [math]\displaystyle{ \omega = 2\pi f, }[/math] favored by many filter design programs, changes the units of frequency [math]\displaystyle{ (f) }[/math] to cycles/sample and the periodicity to 1. When the x[n] sequence has a known sampling-rate, [math]\displaystyle{ f_s }[/math] samples/second, the substitution [math]\displaystyle{ \omega = 2\pi f/f_s }[/math] changes the units of frequency [math]\displaystyle{ (f) }[/math] to cycles/second (hertz) and the periodicity to [math]\displaystyle{ f_s. }[/math] The value [math]\displaystyle{ \omega = \pi }[/math] corresponds to a frequency of [math]\displaystyle{ f = \tfrac{f_s}{2} }[/math] Hz [math]\displaystyle{ = \tfrac{1}{2} }[/math] cycles/sample, which is the Nyquist frequency.

[math]\displaystyle{ H_{2\pi}(\omega) }[/math] can also be expressed in terms of the Z-transform of the filter impulse response:

[math]\displaystyle{ \widehat H(z)\ \triangleq \sum_{n=-\infty}^{\infty} h[n]\cdot z^{-n}. }[/math]

[math]\displaystyle{ H_{2\pi}(\omega) = \left. \widehat H(z) \, \right|_{z = e^{j \omega}} = \widehat H(e^{j \omega}). }[/math]

Filter design

An FIR filter is designed by finding the coefficients and filter order that meet certain specifications, which can be in the time domain (e.g. a matched filter) and/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.

When a particular frequency response is desired, several different design methods are common:

1. Window design method
2. Frequency sampling method
3. Least MSE (mean square error) method
4. Parks–McClellan method (also known as the equiripple, optimal, or minimax method). The 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]\displaystyle{ 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]\displaystyle{ N + 1 }[/math] coefficients can be used. This method is particularly easy in practice since at least one text includes a program that takes the desired filter and N, and returns the optimum coefficients.
5. Equiripple FIR filters can be designed using the DFT algorithms as well. 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 windows, 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 filters, 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]\displaystyle{ \text{MSE}=f_s^{-1} \int_{-f_s/2}^{f_s/2} |H(f)-H_d(f)|^2\,df }[/math] , where [math]\displaystyle{ f_s\, }[/math] is sampling frequency, [math]\displaystyle{ H(f)\, }[/math] is the spectrum of the filter we obtained, and [math]\displaystyle{ H_d(f)\, }[/math] is the spectrum of the desired filter.

Method:

Given an N-point FIR filter [math]\displaystyle{ h[n] }[/math], and [math]\displaystyle{ r[n] = h[n+k], k = \frac{(N-1)}{2} }[/math].

Step 1: Suppose [math]\displaystyle{ h[n] }[/math]even symmetric. Then, the discrete time Fourier transform of [math]\displaystyle{ r[n] }[/math] is defined as

[math]\displaystyle{ 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]\displaystyle{ \text{MSE}=\int_{-1/2}^{1/2} |R(F)-H_d(F)|^2\,dF }[/math]

Therefore,

[math]\displaystyle{ \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]\displaystyle{ s[n] }[/math]

[math]\displaystyle{ \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]\displaystyle{ s[0] = \int_{-1/2}^{1/2} H_d(F)\, dF }[/math]

[math]\displaystyle{ 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]\displaystyle{ s[n] }[/math] back to the presentation of [math]\displaystyle{ h[n] }[/math]

[math]\displaystyle{ 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]\displaystyle{ h[n] =0 \text{ for } n \lt 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]\displaystyle{ W(f) }[/math] Then, the MSE error becomes

[math]\displaystyle{ \text{MSE} =\int_{-1/2}^{1/2} W(F)|R(F)-H_d(F)|^2\,dF }[/math]

Moving average example

Block diagram of a simple FIR filter (second-order/3-tap filter in this case, implementing a moving average smoothing filter)

Pole–zero diagram of the example second-order FIR smoothing filter

Magnitude and phase responses of the example second-order FIR smoothing filter

Amplitude and phase responses of the example second-order FIR smoothing filter

A moving average filter is a very simple FIR filter. It is sometimes called a boxcar filter, especially when followed by decimation, or a sinc-in-frequency. The filter coefficients, [math]\displaystyle{ b_0, \ldots, b_N }[/math], are found via the following equation:

[math]\displaystyle{ b_i=\frac{1}{N+1} }[/math]

To provide a more specific example, we select the filter order:

[math]\displaystyle{ N = 2 }[/math]

The impulse response of the resulting filter is:

[math]\displaystyle{ h[n] = \frac{1}{3}\delta[n] + \frac{1}{3}\delta[n-1] + \frac{1}{3}\delta[n-2] }[/math]

The block diagram on the right shows the second-order moving-average filter discussed below. The transfer function is:

[math]\displaystyle{ H(z) = \frac{1}{3} + \frac{1}{3}z^{-1} + \frac{1}{3}z^{-2} = \frac{1}{3}\frac{z^{2} + z + 1}{z^{2}}. }[/math]

The next figure shows the corresponding pole–zero diagram. Zero frequency (DC) corresponds to (1, 0), positive frequencies advancing counterclockwise around the circle to the Nyquist frequency at (−1, 0). Two poles are located at the origin, and two zeros are located at [math]\displaystyle{ z_1 = -\frac{1}{2} + j\frac{\sqrt{3}}{2} }[/math], [math]\displaystyle{ z_2 = -\frac{1}{2} - j \frac{\sqrt{3}}{2} }[/math].

The frequency response, in terms of normalized frequency ω, is:

[math]\displaystyle{ \begin{align} H\left(e^{j\omega}\right) &= \frac{1}{3} + \frac{1}{3}e^{-j\omega} + \frac{1}{3}e^{-j2\omega}\\ &= \frac{1}{3}e^{-j\omega}\left(1+2\cos(\omega)\right). \end{align} }[/math]

The magnitude and phase components of [math]\displaystyle{ H\left(e^{j\omega}\right) }[/math] are plotted in the figure. But plots like these can also be generated by doing a discrete Fourier transform (DFT) of the impulse response. And because of symmetry, filter design or viewing software often displays only the [0, π] region. The magnitude plot indicates that the moving-average filter passes low frequencies with a gain near 1 and attenuates high frequencies, and is thus a crude low-pass filter. The phase plot is linear except for discontinuities at the two frequencies where the magnitude goes to zero. The size of the discontinuities is π, representing a sign reversal. They do not affect the property of linear phase, as illustrated in the final figure.

See also

• Electronic filter
• Filter (signal processing)
• Infinite impulse response (IIR) filter
• Z-transform (specifically Linear constant-coefficient difference equation)
• FIR transfer function
• Filter design
• Cascaded integrator–comb filter
• Compact support