Structures for Implementing Finite Impulse Response Filters
October 04, 2017 by Steve ArarThis article will review some basic structures to implement Finite Impulse Response (FIR) filters.
This article will review some basic structures to implement Finite Impulse Response (FIR) filters.
When designing a filter, we start from a set of specifications which are generally determined by a particular application. For example, we may need to suppress the 50Hz noise which appears at the output of a sensor and makes our measurements inaccurate. Based on the frequency and strength of the noise component, we can determine the filter specifications such as the passband and stopband edge, the transition bandwidth, the ultimate outofband rejection, etc. Now, we can find the system function, $$H(z)$$, which satisfies these requirements.
For a FIR design, we have a couple of options such as the windowing method, the frequency sampling method, and more. Then, we need to choose a realization structure for the obtained system function. In other words, there are several structures which exhibit the same system function $$H(z)$$. One consideration for choosing the appropriate structure is the sensitivity to coefficient quantization. Since a digital filter uses a finite number of bits to represent signals and coefficients, we need structures which can somehow retain the target filter specifications even after quantizing the coefficients. In addition, sometimes we observe that a particular structure can dramatically reduce the computational complexity of the system.
The DirectForm Structure
The directform structure is directly obtained from the difference equation. Assume that the difference equation of the FIR filter is given by
$$y(n)=\sum_{k=0}^{M1}b_{k}x(nk)$$
Equation 1
Based on the above equation, we need the current input sample and $$M1$$ previous samples of the input to produce an output point. For $$M=5$$, we can simply obtain the following diagram from Equation 1.
Figure 1. Directform structure for a fourthorder FIR filter.
Using the directform realization of Figure 1, we need $$M$$ multipliers for an $$(M1)$$thorder FIR filter. However, usually, we can almost halve the number of multipliers. This can be achieved by noting that we are mainly interested in linearphase FIR filters. In fact, the main advantage of a FIR filter over an infinite impulse response (IIR) design is its linearphase response, otherwise, for a given set of specifications, an IIR design can offer a filter of lower order and reduce the computational complexity. On the other hand, for a linearphase FIR filter, we observe the following symmetry in the coefficients of the difference equation
$$b_{k}=\pm b_{M1k}$$
For $$M=5$$, Equation 1 gives
$$y(n)=b_{0}x(n)+b_{1}x(n1)+b_{2}x(n2)+b_{3}x(n3)+b_{4}x(n4)$$
Assuming $$b_{k}=b_{M1k}$$, we obtain
$$y(n)=b_{0}\left( x(n) + x(n4) \right)+b_{1}\left( x(n1)+x(n3) \right)+b_{2}x(n2)$$
The structure obtained from the above equation is shown in Figure 2. While Figure 1 requires five multipliers, employing the symmetry of a linearphase FIR filter, we can implement the filter using only three multipliers. This example shows that for an odd $$M$$, the symmetry property reduces the number of multipliers of an $$(M1)$$thorder FIR filter from $$M$$ to $$\tfrac{M+1}{2}$$. For a brief discussion about the importance of linearphase response see this article.
Figure 2. The symmetry of a linearphase FIR filter can be used to reduce the number of multipliers.
The CascadeForm Structure
While the direct form is derived from the difference equation, the cascade structure is obtained from the system function $$H(z)$$. The idea is to decompose the target system function into a cascade of secondorder FIR systems. In other words, we need to find secondorder systems which satisfy
$$H(z)=\sum_{k=0}^{M1}b_{k}z^{k}=\prod_{k=1}^{P}\left(b_{0k}+b_{1k}z^{1}+b_{2k}z^{2} \right)$$
Equation 2
where $$P$$ is the integer part of $$\tfrac{M}{2}$$. For example, $$M=5$$, $$H(z)$$ will be a polynomial of degree four which can be decomposed into two secondorder sections. Each of these secondorder filters can be realized using a direct form structure. It is desirable to set a pair of complexconjugate roots for each of the secondorder sections so that the coefficients become real. The reader may wonder why we need to rewrite a given $$H(z)$$ in terms of secondorder sections. In a future article, we will see that the main advantage of the cascade structure is its smaller sensitivity to the coefficient quantization.
To clarify converting a system function into the cascade form, let’s review an example.
Example 1
Assume that we need to implement the ninetap FIR filter given by the following table using a cascade structure.
The system function of this filter is
$$H(z)=0.0977+0.1497z^{2}+0.2813z^{3}+0.3333z^{4}+0.2813z^{5}+0.1497z^{6}0.0977z^{8}$$
It can be shown that
$$H(z)=GH_{1}(z)H_{2}(z)H_{3}(z)H_{4}(z)$$
where
$$G=0.0977$$
$$H_{1}(z)=\left(12.5321z^{1}+z^{2}\right)$$
$$H_{2}(z)=\left(10.3474z^{1}+z^{2}\right)$$
$$H_{3}(z)=\left(1+1.8794z^{1}+z^{2}\right)$$
$$H_{4}(z)=\left(1+z^{1}+z^{2}\right)$$
Hence, we obtain the structure shown in Figure 3.
Figure 3. The cascade structure for the system function of Example 1.
Each of these secondorder systems can be realized using the directform structure. For example, the realization of $$H_{1}(z)$$ is shown in Figure 4.
Figure 4. The direct form realization of $$H_{1}(z)$$.
You can verify that $$H_{1}(z)$$ pairs two real zeros of $$H(z)$$, i.e. $$z_1=2.0425$$ and $$z_2=0.4896$$; however, the other three secondorder sections (sos) incorporate the complexconjugate roots of $$H(z)$$. For example, the roots of $$H_2(z)$$ are $$z_3=0.1737 + 0.9848j$$ and $$z_4=0.1737  0.9848j$$.
Since finding the cascade form of a practical FIR filter involves tedious mathematics, we can use the MATLAB function tf2sos, which stands for transfer function to secondorder section, to obtain the cascade form of a given transfer function. In fact, the cascade form of $$H(z)$$ in the above example was found using the tf2sos function with the following lines of code:
N=[0.0977 0 0.1497 0.2813 0.3333 0.2813 0.1497 0 0.0977]; % This line defines the numerator of H(z)
D=1; % This defines the denominator of H(z)
[sos, G]=tf2sos(N, D) % converts the transfer function defined by Nand Dinto a cascade of secondorder sections
The result will be:
sos=
and $$G=0.0977$$.
Each row of sos above gives the transfer function of one of the secondorder sections. The first three numbers of each row represent the numerator of the corresponding secondorder section and the second three numbers give its denominator. For example, the first row of sos gives the secondorder section $$H_{1}(z)$$ of Example 1 and so on. The tf2sos command also gives a gain factor, $$G$$, which can be included in the cascadeform structure as shown in Figure 3.
Example 2
Assume that we need to implement the tentap FIR filter given by the following table using a cascade structure.
Similar to the previous example, we have:
N=[0.0024 0.0073 0.0606 0.1691 0.2654 0.2654 0.1691 0.0606 0.0073 0.0024];
D=1;
[sos, G]=tf2sos(N, D)
The result will be:
sos =
and $$G =0.0024$$.
Hence, the target system function can be rewritten in terms of secondorder sections as
$$H(z)=GH_{1}(z)H_{2}(z)H_{3}(z)H_{4}(z)H_{5}(z)$$
where
$$G=0.0024$$
$$H_{1}(z)=17.7465z^{1}$$
$$H_{2}(z)=1+0.8709z^{1}0.1291z^{2}$$
$$H_{3}(z)=1+1.7922z^{1}+1.6972z^{2}$$
$$H_{4}(z)=1+0.9858z^{1}+z^{2}$$
$$H_{5}(z)=1+1.0560z^{1}+0.5892z^{2}$$
In this example, the system function polynomial is of degree nine and, hence, the filter has nine zeros. As a result, we observe that $$H_{1}(z)$$ incorporates only one zero, i.e. the coefficient $$b_{2k}$$ in Equation 2 is zero for this secondorder section.
We can realize the secondorder sections of this example using a direct form structure and obtain the cascade structure of the filter; however, there is another alternative which allows us to reduce the computational complexity. To find this computationally efficient structure, remember that, as illustrated by Figure 1 and 2 above, a linearphase FIR filter can be realized with a smaller number of multipliers. On the other hand, notice that while the target system function is a linear phase, only $$H_{4}(z)$$ is a linearphase FIR structure (because of the coefficient symmetry).
So, the question remains: can we group the zeros of a given linearphase FIR system function in a way that the obtained decomposition incorporates linearphase structures? For a linearphase FIR filter, the symmetry in the $$b_{k}$$ coefficients leads to asymmetry in the zeros of the transfer function. In particular, if $$z_{1}$$ and $$z_{1}^{*}$$ are the zeros of the transfer function, then $$\tfrac{1}{z_{1}}$$ and $$\tfrac{1}{z_{1}^{*}}$$ are also a pair of its zeros.We can use this property to group the zeros in a way that the system function is decomposed into linearphase elements. Let’s use the MATLAB command roots, to find the zeros of the system function:
N=[0.0024 0.0073 0.0606 0.1691 0.2654 0.2654 0.1691 0.0606 0.0073 0.0024];
roots(N)
Hence, we obtain:
$$z_1=1.0000$$
$$z_2=7.7465$$, $$z_3=0.1291$$
$$z_4=0.4929 + 0.8701j$$, $$z_5=0.4929  0.8701j$$
$$z_6=0.5280+0.5571j$$, $$z_7=0.52800.5571j$$
$$z_8=0.8961+0.9456j$$, $$z_9=0.89610.9456j$$
The reader can verify that $$z_2=\tfrac{1}{z_3}$$, $$z_4=\tfrac{1}{z_{5}^{*}}$$, $$z_6=\tfrac{1}{z_{8}^{*}}$$ and $$z_7=\tfrac{1}{z_{9}^{*}}$$. Then, we can pair $$z_2$$ and $$z_3$$ to obtain the following linearphase secondorder section
$$H_{LP1}(z)=(10.1291z^{1})(17.7465z^{1})=(17.8756z^{1}+z^{2})$$
Pairing $$z_4$$ and $$z_5$$ gives:
$$H_{LP2}(z)=(1(0.4929 + 0.8701j)z^{1})(1(0.4929  0.8701j)z^{1})=(1+0.9858z^{1}+z^{2})$$
Grouping $$z_6$$, $$z_7$$, $$z_8$$, and $$z_9$$ together, we obtain:
$$H_{LP3}(z)=1+2.8482z^{1}+4.1790z^{2}+2.8482z^{3}+z^{4}$$
To incorporate the zero $$z_1$$, we need to include a firstorder section, i.e. $$H_{LP4}(z)=1+z^{1}$$. A cascade of these linearphase elements will give the original system function:
$$H(z)=GH_{LP1}(z)H_{LP2}(z)H_{LP3}(z)H_{LP4}(z)$$
where $$G=0.0024$$ as before.
In general, the zeros of a linearphase FIR filter can be of four different arrangements as illustrated in Figure 5. These arrangements include: 1 a pair of complexconjugate zeros which are not on the unit circle along with their reciprocals, e.g. $$z_1$$, $$z_{1}^{*}$$, $$\tfrac{1}{z_1}$$, and $$\tfrac{1}{z_{1}^{*}}$$ in the figure, 2 a pair of complexconjugate zeros on the unit circle such as $$z_3$$ and $$z_{3}^{*}$$ in the figure, 3 a real zero which is not on the unit circle along with its reciprocal such as $$z_{2}$$ and $$\tfrac{1}{z_{2}}$$, and finally, 4 a real zero on the unit circle like $$z_4$$ in Figure 5. The system function of the above example had zeros of all these four groups.
Figure 5. The symmetry of zeros for a linearphase FIR filter. Image courtesy of DiscreteTime Signal Processing.
Factoring the system function of Example 2 into linearphase elements, we need a total of five multipliers. The following table shows the number of multipliers for each section.
However, the first realization requires nine multipliers as listed below:
In summary, we can use the tf2sos command to rewrite the system function of a FIR filter as the product of secondorder sections; however, these secondorder sections are not necessarily linearphase. To have a cascade of linearphase elements, we need to group the zeros of the transfer function appropriately. Using a cascade of linearphase sections, we can reduce the number of multiplications. Note that, in this case, some of the sections might be of order four as $$H_{LP3}(z)$$ in the above example.
Summary

There are several structures to realize a given system function $$H(z)$$. One consideration choosing the appropriate structure is the sensitivity to coefficient quantization. In addition, sometimes we observe that a particular structure can dramatically reduce the computational complexity of the system.

The symmetry property of a linearphase FIR filter can be used to reduce the number of the required multiplications.

The main advantage of the cascade structure is its smaller sensitivity to the coefficient quantization.

We can use the tf2sos command to rewrite the system function of a FIR filter as the product of secondorder sections; however, these secondorder sections are not necessarily linearphase. To have a cascade of linearphase elements, we need to group the zeros of the transfer function appropriately.
Is there a typo in the relationship z4 = 1/z5*? I guess it is z4 = z5*.