General FIR Filter Design with Linear Phase in Passband by Water Cycle Algorithm

Show more

1. Introduction

FIR filter is an important type of filter in the field of signal processing because of its inherent stability, simpler structure, and easier implementation on linear phase [1]. The linear phase is an important property of filters in many applications. If the coefficients of a FIR filter are odd symmetry or even symmetry, this FIR filter has the linear phase. The linear phase in entire frequency domain can be easily achieved using the classic design method for FIR filters. However, the symmetric coefficients are not realized by all FIR design methods, especially in the methods based on the optimizing theories. Some optimization methods can obtain very good amplification-frequency characteristic, but not realize the linear phase. Therefore how to design an asymmetric coefficient FIR filter with excellent amplification-frequency characteristic and linear phase is an interesting study [2] [3] [4] [5] [6].

Water cycle algorithm (WCA) [7] is a metaheuristic optimizer which is to solve the constrained engineering optimization problems. This algorithm simulates the process of water cycle in nature. The fundamental concept of the WCA is inspired by the observation of water cycle process, and movement of rivers and streams to the sea in the real world. In this paper we focus on FIR design with the asymmetric coefficients and the linear phase in the passband. WCA is applied in phase optimization in the process of our FIR design.

2. Principle of WCA

The same to other bionic algorithm, the idea of WCA is also inspired from nature. In our world, a river or stream is collected when water moves downhill. This means that most rivers are formed high up in the mountains, where the snow or the glaciers melt. The rivers always flow downhill. On their downhill journey and eventually ending up to a sea, water is collected from rain and other streams. Therefore, streams flow to the rivers and rivers flow to the sea.

WCA begins with an initial population which is called raindrops. So at first we have rain. The best raindrop is chosen as a sea while some good raindrops are selected as the river. Besides the sea and the river, other unselected raindrops are defined as the stream which flow to the river and the sea. For the ${N}_{var}$ dimensional optimization problem, a raindrop is defined as an array of $1\times {N}_{var}$ , which is described as follows:

$\text{Raindrop}=\left[{x}_{1},{x}_{2},{x}_{3},\cdots ,{x}_{N}\right]\text{.}$

At the beginning of WCA, a population of raindrops is generated by use of a matrix X with size ${N}_{pop}\times {N}_{var}$ which is shown as follows:

$\begin{array}{l}\text{PopulationofRaindrops}=\left[\begin{array}{c}\begin{array}{c}Raindro{p}_{1}\\ Raindro{p}_{2}\end{array}\\ \begin{array}{c}\begin{array}{c}Raindro{p}_{3}\\ \vdots \end{array}\\ Raindro{p}_{{N}_{pop}}\end{array}\end{array}\right]\\ =\left[\begin{array}{ccccc}{x}_{1}^{1}& {x}_{2}^{1}& {x}_{3}^{1}& \cdots & {x}_{{N}_{var}}^{1}\\ {x}_{1}^{2}& {x}_{2}^{2}& {x}_{3}^{2}& \cdots & {x}_{{N}_{var}}^{2}\\ \vdots & \vdots & \vdots & \vdots & \\ {x}_{1}^{{N}_{pop}}& {x}_{2}^{{N}_{pop}}& {x}_{3}^{{N}_{pop}}& \cdots & {x}_{{N}_{var}}^{{N}_{pop}}\end{array}\right].\end{array}$ (1)

In WCA, the cost of a raindrop is calculated by a cost function which is shown as follows:

${C}_{i}=Cos{t}_{i}=f\left({x}_{1}^{i},{x}_{2}^{i},{x}_{3}^{i},\cdots ,{x}_{{N}_{var}}^{i}\right),i=1,2,3,\cdots ,{N}_{pop},$ (2)

where ${N}_{pop}$ and ${N}_{var}$ are the number of raindrops (initial population) and the number of design variables, respectively. Then ${N}_{pop}$ raindrops is created and initialized, and the ${N}_{sr}$ raindrops of them which are the best individuals or minimum values are chosen as sea and rivers. Especially, a raindrop with minimum value among others is defined as sea. Therefore, ${N}_{sr}$ is sum of sea and rivers which is shown as follows:

${N}_{sr}=number\text{}of\text{}rivers+1.$ (3)

The number of other unselected raindrops is

${N}_{raindrops}={N}_{pop}-{N}_{sr}.$ (4)

WCA uses an equation to assign the raindrops to rivers and sea based on the flow intensity. This equation is

$N{S}_{n}=round\left\{\left|\frac{Cos{t}_{n}}{{{\displaystyle \sum}}_{i=1}^{{N}_{sr}}Cos{t}_{i}}\right|\times {N}_{raindrops}\right\},n=1,2,3,\cdots ,{N}_{sr},$ (5)

where $N{S}_{n}$ is the number of streams which flow to the particular rivers or sea.

In WCA, all streams and rivers flow to sea. Obviously sea is the best optimal point. A stream flows to the river along the connecting line between them using a randomly selected distance that is shown as follows:

$\text{X}\in \left(0,C\times d\right),C>1,$ (6)

where C is a value between 1 and 2 and near 2 (best value is 2), d is the current distance between stream and river, respectively. X is a random number between 0 and $C\times d$ . C enables streams to flow in different directions towards the rivers. Similarly, C also can be used for the water flow from river to sea. So, the new position for streams and rivers are shown as follows:

${X}_{stream}^{i+1}={X}_{stream}^{i}+rand\times C\times \left({X}_{river}^{i}-{X}_{stream}^{i}\right),$ (7a)

${X}_{stream}^{i+1}={X}_{stream}^{i}+rand\times C\times \left({X}_{sea}^{i}-{X}_{stream}^{i}\right),$ (7b)

${X}_{river}^{i+1}={X}_{river}^{i}+rand\times C\times \left({X}_{sea}^{i}-{X}_{river}^{i}\right),$ (8)

where rand is random number between 0 and 1. If the solution from a stream is better than its connecting river, the positions of stream and river are exchanged each other. Similarly, if the solution from a river is better than sea, the positions of river and sea are exchanged each other. Therefore, a river should be considered as a locally optimal solution, while sea should be considered as the globally optimal solution.

Evaporation is a method to prevent the algorithm from rapid convergence (immature convergence). In WCA, the evaporation process causes the sea water to evaporate as rivers/streams flow to the sea. This method is proposed in order to avoid getting trapped in local optima. The following pseudo code shows how to determine whether or not river flows to the sea.

If

$\left|{X}_{sea}^{i}-{X}_{river}^{i}\right|<{d}_{\mathrm{max}},i=1,2,3,\cdots ,{N}_{sr}-1$

Evaporation and raining process

End

Where ${d}_{\mathrm{max}}$ is a small value which is close to zero. Therefore, if the distance between a river and sea is less than ${d}_{\mathrm{max}}$ , it means that the river has reached or joined the sea. In this situation, the evaporation process is used and as seen in the nature after some adequate evaporation the raining will start. A large value for ${d}_{\mathrm{max}}$ reduces the search while a small value encourages the search intensity near the sea. Therefore, ${d}_{\mathrm{max}}$ controls the search intensity near the sea (the optimum solution). In original WCA, the value of ${d}_{\mathrm{max}}$ can be decreased adaptively as:

${d}_{\mathrm{max}}^{i+1}={d}_{\mathrm{max}}^{i}-\frac{{d}_{\mathrm{max}}^{i}}{\mathrm{max}iteration}.$ (9)

After satisfying the evaporation process, the raining process is applied. In the raining process, the new raindrops form streams in the different locations (acting similar to mutation operator in GA). For specifying the new locations of the newly formed streams, the following equation is used:

${X}_{stream}^{new}=LB+rand\times \left(UB-LB\right),$ (10)

where LB and UB are lower and upper bounds defined by the given problem, respectively. The rest of new raindrops are assumed to form new streams which flow to the rivers or may directly flow to the sea.

3. Prepare Your Paper before Styling

3.1. Example 1

We use WCA to implement a general FIR with passband linear group delay design. For lowpass filter example: Filter order = 24, ${w}_{p}=0.3\pi ,{w}_{s}=0.4\pi $ , passband group delay = 10.

In this design, we use the smallest group delay in passband as object function, amplitude error in passband and stopband as constraint condition. Therefore a general FIR design can be described as follows:

$\mathrm{min}f\left(X\right)={\Vert {H}^{pb}-1\Vert}_{2}+{\Vert {H}^{sb}\Vert}_{2}$ ,

$\text{s}\text{.t}\text{.}{\Vert GroupDela{y}^{pb}\left(X\right)-G{d}_{ideal}\Vert}_{2}<{\tau}^{pb}$ ,

where ${\tau}^{pb}$ is the presetting values. In our design, the population is 100, the number of sea and rivers is 8, and the iteration is 2000, respectively.

Our all filter designs are realized in Matlab R2009b. WCA function is obtained from [8]. Figure 1 shows the performance of design result by our proposed method. From Figure 1, we can know the magnitude-frequency characteristicmeets the requirement while the group delay in passband is the approximate linearization.

3.2. Example 2

In this example, we also use single-object WCA to implement a general FIR design. For bandpass filter example: Filter order = 24, ${w}_{s1}=0.25\pi $ , ${w}_{p1}=0.35\pi $ , ${w}_{p2}=0.6\pi $ , ${w}_{s2}=0.7\pi $ , passband group delay = 14. From Figure 2, we also we can know the magnitude-frequency characteristic meets the requirement while the group delay in passband is the approximate linearization.

Figure 1. Performance of design result for example 1.

Figure 2. Performance of design result for example 2.

4. Conclusion

In this paper we use WCA to solve FIR filter design with low magnitude error and linear phase in passband. This method uses WCA to optimize the filter coefficient based on the low magnitude errors in all frequency domains. Moreover, in the constraint conditions, the least group delay in passband is used for the optimization. The experiments testify this method has good performance on the passband error and group delay error in the passband. Therefore this method is an efficient algorithm for FIR filter optimization which can be used in the digital signal processing widely.

Acknowledgements

The generous support of the Discipline Construction Fund of SSPU (XXKZD1605) and the Construction of University Enterprise Cooperation Automobile Electronic Joint Experiment Center (A11NH182016) are gratefully acknowledged.

References

[1] Beylkin, G., Lewis, R.D. and Monzón, L. (2012) On the Design of Highly Accurate and Efficient IIR and FIR Filters. IEEE Transactions on Signal Processing, 60, 4045-4054. https://doi.org/10.1109/TSP.2012.2197397

[2] Longpiur, R.C., Shpak, D.J. and Antoniou, A. (2013) Improved Design Method for Nearly Linear-Phase IIR Filters Using Constrained Optimization. IEEE Transactions on Signal Processing, 61, 895-906. https://doi.org/10.1109/TSP.2012.2231678

[3] Wu, C., Gao, D. and Teo, K.L. (2013) A Direct Optimization Method for Low Group Delay FIR Filter Design. Signal Process, 93, 1764-1772.
https://doi.org/10.1016/j.sigpro.2013.01.015

[4] Lai, X., Lai, C. and Zhao, R. (2011) An Iterative Approach to Near-Uniform Group- Delay Error Design of FIR Filters. IEEE Signal Process. Lett., 18, 107-110.
https://doi.org/10.1109/LSP.2010.2099217

[5] Chui, K.M., Chan, S.C. and Yeung, K.S. (2005) Design of FIR Digital Filters with Prescribed Flatness and Peak Error Constraints Using Second-Order Cone Programming. IEEE Trans. Circuits Syst. II, 52, 601-605.
https://doi.org/10.1109/TCSII.2005.850515

[6] Lai, X. (2009) Optimal Design of Nonlinear-Phase FIR Filters with Prescribed Phase Error. IEEE Trans. Signal Process., 57, 3399-3410.
https://doi.org/10.1109/TSP.2009.2021639

[7] Eskandar, H., Sadollah, A., Bahreininejad, A., et al. (2012) Water Cycle Algorithm— A Novel Metaheuristic Optimization Method for Solving Constrained Engineering Optimization Problems. Computers & Structures, 110, 151-166.
https://doi.org/10.1109/TSP.2009.2021639