There are two types of linear, time-invariant digital filters. We will investigate digital filters with a finite-duration impulse response (FIR) in this section and those with an infinite-duration impulse response (IIR) in another document. FIR filters have characteristics that make them useful in many applications , . FIR filters can achieve an exactly linear phase frequency response FIR filters cannot be unstable. FIR filters are generally less sensitive to coefficient round-off and finite-precision arithmetic than IIR filters. FIR filters design methods are generally linear. FIR filters can be efficiently realized on general or special-purpose hardware. However, frequency responses that need a rapid transition between bands and do not require linear phase are often more efficiently realized with IIR filters. It is the purpose of this section to examine and evaluate these characteristics which are important in the design of the four basic types of linear-phase FIR filters. Because of the usual methods of implementation, the Finite Impulse Response (FIR) filter is also called a nonrecursive filter or a convolution filter. From the time-domain view of this operation, the FIR filter is sometimes called a moving-average or running-average filter. All of these names represent useful interpretations that are discussed in this section; however, the name, FIR, is most commonly seen in filter-design literature and is used in these notes. The duration or sequence length of the impulse response of these filters is by definition finite; therefore, the output can be written as a finite convolution sum by y ( n ) = ∑ m = 0 N - 1 h ( m ) x ( n - m ) where n and m are integers, perhaps representing samples in time, and where x(n) is the input sequence, y(n) the output sequence, and h(n) is the length-N impulse response of the filter. With a change of index variables, this can also be written as y ( n ) = ∑ m = n n - N + 1 h ( n - m ) x ( m ) . If the FIR filter is interpreted as an extension of a moving sum or as a weighted moving average, some of its properties can easily be seen. If one has a sequence of numbers, e.g., prices from the daily stock market for a particular stock, and would like to remove the erratic variations in order to discover longer term trends, each number could be replaced by the average of itself and the preceding three numbers, i.e., the variations within a four-day period would be “averaged out" while the longer-term variations would remain. To illustrate how this happens, consider an artificial signal x(n) containing a linear term, K1n, and an undesired oscillating term added to it, such that x ( n ) = K 1 n + K 2 cos ( π n ) If a length-2 averaging filter is used with h ( n ) = 1 / 2 for n = 0 , 1 0 otherwise it can be verified that, after two outputs, the output y(n) is exactly the linear term x(n) with a delay of one half sample interval and no oscillation. This example illustrates the basic FIR filter-design problem: determine N, the number of terms for h(n), and the values of h(n) for achieving a desired effect on the signal. The reader should examine simple examples to obtain an intuitive idea of the FIR filter as a moving average; however, this simple time-domain interpretation will not suffice for complicated problems where the concept of frequency becomes more valuable.

Frequency-Domain Description of FIR Filters The output of a length-N FIR filter can be calculated from the input using convolution. y ( n ) = ∑ k = 0 N - 1 h ( k ) x ( n - k ) and the transfer function of an FIR filter is given by the z-transform of the finite length impulse response h(n) as H ( z ) = ∑ n = 0 N - 1 h ( n ) z - n . The frequency response of a filter, is found by setting z=ejω, which is the same as the discrete-time Fourier transform (DTFT) of h(n), which gives H ( ω ) = ∑ n = 0 N - 1 h ( n ) e - j ω n with ω being frequency in radians per second. Strictly speaking, the exponent should be -jωTn where T is the time interval between the integer steps of n (the sampling interval). But to simplify notation, it will be assumed that T=1 until later in the notes where the relation between n and time is more important. Also to simplify notation, H(ω) is used to represent the frequency response rather that H(ejω). It should always be clear from the context whether H is a function of z or ω. This frequency-response function is complex-valued and consists of a magnitude and a phase. Even though the impulse response is a function of the discrete variable n, the frequency response is a function of the continuous-frequency variable ω and is periodic with period 2π. This periodicity is easily shown by H ( w + 2 π ) = ∑ n = 0 N - 1 h ( n ) e - j ( w + 2 π ) n = ∑ n = 0 N - 1 h ( n ) e - j ω n e - j 2 π n = H ( ω ) with frequency denoted by ω in radians per second or by f in Hz (hertz or cycles per second). These are related by ω = 2 π f An example of a length-5 filter might be h ( n ) = 2 , 3 , 4 , 3 , 2 with a frequency-response plot shown over the base frequency band (0<ω<π or 0<f<1 in . To illustrate the periodic nature of the total frequency response, shows the response over a wider set of frequencies.

Frequency Response of Example Filter

Frequency Response of Example Filter over a wide band of frequencies The Discrete Fourier Transform (DFT) can be used to evaluate the frequency response at certain frequencies. The DFT of the length-N impulse response h(n) is defined as C ( k ) = ∑ n = 0 N - 1 h ( n ) e - j 2 π n k / N k = 0 , 1 , . . . , N - 1 which, when compared to (), gives C ( k ) = H ( ω k ) = H ( 2 π k / N ) k = 0 , 1 , . . . , N - 1 for ωk=2πk/N. This states that the DFT of h(n) gives N samples of the frequency-response function H(ω). This sampling at N points may not give enough detail, and, therefore, more samples are needed. Any number of equally spaced samples can be found with the DFT by simply appending L-N zeros to h(n) and taking an L-length DFT. This is often useful when an accurate picture of all of H(ω) is required. Indeed, when the number of appended zeros goes to infinity, the DFT becomes the discrete-time Fourier transform of h(n). The fact that the DFT of h(n) is a set of N samples of the frequency response suggests a method of designing FIR filters in which the inverse DFT of N samples of a desired frequency response gives the filter coefficients h(n). That approach is called frequency sampling and is developed in another section.

Linear-Phase FIR Filters A particular property of FIR filters that has proven to be very powerful is that a linear phase shift for the frequency response is possible. This is especially important to time domain details of a signal. The spectrum of a signal contains the individual frequency domain components separated in frequency. The process of filtering usually involves passing some of these components and rejecting others. This is done by multiplying the desired ones by one and the undesired ones by zero. When they are recombined, it is important that the components have the same time domain alignment as they originally did. That is exactly what linear phase insures. A phase response that is linear with frequency keeps all of the frequency components properly registered with each other. That is especially important in seismic, radar, and sonar signal analysis as well as for many medical signals where the relative time locations of events contains the information of interest. To develop the theory for linear phase FIR filters, a careful definition of phase shift is necessary. If the real and imaginary parts of H(ω) are given by H ( ω ) = R ( ω ) + j I ( ω ) where j=-1 and the magnitude is defined by | H ( ω ) | = R 2 + I 2 and the phase by Φ ( ω ) = arctan ( I / R ) which gives H ( ω ) = | H ( ω ) | e j Φ ( ω ) in terms of the magnitude and phase. Using the real and imaginary parts is using a rectangular coordinate system and using the magnitude and phase is using a polar coordinate system. Often, the polar system is easier to interpret. Mathematical problems arise from using |H(ω)| and Φ(ω), because |H(ω)| is not analytic and Φ(ω) not continuous. This problem is solved by introducing an amplitude function A(ω) that is real valued and may be positive or negative. The frequency response is written as H ( ω ) = A ( ω ) e j Θ ( ω ) where A(ω) is called the amplitude in order to distinguish it from the magnitude |H(ω)|, and Θ(ω) is the continuous version of Φ(ω). A(ω) is a real, analytic function that is related to the magnitude by A ( ω ) = ± | H ( ω ) | or | A ( ω ) | = | H ( ω ) | With this definition, A(ω) can be made analytic and Θ(ω) continuous. These are much easier to work with than |H(ω)| and Φ(ω). The relationship of A(ω) and |H(ω)|, and of Θ(ω) and Φ(ω) are shown in .

Magnitude and Amplitude Frequency Responses and Corresponding Phase Frequency Response of Example Filter To develop the characteristics and properties of linear-phase filters, assume a general linear plus constant form for the phase function as Θ ( ω ) = K 1 + K 2 ω This gives the frequency response function of a length-N FIR filter as H ( ω ) = ∑ n = 0 N - 1 h ( n ) e - j ω n = e - j ω M ∑ n = 0 N - 1 h ( n ) e j ω ( M - n ) and H ( ω ) = e - j ω M [ h 0 e j ω M + h 1 e j ω ( M - 1 ) + ⋯ + h N - 1 e j ω ( M - N + 1 ) ] can be put in the form of H ( ω ) = A ( ω ) e j ( K 1 + K 2 ω ) if M (not necessarily an integer) is defined by M = N - 1 2 or equivalently, M = N - M - 1 then becomes H ( ω ) = e - j ω M [ ( h 0 + h N - 1 ) cos ( ω M ) + j ( h 0 - h N - 1 ) sin ( ω M ) + ( h 1 + h N - 2 ) cos ( ω ( M - 1 ) ) + j ( h 1 - h N - 2 ) sin ( w ( M - 1 ) ) + ⋯ ] There are two possibilities for putting this in the form of () where A(ω) is real: K1=0 or K1=π/2. The first case requires a special even symmetry in h(n) of the form h ( n ) = h ( N - n - 1 ) which gives H ( ω ) = A ( ω ) e - j M ω where A(ω) is the amplitude, a real-valued function of ω and e-jMω gives the linear phase with M being the group delay. For the case where N is odd, using (), (), and (), we have A ( ω ) = ∑ n = 0 M - 1 2 h ( n ) cos ω ( M - n ) + h ( M ) or with a change of variables, A ( ω ) = ∑ n = 1 M 2 h ( M - n ) cos ( ω n ) + h ( M ) which becomes A ( ω ) = ∑ n = 1 M 2 h ^ ( n ) cos ( ω n ) + h ( M ) where h^(n)=h(M-n) is a shifted h(n). These formulas can be made simpler by defining new coefficients so that () becomes A ( ω ) = ∑ n = 0 M a ( n ) cos ( ω ( M - n ) ) where a ( n ) = { h(M) 0 2h(n) for n = M otherwise for 0 n M - 1 and becomes A ( ω ) = ∑ n = 0 M a ( n ) cos ( ω n ) with a ( n ) = { 2h(M+n) 0 h(M) for 0 n M - 1 otherwise for n = 0 Notice from () for N odd, A(ω) is an even function around ω=0 and ω=π, and is periodic with period 2π. For the case where N is even, A ( ω ) = ∑ n = 0 N / 2 - 1 2 h ( n ) cos ω ( M - n ) or with a change of variables, A ( ω ) = ∑ n = 1 N / 2 2 h ( N / 2 - n ) cos ω ( n - 1 / 2 ) These formulas can also be made simpler by defining new coefficients so that () becomes A ( ω ) = ∑ n = 0 N / 2 - 1 a ( n ) cos ( ω ( M - n ) ) where a ( n ) = { 0 otherwise 2 h ( n ) for 0 n N / 2 - 1 and () becomes A ( ω ) = ∑ n = 1 N / 2 a ( n ) cos ( ω ( n - 1 / 2 ) ) with a ( n ) = { 0 otherwise 2 h ( N / 2 - n ) for 1 ≤ n ≤ N / 2 Notice from for N even, A(ω) is an even function around ω=0, an odd function around ω=π, and is periodic with period 4π. This requires A(π)=0.For the case in () where K1=π/2, an odd symmetry is required of the form h ( n ) = - h ( N - n - 1 ) which, for N odd, gives H ( ω ) = j A ( ω ) e j M ω with A ( ω ) = ∑ n = 0 M - 1 2 h ( n ) sin ω ( M - n ) and for N even A ( ω ) = ∑ n = 0 N / 2 - 1 2 h ( n ) sin ω ( M - n ) To calculate the frequency or amplitude response numerically, one must consider samples of the continuous frequency response function above. L samples of the general complex frequency response H(ω) in are calculated from H ( ω k ) = ∑ n = 0 N - 1 h ( n ) e - j ω k n . for k=0,1,2,⋯,L-1. This can be written with matrix notation as H = F h where H is an L by 1 vector of the samples of the complex frequency response, F is the L by N matrix of complex exponentials from (), and h is the N by 1 vector of real filter coefficients. These equations are possibly redundant for equally spaced samples since A(ω) is an even function and, if the phase response is linear, h(n) is symmetric. These redundancies are removed by sampling () over 0≤ωk≤π and by using a defined in () rather than h. This can be written A = C a where A is an L by 1 vector of the samples of the real valued amplitude frequency response, C is the L by M real matrix of cosines from (), and a is the M by 1 vector of filter coefficients related to the impulse response by (). A similar set of equations can be written from () for N odd or from () for N even. This formulation becomes a filter design method by giving the samples of a desired amplitude response as Ad(k) and solving () for the filter coefficients a(n). If the number of independent frequency samples is equal to the number of independent filter coefficients and if C is not singular, this is the frequency sampling filter design method and the frequency response of the designed filter will interpolate the specified samples. If the number of frequency samples L is larger than the number of filter coefficients N, () may be solved approximately by minimizing the norm ∥A(ω)-Ad(ω)∥.

The Discrete Time Fourier Transform with Normalization The discrete time Fourier transform of the impulse response of a digital filter is its frequency response, therefore, it is an important tool. When the symmetry conditions of linear phase are incorporated into the DTFT, it becomes similar to the discrete cosine or sine transform (DCT or DST). It also has an arbitrary normalization possible for the odd length that needs to be understood. The discrete time Fourier transform (DTFT) is defined in () which, with the conditions of an odd length-N symmetrical signal, becomes A ( ω ) = ∑ n = 1 M a ( n ) cos ( ω n ) + K a ( 0 ) where M=(N-1)/2. Its inverse as a ( n ) = 2 π ∫ 0 π A ( ω ) cos ( ω n ) d ω for n=1,2,⋯,M and a ( 0 ) = 1 K π ∫ 0 π A ( ω ) d ω where K is a parameter of normalization for the a(0) term with 0<K<∞. If K=1, the expansion equation () is one summation and doesn't have to have the separate term for a(0). If K=1/2, the equation for the coefficients () will also calculate the a(0) term and the separate equation () is not needed. If K=1/2, a symmetry results which simplifies equations later in the notes.

Four Types of Linear-Phase FIR Filters From the previous discussion, it is seen that there are four possible types of FIR filters [1] that lead to the linear phase of (). These are summarized in . Type 1. The impulse response has an odd length and is even symmetric about its midpoint of n=M=(N-1)/2 which requires h(n)=h(N-n-1) and gives () and (). Type 2. The impulse response has an even length and is even symmetric about M, but M is not an integer. Therefore, there is no h(n) at the point of symmetry, but it satisfies () and (). Type 3. The impulse response has an odd length as for Type 1 and has the odd symmetry of (), giving an imaginary multiplier for the linear-phase form in () with amplitude (). Type 4. The impulse response has an even length as for Type 2 and the odd symmetry of Type 3 in () and () with amplitude ().

Examples of the four types of linear-phase FIR filters with the symmetries for odd and even length are shown in . Note that for N odd and h(n) odd symmetric, h(M)=0.

Example of Impulse Responses for the Four Types of Linear Phase FIR Filters For the analysis or design of linear-phase FIR filters, it is necessary to know the characteristics of A(ω). The most important characteristics are shown in . 0.0pt7.11317pt12.80374pt TYPE 1. Odd length, even symmetric h(n) A(ω) is even about ω=0 A ( ω ) = A ( - ω ) A(ω) is even about ω=π A ( π + ω ) = A ( π - ω ) A(ω) is periodic with period = 2π A ( ω + 2 π ) = A ( ω ) 0.0pt7.11317pt12.80374pt TYPE 2. Even length, even symmetric h(n) A(ω) is even about ω=0 A ( ω ) = A ( - ω ) A(ω) is odd about ω=π A ( π + ω ) = - A ( π - ω ) A(ω) is periodic with period 4π A ( ω + 4 π ) = A ( ω ) 0.0pt7.11317pt12.80374pt TYPE 3. Odd length, odd symmetric h(n) A(ω) is odd about ω=0 A ( ω ) = - A ( - ω ) A(ω) is odd about ω=π A ( π + ω ) = - A ( π - ω ) A(ω) is periodic with period =2π A ( ω + 2 π ) = A ( ω ) 0.0pt7.11317pt12.80374pt TYPE 4. Even length, odd symmetric h(n) A(ω) is odd about ω=0 A ( ω ) = - A ( - ω ) A(ω) is even about ω=π A ( π + ω ) = A ( π - ω ) A(ω) is periodic with period =4π A ( ω + 4 π ) = A ( ω )

Examples of the amplitude function for odd and even length linear-phase filter A(ω) are shown in .

Example of Amplitude Responses for the Four Types of Linear Phase FIR Filters These characteristics reveal several inherent features that are extremely important to filter design. For Types 3 and 4, A(0)=0 for any choice of filter coefficients h(n). This would not be desirable for a lowpass filter. Types 2 and 3 always have A(π)=0 which is not desirable for a highpass filter. In addition to the linear-phase characteristic that represents a time shift, Types 3 and 4 give a constant 90-degree phase shift, desirable for a differentiator or Hilbert transformer. The first step in the design of a linear-phase FIR filter is the choice of the type most compatible with the specifications. It is possible to uses the formulas to express the frequency response of a general complex or non-linear phase FIR filter by taking the even and odd parts of h(n) and calculating a real and imaginary “amplitude" that would be added to give the actual frequency response.

Calculation of FIR Filter Frequency Response As shown earlier, L equally spaced samples of H(ω) are easily calculated for L>N by appending L-N zeros to h(n) for a length-L DFT. This appears as H ( 2 π k / L ) = DFT { h ( n ) } for k = 0 , 1 , ⋯ , L - 1 This direct method of calculation is a straightforward and flexible approach. Only the samples of H(ω) that are of interest need to be calculated. In fact, even nonuniform spacing of the frequency samples can be achieved by sampling the DTFT defined in (). The direct use of the DFT can be inefficient, and for linear-phase filters, it is A(ω), not H(ω), that is the most informative. In addition to the direct application of the DFT, special formulas are developed in () for evaluating samples of A(ω) that exploit the fact that h(n) is real and has certain symmetries. For long filters, even these formulas are too inefficient, so the DFT is used, but implemented by a Fast Fourier Transform (FFT) algorithm. In the special case of Type 1 filters with L equally spaced sample points, the samples of the frequency response are of the form A k = A ( 2 π k / L ) = ∑ n = 0 M - 1 2 h ( n ) cos ( 2 π ( M - n ) k / L ) + h ( M ) For Type 2 filters, A k = A ( 2 π k / L ) = ∑ n = 0 N / 2 - 1 2 h ( n ) cos ( 2 π ( M - n ) k / L ) For Type 3 filters, A k = A ( 2 π k / L ) = ∑ n = 0 M - 1 2 h ( n ) sin ( 2 π ( M - n ) k / L ) For Type 4 filters, A k = A ( 2 π k / L ) = ∑ n = 0 N - 1 2 h ( n ) sin ( 2 π ( M - n ) k / L ) Although this section has primarily concentrated on linear-phase filters by taking their symmetries into account, the method of taking the DFT of h(n) to obtain samples of the frequency response of an FIR filter also holds for general arbitrary linear phase filters.

Zero Locations for Linear-Phase FIR Filters A qualitative understanding of the filter characteristics can be obtained from an examination of the location of the N-1 zeros of an FIR filter's transfer function. This transfer function is given by the z-transform of the length-N impulse response H ( z ) = ∑ n = 0 N - 1 h ( n ) z - n which can be rewritten as H ( z ) = z - N + 1 ( h 0 z N - 1 + h 1 z N - 2 + . . . + h N - 1 ) or as H ( z ) = z - N + 1 D ( z ) where D(z) is an N-1 order polynomial that is multiplied by an N-1 order pole located at the origin of the complex z-plane. D(z) is defined in order to have a simple polynomial in positive powers of z. The fact that h(n) is real valued requires the zeros to all be real or occur in complex conjugate pairs. If the FIR filter is linear phase, there are further restrictions on the possible zero locations. From (), it is seen that linear phase implies a symmetry in the impulse response and, therefore, in the coefficients of the polynomial D(z) in (). Let the complex zero z1 be expressed in polar form by z 1 = r 1 e j x where r1 is the radial distance of z1 from the origin in the complex z-plane, and x is the angle from the real axis as shown in .

Example of Impulse Responses for the Four Types of Linear Phase FIR Filters Using the definition of H(z) and D(z) in () and () and the linear-phase even symmetry requirement of h ( n ) = h ( N - 1 - n ) gives H ( 1 / z ) = D ( z ) </