2.2 Finite impulse response (FIR) filter design methods
Most FIR filter design methods are based on ideal filter approximation. The resulting filter approximates the ideal characteristic as the filter order increases, thus making the filter and its implementation more complex.
The filter design process starts with specifications and requirements of the desirable FIR filter. Which method is to be used in the filter design process depends on the filter specifications and implementation. This chapter discusses the FIR filter design method using window functions.
Each of the given methods has its advantages and disadvantages. Thus, it is very important to carefully choose the right method for FIR filter design. Due to its simplicity and efficiency, the window method is most commonly used method for designing filters. The sampling frequency method is easy to use, but filters designed this way have small attenuation in the stopband.
As we have mentioned above, the design process starts with the specification of desirable FIR filter.
2.2.1 Basic concepts and FIR filter specification
First of all, it is necessay to learn the basic concepts that will be used further in this book. You should be aware that without being familiar with these concepts, it is not possible to understand analyses and synthesis of digital filters.
Figure 221 illustrates a lowpass digital filter specification. The word specification actually refers to the frequency response specification.
Figure 221a. Lowpass digital filter specification
Figure221b. Lowpass digital filter specification

 ωp – normalized cutoff frequency in the passband;

 ωs – normalized cutoff frequency in the stopband;

 δ1 – maximum ripples in the passband;

 δ2 – minimum attenuation in the stopband [dB];

 ap – maximum ripples in the passband; and

 as – minimum attenuation in the stopband [dB].
Frequency normalization can be expressed as follows:
where:

 fs is a sampling frequency;

 f is a frequency to normalize; and

 ω is normalized frequency.
Specifications for highpass, bandpass and bandstop filters are defined almost the same way as those for lowpass filters. Figure 222 illustrates a highpass filter specification.
Figure 222a. Highpass digital filter specification
Figure 222b. Highpass digital filter specification
Comparing these two figures 221 and 222, it is obvious that lowpass and highpass filters have similar specifications. The same values are defined in both cases with the difference that in the later case the passband is substituded by the stopband and vice versa.
Figure 223 illustrates a bandpass filter specification.
Figure 223a. Bandpass digital filter specification
Figure 223b. Bandpass digital filter specification
Figure 224 illustrates a bandstop digital filter specification.
Figure 224a. Bandstop digital filter specification
Figure 224b. Bandstop digital filter specification
2.2.2 Ztransform
The Ztransform is performed upon discretetime signals. It converts a discrete timedomain signal into a complex frequencydomain representation. It is very suitable for analysing discrete timedomain signals and systems. The ztransform is derived from the Fourier discrete timedomain transformation and is considered the basic operation in digital filter design process.
The Ztransform is defined as:
where
z is the complex number.
Example:
Assume that samples of a discretetime signal x(n) are known. It is necessary to transform this signal through the ztransform and Fourier fransform.
x(n)={1,2,3,4,5,4,3,2,1} ; 0 ≤ n ≤ 8
ztransform is defined as follows:
It becomes:
The last expression represents the ztransform of the given signal.
The Fourier transform can be found by rewriting the previous expression in terms of z as z=ejω. It further becomes:
Figure 225 illustrates the frequency spectrum of the given signal.
Figure 225. Frequency spectrum of the given signal
Comparing Z and Fourier transforms, it is easy to notice some similarities between them:
In polar coordinate system, the complex number z may be expressed as:
The two last expressions lead us to the conclusion that the Fourier transform is just a special form of the ztransform for r=1.
In the z plane, the Fourier transform is represented as a unit circle, which can be seen in Figure 226 below.
Figure 226. Fourier transform in the z plane
2.2.2.1 Transform function of discretetime systems
The Ztransform is primarily used for finding the transfer function of linear discretetime systems. When the transfer function is found, it is necessary to consider its zeros and poles in the z plane. The transfer function of discretetime systems is defined as:
where:

 bi are the feedforward filter coefficients (nonrecursive part);

 aj are the feedback filter coefficients (recursive part);

 qi are the zeros of the transfer function; and

 pj are the poles of the transfer function.
The recursive part of the transfer function is actually a feedback of discretetime system. As we previously mentioned, FIR filters do not have this recursive part of the transfer function, so the expression above can be simplified in the following way:
The impulse response of discretetime system is obtained from inverse ztransform of the transfer function i.e. the transfer function of discretetime system is actually the Ztransform of impulse response:
where h(n) is the impulse response of discretetime system.
Figure 227. Block diagram of a linear discretetime system
In the time domain, the discretetime system, shown in Figure 227, can also be expressed as the convolution of the input signal
x(n) and the impulse response
h(n) of the system:
In the frequency domain, the discretetime system, shown in Figure 227, can be expressed as the multiplication of the Ztransform input signal
X(z) and the transfer function
H(z) of the system:
which further gives:
The first way of representing discretetime systems is more suitable for software implementation itself, whereas the later is more suitable for analyse, hardware implementation (described later) and synthesis, i.e. discretetime system design.
Example:
The impulse response of a 10th order FIR filter designed using the Hamming window (discussed in the next chapter) is:
h(n) = {0,  0.0127,  0.0248, 0.0638, 0.2761, 0.4, 0.2761, 0.0638,  0.0248,  0.0127, 0}
The transfer function of this filter is found via the ztransform of impulse response:
Using the following expression:
it is possible to yield the transfer function of the fixed normalized frequency. If for example ω = 0.2π then:
One example of hardware realization of this filter is illustrated in Figure 228.
Figure 228. FIR filter realization
Software realization requires a buffer of minimum length 9. Buffers are usually circular and their length can be expressed as 2^n, which in this case means that the circular buffer is of length 16=2^4.
2.2.2.2 Effect of the poles and zeros of the transfer function
The location of zeros and poles of the transfer function is very important for discretetime system analyses and synthesis. According to their position it is possible to test stability of a discretetime system, detect roundoff errors made due to software implementation of a filter as well as errors in the coefficients encountered during hardware implementation of a filter.
In order that a discretetime system is stable, all poles of the discretetime system transfer function must be located inside the unit circle, as shown in Figure 226. If this requirement is not satisfied, the system becomes unstable, which is very dangerous. The location of zeros doesn’t affect the stabilty of discretetime systems. Recalling that FIR flters do not have a feedback, which further means that the transfer function has no poles. This causes a FIR filter to be always stable. Filter stability will be discussed in more details along with IIR filters which have potential to become unstable because of the feedback they have. This property of FIR filters actually represents their essential adventage. From now on, only the zeros of the transfer function will be discussed in this chapter.
An error in coefficient representation is always produced due to software and hardware implementation. In software implementation, an error is triggered by the finite wordlength effect, whereas in hardware implementation, it ocurrs due to impossibility of representing the coefficients with absolute accuracy. The result in both cases is that the value of coefficients differs from their value obtained in design process. Such errors cause frequency deviation of discretetime system designed.
Frequency deviation depends on the spacing between the zeros of the FIR filter transfer function. FIR filter coefficient error affects more the frequency characteristic as the spacing between the zeros of the transfer function narrows. This property is particularly typical of highorder filters because their zeros are very close each other. However, slight errors in coefficient representation may cause large frequency deviations.
Figure 229 illustrates the required and obtained frequency characteristic of a FIR filter. The finite wordlength effect on the transform function of a FIR filter is clearly marked. Assume that a 50th order lowpass FIR filter with normalized cutoff frequency of 0.25 Hz is designed using the Hann window.
Figure 229. Deviation from required frequency characteristic
The frequency deviation shown in Figure 229 is basically slight deviation, even though it is very large at certain points. The minimum attenuation and the width of transition region of the resulting IIR filter remain unchanged, so that such deviation is acceptable. However, as this is not a common case, it is necessary to be very careful when designing high order filters because the transfer function zeros get closer, while more affecting the resulting frequency characteristic.
2.2.3 Ideal filter approximation
The ideal filter frequency response is used when designing FIR filters using window functions. The objective is to compute the ideal filter samples. FIR filters have finite impulse response, which means the ideal filter frequency sampling must be performed in a finite number of points. As the ideal filter frequency response is infinite, it is easy to produce sampling errors. The error is less as the filter order increases.
Figure 2210 illustrates the transfer functions of four standard ideal filters.
Figure 2210. Transfer functions of four standard ideal filters
The ideal filter frequency response can be computed via inverse Fourier transform. The four standard ideal filters frequency responses are contained in the table 221 below.
Table 221. The frequency responses of four standard ideal filters
The value of variable
n ranges between 0 and N, where N is the filter order. A constant M can be expressed as M = N / 2. Equivalently, N can be expressed as N = 2M.
The constant M is an integer if the filter order N is even, which is not the case with odd order filters. If M is an integer (even filter order), the ideal filter frequency response is symmetric about its Mth sample which is found via expression shown in the table 221 above. If M is not an integer, the ideal filter frequency response is still symmetric, but not about some frequency response sample.
Since the variable
n ranges between 0 and N, the ideal filter frequency response has N+1 sample.
If it is needed to find frequency response of a nonstandard ideal filter, the expression for inverse Fourier transform must be used:
Nonstandard filters are rarely used. However, if there is a need to use some of them, the integral above must be computed via various numerical methodes.
2.2.4 FIR filter design using window functions
The FIR filter design process via window functions can be split into several steps:

 Defining filter specifications;

 Specifying a window function according to the filter specifications;

 Computing the filter order required for a given set of specifications;

 Computing the window function coefficients;

 Computing the ideal filter coefficients according to the filter order;

 Computing FIR filter coefficients according to the obtained window function and ideal filter coefficients;

 If the resulting filter has too wide or too narrow transition region, it is necessary to change the filter order by increasing or decreasing it according to needs, and after that steps 4, 5 and 6 are iterated as many times as needed.
The final objective of defining filter specifications is to find the desired normalized frequencies (ωc, ωc1, ωc2), transition width and stopband attenuation. The window function and filter order are both specified according to these parameters.
Accordingly, the selected window function must satisfy the given specifications. This point will be discussed im more detail in the next chapter (2.3).
After this step, that is, when the window function is known, we can compute the filter order required for a given set of specifications. One of the techniques for computing is provided in chapter 2.3.
When both the window function and filter order are known, it is possible to calculate the window function coefficients w[n] using the formula for the specified window function. This issue is also covered in the next chapter.
After estimating the window function coefficients, it is necessary to find the ideal filter frequency samples. The expressions used for computing these samples are discussed in section 2.2.3 under
Ideal filter approximation. The final objective of this step is to obtain the coefficients hd[n]. Two sequencies w[n] and hd[n] have the same number of elements.
The next step is to compute the frequency response of designed filter h[n] using the following expression:
Lastly, the transfer function of designed filter will be found by transforming impulse response via Fourier transform:
or via Ztransform:
If the transition region of designed filter is wider than needed, it is necessary to increase the filter order, reestimate the window function coefficients and ideal filter frequency samples, multiply them in order to obtain the frequency response of designed filter and reestimate the transfer function as well. If the transition region is narrower than needed, the filter order can be decreased for the purpose of optimizing hardware and/or software resources. It is also necessary to reestimate the filter frequency coefficients after that. For the sake of precise estimates, the filter order should be decreased or increased by 1.
2.2.5 FIR filter realization
FIR filter transfer function can be expressed as:
The frequency response realized in the time domain is of more interest for FIR filter realization (both hardware and software). The transfer function can be found via the ztransform of a FIR filter frequency response. FIR filter output samples can be computed using the following expression:
where:

 x[k] are FIR filter input samples;

 h[k] are the coefficients of FIR filter frequency response; and

 y[n] are FIR filter output samples.
A good property of FIR filters is that they are less sensitive to the accuracy of constants than IIR filters of the same order.
There are several types of FIR filter realization. This chapter covers direct, direct transpose and cascade realizations which are very convenient for the hardware implementation of a filter. As for the software implementation, direct and optimized realizations will be discussed in this book.
2.2.5.1 Direct realization
Direct realization of FIR filter is based on the direct implementation of this expression:
Direct realization is also known as a transversal filter.
Figure 2211 illustrates the block diagram describing the hardware direct realization of a FIR filter.
Figure 2211. FIR filter direct realization
For direct realization structure, the multiplication constants are the same as the transfer function coefficients, i.e. the FIR filter frequency response coefficients.
As for software direct realization of the FIR filter, it is necessary to provide a buffer for minimum N samples, where N is the number of FIR filter coefficients. For its simplicity and speed, most commonly used buffer is so called circular buffer the length of which can be expressed as 2^k. The value of the constant k is a minimum value for which the expression N ≤ 2^k is valid. Accordingly:
where the operator
represents rounding down to a less value.
Figure 2212. Circular buffer of length 16 = 2^4
The algorithm used for software direct realization of FIR filter consists of:

 Reading the samples of a signal being filtered;

 Storing a new sample on the first available location; and

 Performing a convolution operation upon filter coefficients (frequency response coefficients), resulting in a FIR filter output sample.
Since the buffer is 16 bits wide, circular buffer addressing is performed using addressing mode 16:
Example: Assuming that a filter used in this example is a 5th order FIR filter. Design this filter using direct realization with circular buffer. The buffer length needs to be 2^k.
The buffer length is obtained in the following way:
This means that the minimum length of circular buffer is 2^3 = 8.
The contents of the buffer after receiving the first 10 samples is shown in the table 222. Input samples are denoted by x[n], whereas the shaded cells denote buffer locations that have been changed.
STEP 
ADDR. 7 
ADDR. 6 
ADDR. 5 
ADDR. 4 
ADDR. 3 
ADDR. 2 
ADDR. 1 
ADDR. 0 

0 








1 







x[0] 
2 






x[1] 
x[0] 
3 





x[2] 
x[1] 
x[0] 
4 




x[3] 
x[2] 
x[1] 
x[0] 
5 



x[4] 
x[3] 
x[2] 
x[1] 
x[0] 
6 


x[5] 
x[4] 
x[3] 
x[2] 
x[1] 
x[0] 
7 

x[6] 
x[5] 
x[4] 
x[3] 
x[2] 
x[1] 
x[0] 
8 
x[7] 
x[6] 
x[5] 
x[4] 
x[3] 
x[2] 
x[1] 
x[0] 
9 
x[7] 
x[6] 
x[5] 
x[4] 
x[3] 
x[2] 
x[1] 
x[8] 
10 
x[7] 
x[6] 
x[5] 
x[4] 
x[3] 
x[2] 
x[9] 
x[8] 
Table 222. Input circular buffer after receiving 10 samples
For software realization, filtering of input samples is performed as per formula below:
2.2.5.2 Direct transpose realization
Direct transpose realization is similar to direct realization in many ways. Speaking about software implementation, the direct transpose realization must also have a buffer of minimum length N, where N is the number of FIR filter coefficients.
Figure 2213 illustrates the block diagram describing hardware direct transpose realization of a FIR filter.
Figure 2213. Direct transpose realization of a FIR filter
There are no significant differences between direct and direct transpose realizations. Both structures have the same number of delay elements, the same number of multipliers and the same coefficients to perform multiplication upon.
2.2.5.3 Cascade realization
Cascade realization, very convenient for its modular structure, is commonly used for FIR filter hardware realization. When using this realization, a filter is divided into several loworder sections. The secondorder sections are most commonly used. Individual sections are mostly in direct form realization, although they can also be in direct transpose form realization. The cascade realization is normally used for higher order filter realization.
The transfer function of the cascade realization looks as follows:
where:

 M is the number of sections; and

 ak1, ak2 are the multiplication coefficients of section k.
Figure 2214 illustrates the block diagram describing the hardware cascade realization of a FIR filter.
Figure 2214. FIR filter cascade realization
The number of multipliers, adders and delays is the same as for direct realization. The main advantage of the cascade realization is its modularity, otherwise very convenient for hardware implementation. The cascade of second order sections is important for the realization of the filters of arbitrary order.
2.2.5.4 Optimized realization
Optimized realization has less, but more demanding multipliers for realization. This realization is most commonly used for software implementation of FIR filters, because a reduction in the number of multipliers enhances the process of convolution (samples filtering process).
Optimized realization utilizes the symmetry of frequency response coefficients. There are also antisymmetric FIR filters that are beyond the scope of this book. Anyway, the optimized realization may be used for these filters as well.
The symmetry of the coefficients of FIR filter frequency response can be expressed by equation below:
This symmetry makes it possible for the transfer function to be expressed as follows:
Figure 2215 illustrates the block diagram of optimized realization for even N, whereas Figure 2216 illustrates that for odd N.
Figure 2215. Optimized realization for odd frequency response
Figure 2216. Optimized realization for even frequency response