Differential Evolution Method for the Optimal Design of Digital High Pass FIR Filter

Differential Evolution Method for the Optimal Design of Digital High Pass FIR Filter

Prabhjot Kaur

Giani Zail Singh Campus College of Engineering and Technology, Bathinda

Balraj Singh

Giani Zail Singh Campus College of Engineering and Technology, Bathinda

AbstractDigital filters with the demand of good performance are generally used in the present era of communication and computation systems. Its a challengeful task to design the digital filter that would satisfy all the necessary and sufficient conditions. This paper demonstrates the design of linear phase digital finite impulse response (FIR) filter with ten different mutation strategies of differential evolution (DE) algorithm. DE is arguably most powerful, population based stochastic and real parameter algorithm. The capability of fast convergence speed, robustness and simplicity makes DE algorithm stronger over other evolutionary algorithms. The proposed DE algorithm augments the capability of exploring and exploiting the continuous search space locally as well as globally. The multivariable DE method is employed as a design criterion to determine the frequency response and to obtain the optimal coefficients of digital FIR high pass filter. Magnitude errors and ripple magnitudes of pass band and stop band have been minimized. The computational results authenticates that the proposed DE method can obtain better digital FIR filter than the other existing methods.

KeywordsDigital FIR filter, differential evolution algorithm, particle swarm optimization, multivariable, ripple magnitude of pass band and stop band.

1. INTRODUCTION

   Digital filter is a essential part of digital signal processing system, which extracts useful information from the information bearing signal, by suppressing certain range of frequencies and by passing the desired range of frequencies. They are classified into two categories on the basis of their impulse response as: finite impulse response (FIR) filters and infinite impulse response (IIR) filters. FIR filters are more suitable than IIR filters in most of the cases because of their linear phase response at all frequencies, guaranteed stability, simplicity and low coefficient sensitivity etc [5].

   Digital FIR filters can be designed with various methods such as window method, frequency sampling technique, least squared error frequency domain technique. From all these methods window method is most popular. Variety of windows (Kaiser, Blackman, Rectangular, Hanning etc.) limits the infinite impulse response of ideal filter into finite window so that actual response can be obtained. But the window based methods do not provide sufficient and precise control of frequency response in the various frequency bands and some other window parameters like transition width etc.

   So, Chebyshev approximation methods was developed by Parks and McClellan, which is better than other traditional techniques but it also have problem of computational complexity and high pass band ripples. An iterative computer

   program was also explained for the design of digital FIR filter [1].

   For the optimal design of digital filters, objective function requires accurate and precise control of various control parameters. Thus due to its highly non-uniform, multimodal, non-linear and non-differentiable nature classical methods cannot converge to global optimum solution. Hence to tackle the complex computational problems, nature based heuristic and stochastic optimization techniques have been developed such as genetic algorithm, particle swarm optimization, differential evolution, immune algorithm and artificial bee colony etc [10, 12, 13].

   The idea of GA was pioneered by Holland and Goldberg. It gives better results than window based method and parks McClellan method. But it may get trapped in local minima of objective function, when there are number of control parameters and numerous local minima [2, 3, 6]. An alternative solution was given by Eberhart and Keneddy for complex optimization problems that was inspired by animals social behavior such as bird flocking etc. named as particle swarm optimization. But it also exhibits the limitation of occurrence of divergent particle trajectories if any parameter of PSO has been chosen incorrectly. This results in trapping of local minima [4].

   Price and Storn developed meta heuristic approach which is known as differential evolution for minimizing non-linear, non-uniform, multimodal and non-differentiable continuous space problem with penalty function. Numerous engineering applications have benefitted from the powerful nature of DE. DE has number of advantages like simplicity, low space complexity, parallel processing nature, fast convergence, few control parameters, ability to find true global minima regardless of initial parameters and provide multiple solutions in a single run [7].

   The objective of this paper is to purpose DE method for optimal design of linear phase FIR high pass filter. Optimized filter coefficients have been obtained with DE that closely matches the ideal frequency response. Lp -norm approximation errors and ripple magnitudes of both pass band and stop band have been calculated as objective function for optimization problem. Simulation results illustrate the effectiveness and the better performance of proposed DE algorithm.

   The remaining paper is organized in four sections. Section II formulates the design problem for the optimal design of linear phase digital FIR filter. Section III briefly discusses the various design steps of DE algorithm with ten different

   mutation strategies. Section IV discusses the results and performance of DE algorithm and compares the proposed algorithm with other design algorithms. Finally section V concludes the paper with DE algorithm.

   sampled into equal frequency intervals and error function is obtained from difference between them as in (Eq. 6). The approximation criteria with p=1 and p=2 is most popular for

   M

   M

   the filter design problems. Hence for p=1, E1 represents the

   E

   E

   M

   M

2. DIGITAL FIR FILTER DESIGN PROBLEM absolute error (i.e. L1-norm of magnitude response) and for

   Digital FIR filter is a non-recursive filter. In the design

   p=2, 2

   represents the squared error (i.e. L2-norm of

   problem of digital FIR filter a set of filter coefficients is determined, that should meet the desired performance

   magnitude response).

   specifications of pass band width and its gain, stop band width and its attenuation and tolerable peak ripples of both pass band and stop band.

   T (k

   ) 1

   0

   for

   for

   k passband

   k stopband

   (7)

   The realization of digital FIR filter is governed by the following non-recursive equation:

   Let p (x) and s (x) be the ripple magnitude of both pass

   band and stop band respectively and defined as follows:

   L p (x) max H (k , x) minH (k , x)

   (8)

   y(n) an x(n L)

   n0

   (1)

   for

   k k

   k passbandand

   where y(n) and x(n) indicates the output and input of s (x) max H (k , x)

   (9)

   digital FIR filter respectively. an represents the set of k

   coefficients. The output of digital FIR filter can also be obtained from the convolution of unit impulse response and input data sequence. The transfer function of digital FIR filter is expressed as:

   for k stopband

   In the multiple criterion constrained optimization of designing the digital FIR filter a single non-inferior point ca be found by calculating the following equation:

   H (z)

   h(n)z n

   (2)

   min F(x) minw E1

   (x) w E 2 (x) w

   (x) w4 s (x)

   L

   L

   n0 x

   where L is the order of filter which gives (L+1) impulse response coefficients. h(n) is the impulse response of digital

   x 1 M

   2 M 3 p

   (10)

   FIR filter and also determines the type of filter (i.e. high pass).

   Phase distortion can be avoided by ensuring linear phase characteristics in the pass band, which can be ensured if impulse response is either symmetric (Eq. 3) or anti symmetric (Eq. 4)

   h(n) h(L n), 0 n L , for even (3)

   h(n) h(L n), 0 n L , for odd (4)

   In this paper, symmetric property of impulse response is

   where F(x) is the objective function that is to be

   minimized and w1, w2 , w3 and w4 are the non negative real numbers, named as weights.

3. DE APPROACH FOR DESIGNING DIGITAL FIR FILTER

   DE is a population based stochastic method introduced by Storn and Price in 1995. DE is the encoded floating point evolutionary search technique for global optimization. It is a heuristic algorithm for minimizing non-linear and non-

   used. So, only half of the coefficients L

   2

   are required to

   1

   1

   differentiable continuous space functions using the operators like crossover, mutation and selection. Main operator is based

   design digital FIR high pass filter and other half of coefficients are obtained by concatenation.

   L

   L

   The frequency response of digital FIR filter with impulse response h(n) is given as:

   on the differences of randomly sampled pairs of solutions in the population [8]. Main steps of DE algorithm are explained as follows:

   A. Mutation

   H (e jk )

   h(n)e jk n n0

   (5)

   Biologically mutation means the sudden change in characteristics of a gene that is related to chromosome. Mutation operation actually expands the search space to find

   where k 2k ;k=0,1,2,,M and M=200 samples. The

   M

   performance of digital FIR filter can be evaluated by specified objective function in terms of Lp -norm approximation errors and ripple magnitude of both pass band and stop band.

   1

   global optimal solution for any problem. For the exploration of search space parameter vectors of existing population are combined to generate a new population vector [11].

   In DE literature, a parent vector of current generation is named as target vector. In each generation or iteration a mutant vector or donor vector can be generated,

   p M

   p p

   ( g 1 vg 1, vg 1,, vg 1) , by using ten different mutation

   EM (x) T (k ) H (k , x)

   (6)

   Vi 1,i

   2,i

   D,i

   k 0

   strategies of DE, to change the member of population

   T (k ) is the target magnitude response and

   H (k , x) is

   ( g xg , xg ,, xg ) . Ten different types of mutation

   Xi 1,i

   2,i

   D,i

   calculated magnitude response. Both T (k ) and H (k , x) are

   strategies for DE algorithm are described as:

   g 1 g

   g g

   g 1

   g 1 g

   V1i

   X F( X X )

   r r r

   r r r

   1 2 3

   (11)

   X g 1 Ui

   F (Ui

   Xi )

   (22)

   g 1 g

   g g

   i

   X F ( )

   g g 1 g

   g g 1 g

   V 2i Xb F( Xr Xr )

   (12)

   i Ui Xi

   g 1 g

   1 2

   g g

   g g

   where F ( X ) represents the overall objective function that

   V 3i

   Xi

   • ( Xb Xi ) F( Xr Xr )

     1 2

     1 2

     (13)

     is to be minimized. If the trail vector

     g 1 yields equal or

     Ui

     V 4g 1 X g F( X g X g X g X g ) (14) g

     i b r1 r2

     r3 r4

     smaller value of objective function than target vector Xi

     g 1 g

     g g

     g g

     then it would replace target vector in the next generation

     V 5i Xr F( Xr Xr Xr Xr )

     (15)

     5 1 2 3 4

     otherwise old value of target vector is sustained in the

     V 6g 1 X g F( X g X g )

     (16)

     population. Hence population will never be deteriorated,

     i b

     g 1 g

     b i

     g g g g

     either it will get better or remain equal in the fitness status

     V 7i Xb F( Xb Xi

     • Xr Xr )

       (17)

       g 1 g

       g g

       1 2

       g g

       [9].

       V 8i Xb ( Xb Xi ) F( Xr Xr )

       (18)

       1. Algorithm

          g 1 g

          g g

          1 2

          g g

          The algorithm for DE with binomial crossover has been

          V 9i Xb F( Xb Xi

     • X X )

     r r

     r r

     1 2

     (19)

     shown as under:

     g 1 g

     g g g g

     1. Read values of control parameters of DE: population

        V10i Xi

   • F( X X X X )

   r r r r

   r r r r

   1 2 3 4

   (20)

   size (P), mutation factor (F), crossover rate (Cr),

   where j 1,2,, D; i 1,2,, P . F is the mutation factor, generally lies in the range [0, 2]. It is used to control the amplification of DE algorithm. is the another control parameter apart from F. r1 , r2 , r3 , r4 and r5 P are the

   mutually exclusive integers, different from base index (

   maximum number of iterations and upper and lower limits of population coefficients.

   1. Generate array of uniform random numbers.

   2. Set the generation (Iteration) number and randomly initialize the population of P individuals each of D dimensions.

      i 1,2,, P ) (i.e. r1 r2 r3 r4 r5 i ). P is the set of

      xg xmin rand[0,1](xmax xmin )

      population vector and D shows the search space dimensions.

      j,i j j j

      (23)

      where xmin and xmax

      are the lower and upper bounds

      1. Crossover/Recombination Process j j

         Crossover plays an essential role to increase the potential diversity of population. In this paper binomial (uniform) crossover is employed. An integer is chosen from the interval [1, D], which is a uniformly generated random number between 0 and 1 and less than or equal to the Cr value. It signifies the mutant or donor vector components that will contribute to the target vector in actual. The mutant vector and the target vector subjected to binomial crossover process

         of jth component of ith vector. rand [0, 1] is uniformly distributed random number.

   3. Calculate the objective function and arrange it is ascending order. Then select first P population members out of 2P members.

   4. Set generation (iteration) counter, g=0

   5. Increment generation counter, g=g+1

      Xb

      Xb

   6. Select best member and g corresponding to it.

      and trail vector ( g 1 ug 1, ug 1,,ug 1) is generated as:

   7. Generate an array of uniformly distributed random

      Ui 1,i

      2,i

      D,i

      numbers and generate five different integer numbers

      v g 1 randj,i [0,1] Cr

      j I

      that [1, P] . Then apply mutation operation to

      ug 1 j,i

      or rand

      (21)

      g 1

      j,i

      j,i

      j,1 x g 1 randj,i [0,1] Cr

      j Irand

      compute Vki

      (i 1,2,P; j 1,2,, D;k 1,2,,10) by

      where

      rand

      j,i

      [0,1]

      is uniformly distributed independent

      using ten different mutation strategies as in (Eq. 11) to (Eq. 20). Compute the objective function and check

      fractional value and Irand is a random integer that belongs to

      interval [1,2,, D] which ensures that ug 1 xg 1 . It can

      mutant vector based on minimum objective function.

   8. Generate array of random numbersof size 2P. Apply

      j,1

      j,i

      crossover process to compute ug 1 using (Eq. 21) and

      also be said that ug 1 acquires at least one component from

      j,1

      i

      i

      j,1

      j,i

      j,i

      vg 1 for i to be in range[1,2,, P]. Cr denotes the crossover

      apply selection to compute calculate objective function.

      X g 1 using (Eq. 22). Then

      probability and certainty is in range [0, 1]

      1. Selection

      The final step of evolutionary algorithm is selection which decides whether the target or trail vector survives to the next generation. The trail vector is compared with the target vector of previous generation and the vector which yields lower functional value, than the other one, is allowed to advance the next generation. This can be represented mathematically as in the following equation:

   9. Check whether stopping criteria met?

   10. If not then go to 6.

   11. Write gbest value.

   12. Check whether maximum number of runs has completed or not if not go back to step 2.

   13. Algorithm terminates.

4. SIMULATION RESULTS AND ANALYSIS The cascaded digital FIR filter has been designed by

   evaluating filter coefficients with DE algorithm. The order of digital filter has been taken as 20 and it results in 21 coefficients. In linear phase digital FIR filter coefficients are

   symmetric. So, only half of the coefficients have to be computed in the design problem of digital filter. 200 samples

   have been set with the frequency range 0, . Pass band and

   First of all population size has been varied from 30 to 190 in the steps of 20 at filter order 38 with mutation strategy-9 to observe the values of objective function.

   stop band limit has been taken as

   0.8

   and

   0 0.7 respectively. The DE algorithm has been run for 70 times and 300 iterations have been considered in each run to obtain the optimal results. Initially, population size (P), mutation factor (F) and crossover probability (Cr), has been taken as 90, 0.7 and 0.4 respectively.

   1. Selection of Order

      Order of filter has been varied from 20 to 40 for DE algorithm and ten different mutation strategies have been applied at each filter order. It has been observed from the Table-1 that at each filter order different mutation strategy gives the best value of objective function and at filter order 38 mutation strategy-9 gives the minimum value of objective function.

      Table-1: Objective function variations at different filter orders

      Filter Order	Mutation Strategy	Objective Function
      20	Mutation Strategy 2	5.520916
      22	Mutation Strategy 2	4.429693
      24	Mutation Strategy 2	4.177102
      26	Mutation Strategy 6	3.770070
      28	Mutation Strategy 2	2.669446
      30	Mutation Strategy 4	2.140905
      32	Mutation Strategy 6	2.003540
      34	Mutation Strategy 9	1.826827
      36	Mutation Strategy 2	1.293321
      38	Mutation Strategy 9	1.026339
      40	Mutation Strategy 2	1.089406

      Fig.1 depicts that objective function value continuously goes on decreasing from filter order 20 to filter order 38 for mutation strategy-9. Filter order 38 gives the minimum value of objective function and then it again starts to increase from filter order 38 to filter order 40. So, filter order 38 with mutation strategy-9 has been selected for the design of digital high pass FIR filter.

   2. Analysis of Control Parameters of DE Algorithm

      Control parameters, such as population size (P), mutation factor (F), crossover probability (Cr), of DE algorithm have been varied to further improve the objective function. Convergence speed and global optimum search capability of DE algorithm are very sensitive to the choice of control parameters. Hence the impact of these control parameters has been studied on the performance of DE algorithm.

      Fig.1: Objective function versus filter order

      Fig.2: Population size versus objective function

      Fig.2 indicates that objective function shows linearly decreasing and increasing trend for population size 30 to 110. After this, objective function increases rapidly for population size 110 to 130. Then there is gradual decrease in value of objective function for population size 130 to 170 and again objective function increases rapidly after population size 170. So, population size 110 gives the minimum value of objective function i.e. 1.026311.

      Now, the next parameter that is mutation factor has been varied from 0.55 to 0.95, with mutation strategy-9 at filter order 38 and population size 110, in the steps of 0.05.

      Fig.3 indicates that objective function decreases linearly from 0.55 to 0.6 value of F and then there is linear increase and decrease in objective function for F value 0.6 to 0.65 and

      0.65 to 0.7 respectively. Objective function shows rapidly increasing and then decreasing trend from 0.7 to 0.75 and

      0.75 to 0.8 value of F respectively. After 0.8 objective function starts to increase gradually. So, mutation factor value 0.8 provides the minimum value of objective function.

      Now impact of crossover probability has been studied on the objective function. The effective range of Cr is between 0 to 1. Cr is varied in the steps of 0.1 at filter order 38 with mutation strategy-9, population size 110 and mutation factor 0.8.

      Fig.3: Mutation factor versus objective function

      Fig.4: Crossover probability versus objective function

      It is evident from Fig. 4 that objective function has gradually decreasing trend from 0.1 to 0.4 value of Cr. Objective function increases and then decreases linearly for Cr value 0.4 to 0.5 and 0.5 to 0.6 respectively. Then there are again gradually increasing variations in objective function from Cr value 0.4 to 0.7. So, at Cr value 0.4 minimum value of objective function has been observed

      Hence the detailed analysis of control parameters indicates that DE algorithm with ten different mutation strategies gives the optimum value of objective function with mutation strategy-9 at filter order 30 with the population size 110, mutation factor value 0.8 and crossover probability 0.4, undergoing 300 iterations in each run, for the design of linear phase digital high pass FIR filter.

   3. Magnitude and Phase Response Analysis

   This section presents performance of simulation results in MATLAB. Order of digital high pass filter has been taken as 38 which results in number of coefficients as 39 and these coefficients have been interpolated in MATLAB to obtain the frequency response.

   From Fig. 5 magnitude response has been noticed across the normalized frequency. It analyzes the amplification and attenuation values for different frequency ranges that is pass band and stop band. Behavior of filter is noticed in these frequency bands. Magnitude (in dB) increases with normalized frequency. Maximum stop band attenuation calculated for digital high pass FIR filter is 35.01 dB.

   Fig.5: Magnitude versus normalized frequency

   Fig.6: Magnitude response of digital high pass FIR filter

   Fig. 6 shows that the signals that lie in the frequency range of stop band are attenuated and the signals that lie in the frequency range of pass band are transmitted.

   Fig.7: Phase response versus normalized frequency

   Linear phase characteristics of the digital FIR high pass filter hae been proven in Fig. 7. Digital filter shows the linear phase in the frequency range 0.7 to 1. Robustness of filter has been checked by calculating the standard deviation in Table-2

   The value of standard deviation is very much less than 1 as indicated from Table-2. It shows the robust nature of the digital high pass FIR filter.

   The Comparison of the proposed design algorithm with other design algorithms has been shown in Table-3.

   Table-2: Numerical values of objective function

   Objective Function Value
   Maximum	Minimum	Average	Standard deviation
   1.038091	1.026035	1.029616	0.002813

   Table-3: Comparison of proposed design algorithm with other design algorithms
   Algorithm	Pass Band and Stop Band Performance Analysis
   	Maximum stop band attenuation (dB)	Maximum pass band ripple	Maximum stop band ripple
   PM [12]	-25.09	0.056	0.05557
   RGA [12]	-25.74	0.134	0.04678
   PSO [12]	-29.10	0.130	0.03508
   CRPSO [12]	-31.89	0.153	0.02544
   DE	-35.01	0.026	0.017761

   Table-3: Comparison of proposed design algorithm with other design algorithms
   Algorithm	Pass Band and Stop Band Performance Analysis
   	Maximum stop band attenuation (dB)	Maximum pass band ripple	Maximum stop band ripple
   PM [12]	-25.09	0.056	0.05557
   RGA [12]	-25.74	0.134	0.04678
   PSO [12]	-29.10	0.130	0.03508
   CRPSO [12]	-31.89	0.153	0.02544
   DE	-35.01	0.026	0.017761

   Hence Table-3 indicates that the proposed algorithm gives the better results than other algorithms in terms of maximum stop band attenuation, maximum pass band ripple and maximum stop band ripple.

5. CONCLUSION

DE is very powerful optimization algorithm. It exhibits simplicity, robustness and fast convergence speed using few control parameters. But the right choice of these control parameters is very important because these parameters have great impact on convergence speed and objective function. In this paper linear phase digital FIR high pass filter has been designed using ten different mutation strategies of differential evolution. The designed DE algorithm gives the optimum value of objective function at filter order 38 with mutation strategy-9 and is also comparable to other design algorithms. It is concluded after analyzing the results that design problem of digital FIR high pass filter gives the optimum results at population size 110, mutation factor value 0.8 and crossover probability 0.4. Magnitude and phase response of designed filter are also analyzed and the same technique is also applicable for the design of low pass, band pass and band stop filters.

REFERENCES

1. J. H. McClellan, T. W. Parks, and L. R. Rabiner, A computer program for designing optimum FIR Linear Phase Digital Filters, IEEE Trans. on Audio and Electroacoustics, vol. AU-21, no. 6, pp. 506-526, Dec. 1973.

2. J. H. Holland, Adaptation in natural and artificial systems, Univ. of Michigan Press. Ann Arbor, 1975.

3. D. E. Goldberg, Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, MA, 1975.

4. J. Kennedy and R. Eberhart, Particle swarm optimization, Proc. of IEEE Int. Conf. Neural Network, vol. 3, no. 4, pp. 1942-1948, 1995.

5. J. G. Proakis and D. G. Manolakis, Digital signal processing: principles, algorithms and applications, Prentice Hall, 1996.

6. J. M. Renders and S. P. Flasse, Hybrid methods using genetic algorithms for global optimization, IEEE Trans. Syst., Man and Cybern. Part B, vol. 26, no. 2, pp. 243-258, Apr. 1996.

7. R. Storn and K. Price, Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, vol. 11, no. 4, pp. 341359, 1997.

8. M. Omran, A. Engelbrecht, and A. Salman, Bare bones differential evolution, European Journal of Operational Research, vol. 196, no. 1, pp. 128-139, 2009.

9. S. Das and P. N. Suganthan, Differential evolution: A survey of the state of the art, IEEE Trans. Evol. Comput., vol. 15, no. 1, pp. 4-31, 2011.

10. S. Mondal, D. Chakraborty, R. Kar, D. Mandal, and S. P. Ghosal, Novel particle swarm optimization for high pass FIR filter design, IEEE Symposium on Humanities, Science and Engineering Research, 2012, pp. 413-418.

11. A. Chandra and S. Chattopadhyay, Role of mutation strategies of differential evolution algorithm in designing hardware efficient multiplier less low pass FIR filter, Journal of Multimedia, vol. 7, no. 5, pp. 353-363, 2012.

12. S. Mondal, S. P. Ghosal, R. Kar, and D. Mandal, Design of optimal linear phase FIR filter using craziness based particle swarm optimization technique, Journal of King Saud University- Computer and Information Sciences, vol. 24. 2012, pp. 83-92.

13. B. Singh, J. S. Dhillon, and Y. S. Brar, A hybrid differential evolution method for the design of IIR digital filter, ACEEE Int. Jourmal on Signal & Image Processing, vol. 4, no. 1, pp. 1-10, Jan. 2013.