L₁-Norm and LMS Based Digital FIR Filters Design Using Evolutionary Algorithms

Abstract

The suggested work in this paper involves the construction of digital filters by utilizing optimization algorithms to compute optimum filter coefficients in such a way that the designed filter's magnitude response is identical to the ideal one. The proposed work takes a nature-inspired approach to optimizing the design of 20th order linear phase finite impulse response (FIR) based low pass, high pass and band pass filters. This approach involves the cuckoo search optimization algorithm (CSA) and Grasshopper optimization algorithms (GOA) by minimizing the least mean square error function and L₁-norm based ones. These GOA and CSA are used to find the best possible values for the filter coefficients. The bench mark algorithm to design the FIR filter as Parks–McClellan approach and other recently published optimization algorithms are used to prove the superiority of proposed designs. Compared with PM method, real coded genetic algorithm, Cat swarm, Particle swarm optimization and some hybrid optimization based ones, the proposed design results have been outperform. Moreover, the proposed FIR filters give the best outcome, effectively meeting the target with decreased pass band ripples and higher attenuation in the stop band with a least execution time.

1 Introduction

The word "filtering" refers to the method through which frequency spectrum is altered, reshaped, or otherwise manipulated in accordance with a set of rules or criteria. A digital filter is a filtering system or device that processes digital data to produce a discrete signal. One of the most important components of digital signal processing is the filter, which has applications in many fields, including but not limited to biomedical image processing, communication systems, speech processing, and audio signal processing [1]. The detection of ECG signal using adaptive Autoregressive Modeling and various non-linear techniques are presented by Varun et al. [2,3,4,5,6]. Filtering concept plays an important role to preprocessing the raw ECG data, which is explained in [7, 8]. Recently, Fractional Fourier transform concepts, [9,10,11,12] and Optimization techniques, [13,14,15] are used to analyze the ECG and EEG signals to improve the health monitoring. Especially, [9] Fractional Fourier transform used to extract the features of raw ECG signal. Due to this, noise can be easily separated without disturbing pathological information. In [13], a digital BPF with lower and upper cut-off frequencies of 5 and 22 Hz respectively proposed to pre-process the ECG data i.e. to reject the distortions due to power line interference (PLI), baseline wander (BLW) noise.

Two primary categories of the filters are finite and infinite impulse response (recursive). One of the important aspects of FIR filter is linear phase response, which causes there is no delay distortion involved when the signal is passed through the filter and also inherently built in stability character. Researchers still find the design and implementation of digital filters to be a fascinating issue, since they face numerous difficulties in limiting waves in the pass band, stop band and in amplifying weakening in the stop band with the smallest feasible filter order. They are employing recently developed nature-inspired algorithms to work on the objective issue of maintaining a trade-off between several requirements. In the past, two techniques namely windowing approach [1] and frequency sampling methods, [16] are widely used to construct digital filters. Windowing based design depends on parameter specifications, type of window such as Kaiser, Blackman etc. for designing the FIR filter but does not gets a accurate results over edge frequencies and transmission bandwidth. Moreover, window techniques cause side lobe energy due to the presence of side lobes. The frequency sampling method, which controls the filter response by sampling it at N equally spaced points and gets a desired response but there, will be a discontinuity at near stop band. Traditional approaches have limitations, such as lesser stop band attenuation, maximum ripples present in the pass band and also less convergence speed due to the higher order of filter. In these techniques, there is a trade-off between the filter order and computational complexity. As order of filter increases the response is better, but the computation time as well complexity increase and vice versa. The Parks-McClellan method uses different iterations based on the error criteria to obtain the FIR filter coefficients.

The main intention of all creatures is the survival. To get this, they have been developing and transforming the different methods. Hence, it is intelligent to seek motivation from the nature. So, the most of the researchers are attractive towards nature inspired optimization algorithms than the conventional methodologies. Moreover, these algorithms are useful to estimating the solutions by using objective or fitness functions and also, provide group of random solutions for a given difficulty. In the literature different meta-heuristic methods are employed to calculate the global optimum solution with respect to circumvent these kinds of problem, [17, 18]. Several works carried out for the design of digital FIR filters with the use of optimization methods.

Researchers may choose from a plethora of newly developed meta-heuristic evolutionary algorithms that use meta-heuristic methods for FIR filter design and implementation. Genetic algorithms (GA) [17], real-coded genetic algorithms (RCGA) [19], differential evolution (DE) [20], particle swarm improvement (PSO) [21], ant colony optimization (ACO) [18] and Simulated annealing [22] are only a few examples. Performance comparison of FIR digital filters using optimization techniques like artificial bee colony (ABC), PSO are explained in [23]. Seventh order band stop FIR design using Jaya optimization algorithm are presented in [24]. Cat swarm based optimization technique for the design of various FIR filters are listed in [19]. Some of the researchers used hybrid optimization algorithms to improve the design of FIR filters namely DEPSO [25] and HGWOCS [26]. 1-norm optimization used in the design of sparse FIR filters are given in [27] and multi dimensional FIR coefficients obtained by the application of min–max design methodology presented in [28]. Implementation of FIR filters are also plays an important role in the real time environment [29]. Linear phase FIR design and implementation in Virtex 6 field programmable gate array (FPGA) are presented in [30]. Implementation of distributed arithmetic FIR filters using FPGA are presented in [31]. Differential evolution approach used in design of FIR filter and its transposed direct form implementation is explained in [32]. Recently, Grasshopper optimization based FIR filter are designed by considering absolute difference error as a fitness function, [33]. The aforementioned algorithms suffer from issues such as early convergence, ripples in pass band and stop band. To overcome these problems this work provide an enhanced version of the cuckoo search and Grasshopper methods by introducing the L₁- norm and least mean square (LMS) error based fitness functions for application in the creation of FIR filters.

The paper is arranged as follows. The problem formation of digital FIR design with objective functions are explained in Sect. 2. In Sect. 3, swarm based Grasshopper optimization and Cuckoo search algorithms are presented. Determination of optimum filter coefficients and simulation results using MATLAB are discussed in Sect. 4. Finally, conclusion remarks are given in Sect. 5.

2 Problem Formation

The FIR filter's transfer function can be expressed as

$$A\left(z\right)=\sum_{n=0}^{N-1}a\left(n\right){z}^{-n}$$

(1)

here $a\left(n\right)$ is the impulse response of the filter and $N$ is the length of the filter. FIR filter's frequency response is given by

$$A\left(\omega \right)=\sum_{n=0}^{N-1}a\left(n\right){e}^{-j\omega n}$$

(2)

As part of this work, we used a type-1 FIR filter with even symmetry and odd length, which may be used for low-pass, high-pass and band-pass applications. It is an important to take into account the length $(N=21)$ of the FIR filters as well as the specified specifications, which include smaller pass band ripples and more stop band attenuation. Consider the frequency response of type 1 linear phase FIR filter as

$$A\left(\omega \right)=\sum_{n=0}^{\left(N-1\right)/2}a\left(n\right) cos\omega n$$

(3)

The above (3) can be modified for the length 21 (i.e. odd length with even symmetric) as

$$A\left(\omega \right)=a\left(0\right)+\sum_{n=1}^{10}a\left(n\right) cos\omega n$$

(4)

where the coefficients are $a\left(0\right)=h\left(\frac{N-1}{2}\right)$ and $a\left(n\right)=h\left(\frac{N-1}{2}-n\right)$.The magnitude response of ideal low pass (LP), high pass (HP) and band pass (BP) filters can be defined as

$${A}_{ideal\_LP}\left(\omega \right)=\left\{\begin{array}{c}1;\,\quad \omega \le \left|{\omega }_{c}\right|\\ 0;\,\quad elsewhere\end{array}\right.$$

(5)

$${A}_{ideal\_HP}\left(\omega \right)=\left\{\begin{array}{c}0;\, \quad \omega \le \left|{\omega }_{c}\right|\\ 1;\,\quad elsewhere\end{array}\right.$$

(6)

$${A}_{ideal\_BP}\left(\omega \right)=\left\{\begin{array}{c}1;\quad {\omega }_{c1}\le \omega \le {\omega }_{c2}\\ 0;\quad elsewhere\end{array}\right.$$

(7)

where ${\omega }_{c}$ is the cutoff frequency for both LP and HP filters. Two cutoff frequencies in the pass band region of BP filter are${\omega }_{c1}$, ${\omega }_{c2}$ respectively. In the optimization based problems, fitness function plays an important role on its performance. When creating a digital FIR filter, it's crucial to employ a suitable fitness function. If a variety of error fitness functions are applied to the same issue, a variety of distinct solutions emerge. To get the desired results, proper error function selection is required. Mostly three types of error functions are considered as minmax error, absolute mean error and least mean squared error. In this paper two fitness functions are considered one is fitness function${F}_{1}$, which is ${L}_{1}$ norm based one with ${\delta }_{p}/{\delta }_{s}=10$ and another is,${F}_{2}$, which is Least mean square error based function.

$${F}_{1}=\sum_{\omega <{\omega }_{C}}\left|\left|\left|A\left(\omega \right)\right|-\left|{A}_{ideal}\left(\omega \right)\right|\right|-{\delta }_{p}\right|+\sum\limits_{{\omega }_{C}<\omega <\pi }\left|\left|\left|A\left(\omega \right)\right|-\left|{A}_{ideal}\left(\omega \right)\right|\right|-{\delta }_{s}\right|$$

(8)

where,${\delta }_{p}=0.1$ and ${\delta }_{s}=0.01$ are the maximum pass-band and stop-band ripple levels that may be tolerated in a FIR filter design. Least mean square error based function (LMS) can be represented as

$${F}_{2}=\sum_{<\omega >}{\left(\left|{A}_{ideal}\left(\omega \right)\right|-\left|A\left(\omega \right)\right|\right)}^{2}$$

(9)

where $A\left(\omega \right)$ and ${A}_{ideal}\left(\omega \right)$ are the designed and ideal magnitude responses of the filter.

3 Evolutionary Algorithms

3.1 Grasshopper Optimization Algorithm

While grasshoppers may be seen alone in the wild, they can produce one of the biggest swarms of any insect. Both nymphs and adults exhibit swarming behavior [34]. During their larval (nymph) stage, they move very slowly and in very little steps, but as adults, they either move very swiftly or leap. Looking for food, grasshoppers are affected by their social interactions with other insects, the force of gravity, and the direction of the wind. In addition to the forces considered in calculating the grasshopper's future location, gravity is also present but ignored. The first component of in (10) takes into account the current grasshopper's position in relation to other grasshoppers. In GOA a search agent's next position $\left({Y}_{t+1}\right)$ depending based on where it was, where it has to go, and where the other grasshoppers are right now.

$${Y}_{i}^{d}=c\left(\sum_{j=1}^{\mathrm{N}}c\frac{u{b}_{d}-l{b}_{d}}{2}S\left(\left|{y}_{d}^{j}-{y}_{i}^{d}\right|\right)\frac{{y}_{j}-{y}_{d}}{{d}_{ij}}\right)+{T}_{d}$$

(10)

Here $S$ is the social force applied on the grasshopper, $u{b}_{d}$ and $l{b}_{d}$ are the upper limit and lower limits of having dth dimension, ${T}_{d}$ is the target position and $c$ have some parametric specifications. Now,

$$c={C}_{max}+l\left[\frac{{C}_{min}-{C}_{max}}{L}\right]$$

(11)

In (11), $L$ represents the maximum number of iterations, which may range from 1 to infinity and $c$ is continuously updated in (11).

The work flow for the FIR design using grasshopper optimization technique is mentioned in Fig. 1. The step wise procedure as follows.

• 1. Specify the edge frequency $\left({\omega }_{c}\right)$, lower cut-off frequency $\left({\omega }_{c1}\right)$, higher cut off frequency $\left({\omega }_{c2}\right)$, length of filter,$N$, pass-band ripple $\left({\delta }_{p}\right)$ and stop band ripple $\left({\delta }_{S}\right)$ for FIR filter.

• 2. Initialize number of search agents $\left(\mathrm{N}\right)$, ${C}_{max}$, ${C}_{min}$ and maximum number of iterations $\left(L\right)$.

• 3. Initialize population of search agents ${Y}_{i}\left(t\right)$ has dimension equal to $a\left(n\right)$.

• 4. Calculate fitness values for each ${Y}_{i}\left(t\right)$ using (8) and (9).

• 5. Calculate new search agent position ${Y}_{i}\left(t+1\right)$ for grasshoppers using (10).

• 6. Calculate fitness value $F\left({Y}_{i}\left(t\right)\right)$ for new search agent position ${Y}_{i}\left(t+1\right)$.

• 7. Contrast the wellness and new (target) solution $F\left({Y}_{i}\left(t+1\right)\right)$ and other potential arrangements (search agent) fitness $F\left({X}_{i}\left(t\right)\right)$. If $F\left({Y}_{i}\left(t+1\right)\right)<F\left({Y}_{i}\left(t\right)\right)$ replace by ${Y}_{i}\left(t+1\right)$ and follow the next step. If $F\left({Y}_{i}\left(t+1\right)\right)>F\left({Y}_{i}\left(t\right)\right)$, then increase counter by 1, until it reaches its maximum value or not abandon that solution until built new search agent (solutions) using (10).

• 8. Check whether wellness worth of $F\left({Y}_{i}\left(t+1\right)\right)\le F\left({Y}_{i}\left(t\right)\right)$ best search agent $(t + 1)$ as $a\left(n\right)$. Whether that's not the case, see if the maximum iterations have been reached. If this is the case, you should exit the software and begin the optimization process again, this time using new values for the design and control parameters. If it is not the finest possible location, return to step 5 and try again.

Fig. 1

Flow chat for FIR filter design using GOA algorithm

3.2 Cuckoo Search Optimization Algorithm

Cuckoo search was presented as a streamlining strategy in 2009 by Yang and Deb. The CSA idea depends on the brood parasitic way of behaving of some cuckoo flavours and the Toll flying instrument of natural product flies [35]. Alternatively, Levy flight refers to a species-specific random walk where the step size and direction are determined at random in nature. Intra-explicit brood parasitism, agreeable rearing, and home takeover are the three main kinds of brood parasitism recognized in CSA. According to the foundational principles of CSA, each Cuckoo may lay each egg in turn, which is then placed into a haphazardly chosen home, and the best home (ideal arrangement) containing great eggs is passed down to the future. In the event that the host bird finds the egg with likelihood ${p}_{a}$, which is in the reach [0, 1]. The best nest is identified as the one with the lowest value of fitness function, which is calculated for each possible solution. Using Levy flight, new solutions (such as this host nest) are generated. The following equation describes the Levy flight mechanism:

$$x_i^{m + 1} = x_i^m + \alpha ~ \oplus ~L\dot{e}vy\left( \lambda \right)$$

(12)

where ${x}_{i}^{m}$ is the current (nest) solution and ${x}_{i}^{m+1}$ is the (nest) solution in next iteration. Here $\alpha >0$ is the step size, which can be used as a scaling factor and $\lambda$ is the Lévy index which controls the Lévy mechanism when step size is large and the applied power law is as follows:

$$L\dot{e}vy\left(x\right)={m}^{-\lambda }, \left(1<\lambda \le 3\right)$$

(13)

Finally, the fitness function is calculated and applied to each fresh set of solutions. The conventional fitness model is contrasted with the modern one. If the new one is superior than the old one, then there is a certain likelihood, denoted by the proportion ${p}_{a}$, that the nests will be worse than the old ones. The consequence is the so-called "abandoned nest" solution and the most prestigious roost is protected. As long as the greatest fitness value for the best nest is being achieved. Figure 2, shows the flow diagram for the FIR design using CSA and the procedure for FIR filter design as follows.

• 1. Firstly, specify the edge frequency $\left({\omega }_{c}\right)$, lower cut-off frequency (${\omega }_{c1}$), higher cut off frequency (${\omega }_{c2}$), length of the filter,$N$, pass-band ripple $\left({\delta }_{p}\right)$ and stop band ripple $\left({\delta }_{s}\right)$ for FIR filter.

• 2. Initialize number of host nests (N), $\alpha$ and ${p}_{a}$ within the range [0, 1], maximum number of iterations (L).

• 3. Make initial population of the host nests ${x}_{i}^{m}$ has dimension equal to $a\left(n\right)$.

• 4. Calculate fitness value (F) for each ${x}_{i}^{m}$ using (8) and (9).

• 5. Generate new solution (position) using (12) and calculate fitness value $F\left({X}_{i}\left(m+1\right)\right)$ for new search agent position ${X}_{i}\left(m+1\right)$.

• 6. Compare the fitness with new solution $F\left({X}_{i}\left(m+1\right)\right)$ and other possible solutions (search agent) fitness $F\left({X}_{i}\left(m\right)\right)$. If $F\left({X}_{i}\left(m+1\right)\right)<F\left({X}_{i}\left(m\right)\right)$, replace ${X}_{i}\left(m\right)$ by ${X}_{i}\left(m+1\right)$ and follow the next step. If $F\left({X}_{i}\left(m+1\right)\right)>F\left({X}_{i}\left(m\right)\right)$, then increase the counter by 1, until it reaches its maximum value or not abandon that solution built new search agent (solutions) using (12).

• 7. Select best solution from the desired solution $best\left({X}_{i}\left(m+1\right)\right)$. On the off chance that indeed, plan FIR filter utilizing best $F\left({X}_{i}\left(m+1\right)\right)$ as $a\left(n\right)$ and stop the enhancement calculation strategy. Whether not, then check whether the cutoff has been gone after emphases. If so, halt the process and begin the optimization phase once again, this time using a different value for the design and a new set of control parameters. In the event that this is not the case, go to step 5 and keep trying until find the optimal solution.

Fig. 2

Flow chat for FIR filters design using CSA

4 Simulation Results

In this work taken the both ${L}_{1}$ norm and LMS error based fitness functions to evaluate the GOA and CSA optimization algorithms. The simulations are carried out using MATLAB R2021a simulation software with an Intel Core i5 processor, running at 2.70 GHz, and 4 GB of RAM. These algorithms are run around 50 times, with each trial slightly modifying the method parameters and filter specifications, until the optimal result is reached. The considered control parameters to design of FIR filters using GOA and CSA are listed in Table 1. These results are also compared with the one of finest algorithm, Parks-McClellan approach.

Table 1 Control parameters of GOA and CSA algorithms

4.1 Low Pass Filter Design

The specifications of low pass filter chosen as cutoff frequency, ${\omega }_{c}=0.4\pi$ and filter length, $N=21$. Each iteration of the GOA and CSA algorithm relies on an evaluation of the error fitness functions described by (8) and (9). The obtained optimum low pass filter coefficients are listed in Table 2. The LP filter magnitude response and its dB scale plots based on CSA and GOA algorithms are shown in Figs. 3 and 4. Based on the magnitude plot, it is clear that the GOA with LMS based function gives better response compared to the CSA and PM methods. From the Table 5, it is clear that the minimum pass band ripple of GOA with ${F}_{2}$ is 0.000361 (normalized) and maximum stop band attenuation of 69.0788 dB, which are more effective than the existed algorithms.

Table 2 The coefficients of 20th order low pass FIR filter

Fig. 3

20th order Low pass filter magnitude response

Fig. 4.

20th order Low pass filter magnitude response in dB

4.2 High Pass Filter Design

The specifications of high pass filter chosen as cutoff frequency of ${\omega }_{c}=0.4\pi$, and filter length, $N=21$. The derived optimum filter coefficients of high pass filter using CSA and GOA with ${L}_{1}$ norm and LMS based fitness functions mentioned are listed in Table 3. The magnitude response of designed FIR high pass filter both normalized and dB scale are shown in Figs. 5 and 6. Also, observed that the superiority of CSA with an ${L}_{1}$ norm-based fitness function by getting lower pass band ripple value and increased attenuation in the stop band region. The pass band ripple and stop attenuation for CSA with ${F}_{1}$ based one are 0.0004924 (normalized) and 66.15 dB, which are better compared existed techniques (see Table 6).

Table 3 The coefficients of 20th order high pass FIR filter

Fig. 5

Magnitude response of 20th order High pass filter

Fig. 6

Magnitude response of 20th order High pass filter in dB

4.3 Band Pass Filter Design

Choose the two cutoff frequencies, ${\omega }_{c1}=0.3\pi$, ${\omega }_{c2}=0.7\pi$ and filter length, $N=21$ in the design of band pass filter. Equations (8) and (9) establish the error fitness function that is employed by the optimization algorithms namely CSA and GOA and is tested at each iteration to determine the best possible outcome. The filter coefficients are constrained to values between $-1$ and $+1$. Table 4 contains the 20th order filter coefficients and the FIR filter is created and contrasted with the best reaction of the filter. Figures 7 and 8, shows the magnitude response comparison of the band pass filters based on CSA, GOA and PM methods and noticed that the ${L}_{1}$-norm based CSA have more effective in terms of pass band ripple as 0.0020 (normalized) and stop band attenuation of 53.8289 dB than the other methods (see Table 7).

Table 4 The coefficients of 20th order band pass FIR filter

Fig. 7

20th order Band pass filter magnitude response

Fig. 8

20th order Band pass filter magnitude response in dB

4.4 Performance Comparison of Proposed FIR Design with Existed Designs

The performance metrics like pass band ripple and maximum stop attenuations values are considered to evaluate the FIR magnitude response. Tables 5, 6, 7, shows the performance comparison of proposed FIR LP, HP and BP filters using CSA, GOA methods with Parks-McClellan (PM) and also the other popular existed algorithms like Particle swarm optimization, real coded genetic algorithm etc. It is evident that the GOA with ${F}_{2}$ based FIR low pass and CSA with ${F}_{1}$ used band pass and high pass filters have less pass band ripple values of 0.000361, 0.0020, 0.0004924 compared to the existed works. GOA with the application of ${F}_{2}$ used FIR LP gives the more stop band attenuation of 69.0788 dB compared to the other designs and CSA with ${F}_{1}$ used FIR HP and BP filters have 66.1526 dB, 53.8289 dB stop band attenuation values, which are better compared to the reported algorithms. Hence, it is clear that the GOA using LMS based fitness function of FIR LP gave better response compared to the other designs. Also, Cuckoo Search optimization algorithm using ${L}_{1}$ norm based fitness function have more effectives in the FIR HP and BP filter design compared to the PM approach and well known existing PSO, RCGA, Cat swarm optimization algorithms in terms of its pass band ripple values and stop band attenuations.

Table 5 Performance comparison of FIR LP filter with existed ones

Table 6 Performance comparison of FIR HP filter with existed ones

Table 7 Performance comparison of FIR BP filter with existed ones

5 Conclusion

This work proposes a ${L}_{1}$ norm and least mean square error based cuckoo search optimization algorithm (CSA) and Grass hopper optimization (GOA) to design of 20th order digital FIR low pass, high pass and band pass filters with optimal parameters and compares these designs with Parks-McClellan (PM) method as well the popular existing methods like PSO and RCGA in terms of how closely these approaches the ideal response of the filters. By utilizing optimization techniques to determine the minimum value of a fitness function, we have been able to derive the filter coefficients for the LP, HP and BP filters. By considering parameters as pass band ripple and stop band attenuation values, we can estimate performance of digital FIR filters. Finally, we conclude that the proposed algorithm with ${L}_{1}$-norm and LMS based fitness functions are more effective in terms of reduced ripples in the pass band and higher attenuation in the stop band regions.