Digital filtering is concerned with the manipulation of discrete data sequences to remove noise, extract information, change the sample rate, and perform other functions. Although an infinite number of numerical manipulations can be applied to discrete data (e.g., finding the mean value, forming a histogram), the objective of digital filtering is to form a discrete output sequence *y*(*n*) from a discrete input sequence *x*(*n*). In some manner or another, each output sample is computed from the input sequence—not just from any one sample, but from many, in fact, possibly from all of the input samples. Those filters that compute their output from the present input and a finite number of past inputs are termed *finit**e impulse response *(FIR), whereas those that use all past inputs are *infinite impulse response *(IIR). This chapter will consider the design and realization of both FIR and IIR digital filters and will examine the effect of finite wordlength arithmetic on implementing these filters.

__FIR Filters__

__FIR Filters__

A finite impulse response filter is a linear discrete time system that forms its output as the weighted sum of the most recent, and a finite number of past, inputs. Time-invariant FIR filters have finite memory, and their impulse response, namely, their response to a discrete input that is unity at the first sample and otherwise zero, matches the fixed weighting coefficients of the filter. Time-variant FIR filters, on the other hand, may operate at various sampling rates and/or have weighting coefficients that adapt in sympathy with some statistical property of the environment in which they are applied.

__Fundamentals__

__Fundamentals__

Perhaps the simplest example of an FIR filter is the moving average operation described by the following linear constant-coefficient difference equation:

In a practical application, the input and output discrete-time signals is sampled at some regular sampling time interval, *T *seconds, denoted *x*(*n**T *) and *y*(*n**T *), which is related to the sampling frequency by *f**s *= 1*/ **T** *samples per second. For generality, however, it is more convenient to assume that *T *is unity, so that the effective sampling frequency is also unity and the Nyquist frequency (Oppenheim and Schafer, 1989), namely, the maximum analog frequency that when sampled at *f**s *will not yield an aliasing distortion, is one-half. It is then straightforward to scale, by multiplication, this normalized frequency range, that is, (0, 1/2), to any other sampling frequency.

The output of the simple moving average filter is the average of the *M *+ 1 most recent values of *x*(*n*). Intuitively, this corresponds to a smoothed version of the input, but its operation is more appropriately described by calculating the frequency response of the filter. First, however, the *z*-domain representation of the filter is introduced in analogy to the *s *- (or Laplace-) domain representation of analog filters. The *z *transform of a causal discrete-time signal *x*(*n*) is defined by

where *X*(*z*) is *z *transform of *x*(*n*) and *z *is complex variable The *z *transform of a delayed version of *x*(*n*), namely, *x*(*n *− *k*) with *k *a positive integer, is found to be given by *z*−*k **X*(*z*). This result can be used to relate the *z *transform of the output *y*(*n*) of the simple moving average filter to its input

Notice the transfer function *H*(*z*) is entirely defined by the values of the weighting coefficients *b**k *, *k *= 0, 1, *..**. *, *M*, which are identical to the discrete impulse response of the filter, and the complex variable *z*. The finite length of the discrete impulse response means that the transient response of the filter only lasts for *M *+ 1 samples, after which steady state is re__a____che__d. The frequency domain transfer function for the filter is found by setting *z *= *e **j *2*π **f *, where *j *= √ 1, and can be written as

The magnitude and phase response of the simple moving average filter, with *M *= 7, are calculated from *H*(*e **j *2*π **f *) and shown in Fig. 12.1. The filter is seen clearly to act as a crude low-pass, smoothing filter with a **linear-phase **response. The sampling frequency periodicity in the magnitude and phase response is a property of discrete-time systems. The linear-phase response is due to the *e*− *j **π **f** **M *term in *H*(*e **j *2*π **f *) and corresponds to a constant *M*/2 group delay through the filter. A phase discontinuity of +*/ *− 180◦ is introduced each time the magnitude term changes sign. FIR filters that have center symmetry in their weighting coefficients have this constant, frequency independent group delay property that is very desirable in applications in which time dispersion is to be avoided, for example, in pulse transmission where it is important to preserve pulse shapes (Lee and Messerschmit, 1994).

The *z*-domain transfer function is shown to be the ratio of two *M*th-order polynomials in *z*, namely, *N*(*z*) and *D*(*z*). The values of *z *for which *N*(*z*) = 0 are termed the zeros of the filter, whereas those for which *D*(*z*) = 0 are the poles. The poles of such an FIR filter are at the origin, that is, *z *= 0, in the *z** *plane. The positions of the zeros are determined by the weighting coefficients, that is, *b**k *, *k *= 0, 1, *..**. *, *M*. The poles and zeros in the *z *plane for the simple moving average filter are shown in Fig. 12.2. The zeros, marked with a circle, are coincident with the unit circle, that is, the contour in the *z *plane for which |*z*| = 1, and match exactly the zeros in the magnitude response, hence their name; the discontinuities in the phase response are shown in Fig. 12.1.The zeros of an FIR filter may lie anywhere in the *z *plane because they do not impact on the stability of the filter; however, if the weighting coefficients are real and symmetric, or anti-symmetric,about their center value *M*/2, any complex zeros of the filter are constrained to lie as conjugate pairs coincident with the unit circle or as quartets of roots off the unit circle with the form (*ρ**e **j **θ *, *ρ**e*− *j **θ *, (1*/ρ*)*e **j **θ *, (1*/ρ*)*e*− *j **θ *) where *ρ *and *θ *are, respectively, the radius and angle of the first zero. Zeros that lie within the unit circle are termed *minimum*

*phase*, whereas those which lie outside the unit circle are called *ma**x**imu**m phase*. This distinction describes the contribution made by a particular zero to the overall phase response of a filter. A minimum-phase FIR filter that has all its zeros within the unit circle can have identical magnitude response to a maximum-phase FIR that has all its zeros outside the unit circle for the special case when they have an equal number of zeros with identical angles but reciprocal radii. An example of this would be second-order FIR filters with *z*-domain transfer functions *H*min(*z*) = 1 + 0*.*5*z*−1 + 0*.*25*z*−2 and *H*max(*z*) = 0*.*25 + 0*.*5*z*−1 + *z*−2. Notice that the center symmetry in the coefficients is lost, but the minimum- and maximum-phase weighting coefficients are simply reversed. Physically, a minimum-phase FIR filter corresponds to a system for which the energy is rapidly transferred from its input to its output, hence, the large initial weighting coefficients; whereas a maximum-phase FIR filter is slower to transfer the energy from its input to output; as such, its larger coefficients are delayed. Such FIR filters are commonly used for modeling multipath mobile communication transmission paths.

The characteristics of the frequency response of an FIR filter are entirely defined by the values of the weighting coefficients *b**k *, *k *= 0, 1, *..**. *, *M*, which match the impulse response of the filter, and the order *M*. Various techniques are available for designing these coefficients to meet the specifications of some application. However, next consider the structures available for realizing an FIR filter.

__Structures__

__Structures__

The structure of an FIR filter must realize the *z*-domain transfer function given by

where *z*−1 is a unit delay operator. The building blocks for such filters are, therefore, adders, multipliers, and unit delay elements. Such elements do not have the disadvantages of analog components such as capacitors, inductors, operational amplifiers, and resistors, which vary with temperature and age. The direct or tapped-delay line form, as shown in Fig. 12.3, is the most straightforward realization of an FIR filter. The input *x*(*n*) is delayed, scaled by the weighting coefficients *b**k *, *k *= 0, 1, *..**. *, *M*, and accumulated to yield the output.

An equivalent, but transposed, structure of an FIR filter is shown in Fig. 12.4, which is much more modular and well suited to integrated circuit realization. Each module within the structure calculates a partial sum so that only a single addition is calculated at the output stage.

Other structures are possible that exploit symmetries or redundancies in the filter weighting coefficients. For example, FIR filters with linear phase have symmetry about their center coefficient *M*/2; approximately one-half of the coefficients of an odd length, that is, *M *even, half-band FIR filter, namely, a filter that ideally passes frequencies for 0 ≤ *f *≤ 1*/*4 and stops frequencies 1*/*4 *< **f *≤ 1*/*2, are zero. Finally, a lattice structure as shown in Fig. 12.5 may be used to realize an FIR filter. The multiplier coefficients within the lattice *k **j *, *j *= 1, *..**. *, *M*, are not identical to the weighting coefficients of the other FIR filter structures but can be found by an iterative procedure. The attraction of the lattice structure is that it is staightforward to test whether all its zeros lie within the unit circle, namely, the minimum-phase property, and it has low sensitivity to quantization errors. These properties have motivated the use of lattice structures in speech coding applications (Rabiner and Schafer, 1978).

__Design Techniques__

__Design Techniques__

Linear-phase FIR filters can be designed to meet various filter specifications, such as low-pass, high- pass, band-pass and bandstop filtering. For a low-pass filter, two frequencies are required, namely, the maximum frequency of the pass band below which the magnitude response of the filter is approximately unity, denoted the pass-band corner frequency *f **p *, and the minimum frequency of the stop band above which the magnitude response of the filter must be less than some prescribed level, named the stop-band corner frequency *f**s *. The difference between the pass- and stop-band corner frequencies is the *t**r**ansition- bandwidth*. Generally, the order of FIR filter *M *required to meet some design specification increases with a reduction in the width of the transition band. There are three established techniques for coefficient design:

- Windowing
- Frequency sampling
- Optimal approximations

The windowing design method calculates the weighting coefficients by sampling the ideal impulse response of an analog filter and multiplying these values by a smoothing window to improve the overall

frequency domain response of the filter. The frequency sampling technique samples the ideal frequency domain specification of the filter and calculates the weighting coefficients by inverse trans- forming these values. However, better results can generally be obtained with the optimal approxima tionsmethod. The impulse response and magnitude response for a 40th-order optimal half-band FIR low-pass filter designed with the Parks-McClellan algorithm are shown in Fig. 12.6 together with the ideal frequency domain design specification. Notice the zeros in the impulse response. This algorithm minimizes the maximum deviation of the **magnitude response **of the design filter from the ideal magnitude response. The magnitude response of the design filter alternates about the desired specification within the pass band and above the specification in the stop band. The maximum deviation from the desired specification is equalized across the pass and stop bands; this is characteristic of an optimal solution.

The optimal approximation approach can also be used to design *discrete-time differentiators *and *hilbert transformers*, namely, phase shifters. Such filters find extensive application in digital modulation schemes.

__Multirate and Adaptive FIR Filters__

__Multirate and Adaptive FIR Filters__

FIR filter structures can be combined very usefully with multirate processing elements. Such a filtering scheme is, however, time variant and as such may introduce some distortion during processing, but with careful design this can be minimized. Consider the design of a low-pass filter with *f**c *= 1*/*8; frequencies above this value are essentially to be eliminated. The frequency range between *f**c *and the Nyquist frequency, that is, 1/2, therefore contains no useful information. The sampling frequency could, provided no aliasing distortion is introduced, therefore be usefully reduced by a factor of 4. Further processing, possibly adaptive, of the signal could then proceed at this reduced rate, hence, reducing the demands on the system design. This operation can be achieved in two ways: A time-invariant low-pass FIR filter, with *f**c *= 1*/*8, can be designed to operate at the original sampling rate, and its output can be down sampled, termed decimated, by a factor of four; or, more efficiently, the filtering can be performed in two stages, using the same simple half-band filter design twice, each operating at a lower sampling rate. These methods are shown diagrammatically in Fig. 12.7. The second scheme has considerable computational advantages and, because

of the nature of half-band filters, it is also possible to move the decimators in front of the filters. With the introduction of modulation operations it is possible to use the same approach to achieve high-pass and band-pass filtering.

The basic structure of an **adaptive FIR filter **is shown in Fig. 12.8. The input to the adaptive filter *x*(*n*) is used to make an estimate ∩*d*(*n*) of the de-sired response *d*(*n*). The difference between these quantities *e*(*n*), is used by the adaptation algorithm to control the weighting coefficients of the FIR filter. The derivation of the desired response signal depends on the application; in channel equalization, as necessary for reliable communication with data modems, it is typically a training sequence known to the receiver. The weighting coefficients are adjusted to minimize some function of the error, such as the mean square value. The most commonly used adaptive algorithm is the least mean square (lms) algorithm that approximately minimizes the mean square error. Such filters have the ability to adapt to time-varying environments where fixed filters are inappropriate.

__Applications__

__Applications__

The absence of drift in the characteristics of digitally implemented FIR filters, their ability to reproduce, multirate realizations, and their ability to adapt to time-varying environments has meant that they have found many applications, particularly in telecommunications, for example, in receiver and transmitter design, speech compression and coding, and channel multiplexing. The primary advantages of fixed coefficient FIR filters are their unconditional stability due to the lack of feedback within their structure and their exact linear-phase characteristics. Nonetheless, for applications that require sharp, selective, filtering in standard form, they do require relatively large orders. For some applications, this may be prohibitive and, therefore, recursive; IIR filters are a valuable alternative.

*Infinite Impulse Response (IIR) Filters*

A digital filter with impulse response having infinite length is called an *infinite impulse response *(IIR) filter.

An important class of IIR filters can be described by the difference equation

where *x*(*n*) is the input, *y*(*n*) is the output of the filter, and (*a*1, *a*2, *..**. *, *a**N *) and (*b*0, *b*1, *..**. *, *b**M *) are real-value coefficients.

We denote the impulse response by *h*(*n*), which is the output of the system when it is driven by a unit impulse at *n *= 0, with the system being initially at rest. The system function *H*(*z*) is the *z *transform of *h*(*n*). For the system in Eq. (12.1), it is given by

The frequency response of the IIR filter is the value of the system function evaluated on the unit circle on the complex plane, that is, with *z *= *e **j *2*π **f *, where *f *varies from0 to 1, or from −1/2 to 1/2. The variable *f *represents the digital frequency. For simplicity, we write *H*( *f *) for *H*(*z*)|*z*=exp( *j *2*π **f *). Therefore

where |*H*( *f *)| is the magnitude response and *θ *( *f *) is the phase response.

Compared to an FIR filter, an IIR filter requires a much lower order than an FIR filter to achieve the same requirement of the magnitude response. However, whereas an FIR filter is always stable, an IIR filter can be unstable if the coefficients are not properly chosen. Assuming that the system (12.1) is causal, then it is stable if all of the poles lie inside the unit circle on the *z *plane. Since the phase of a stable causal IIR filter cannot be made linear, FIR filters are chosen over IIR filters in applications where linear phase is essential.

Equation (12.1) suggests a realization of an IIR filter as shown in Fig.12.9(a), which is called direct form I. By rearranging the structure, we can obtain direct form II, as shown in Fig. 12.9(b). Through transposition, we can obtain transposed direct form I and transposed direct form II, as shown in Fig 12.9(c) and Fig. 12.9(d).

The system function can be put in the form

by partial fraction expansion. The value of *K *is *N**/*2 when *N *is even, and it is (*N *+ 1)*/*2 when *N *is odd. When *N *is odd, one of *a**i *2 must be zero, as well as one of *b**i *2 in Eq. (12.6) and one of *b**i *1 in Eq. (12.7). According to Eq. (12.6), the IIR filter can be realized by *K *second-order IIR filters in cascade, as shown in Fig. 12.10(a). According to Eq. (12.7), the IIR filter can be realized by *K *second-order IIR filters and one scaler (i.e., *c*0) in parallel, as depicted in Fig. 12.10(b). Each second-order subsystem can use any of the structures given in Fig. 12.9.

There are other realizations for IIR filters, such as state-space structure, wave structure, and lattice structure. See the references for details. In some situations, it is more convenient or suitable to use software realizations that are implemented by a digital signal processor.

__IIR Filter Design__

__IIR Filter Design__

Designing an IIR filter involves choosing the coefficients to satisfy a given specification, usually a magnitude response specification. We assume that the specification is in the form depicted by Fig. 12.11, where the magnitude square must be in the range (1*/*(1+*ε *), 1) in the pass band and it must be no larger than *δ *in the stop band. The pass-band and the stop-band edges are denoted by *f **p *and *f**s *, respectively. No constraint is imposed on the response in the transition band, which lies between a pass band and a stop band.

There are various IIR filter design methods: design using an analog prototype filter, design using digital frequency transformation, and computer-aided design. In the first method, an analog filter is designed to meet the (analog) specification and the analog filter transfer function is transformed to digital system function. The second method assumes that some digital low-pass filter is available and the desired digital

filter is obtained from the digital low-pass filter by a digital frequency transformation. The last method involves algorithms that choose the coefficients so that the response is as close (in some sense) as possible to the desired filter. The first two methods are simple to do, and they are suitable for designing standard filters (low-pass, high-pass, bandpass, and bandstop filters). A computer-aided design requires computer

programming, but it can be used to design standard and nonstandard filters. We will focus only on the first method and present some design examples, as well as a summary of some analog filters, in the following sections.