DOI : 10.17577/IJERTCONV4IS15042
- Open Access
- Total Downloads : 9
- Authors : Sukhdeep Kaur Sohi, Balraj Singh, Darshan Singh
- Paper ID : IJERTCONV4IS15042
- Volume & Issue : ACMEE – 2016 (Volume 4 – Issue 15)
- Published (First Online): 24-04-2018
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
Design of Low-Pass FIR Digital Filter using Soft Computational Techniques: A Comparison
Sukhdeep Kaur Sohi
Giani Zail Singh College of Engineering & Technology, Bathinda
Balraj Singh
Giani Zail Singh College of Engineering & Technology, Bathinda
Darshan Singh
Government Polytechnic College, Bathinda
Abstract This paper compares the performance of Hybrid Differential Evolution (HDE) algorithm with that of Differential Evolution (DE) and Particle Swarm Optimization (PSO) algorithm. Parameter tuning of these three algorithms has been walked around to optimize the results. Results show that HDE
the name recursive filters. Structure of FIR filters is simply composed of adders, multipliers and adders. FIR filters are described by a difference equation as described in Eq. (1) as follows:
N 1
has an upper hand when compared with DE and PSO algorithm.
yn
hk xn k
k 0
(1)
Keywords Exploratory move, mutation strategy, optimization
where y(n) is the output produced by an input x(n).
hk is
-
INTRODUCTION
A device which permits only a particular frequency range
the impulse response and N is the order of filter [2,7]. Desired magnitude response for the ideal filter is given as described in Eq. (2)
to pass while jamming the path of other frequencies is given
H ( ) 1
for i
pass band
(2)
the name filter. Filters are one of the most imperative and
d i
for i
stop band
0
0
dominant tool of DSP. Window method and frequency sampling method are the traditional methods for designing digital filters. But they failed to provide flexibility [1, 2].
Optimization algorithms are used to minimize or maximize a certain work. It is a simple operation for discovering the attractive outputs from a list of possible solutions. These are classified in to direct search, gradient search and nature inspired methods. Nature inspired methods have become a well known name in the field due to their close
where Hd describe the desired magnitude response. Realizing an ideal filter is not possible, there is always a scope of error [8]. Magnitude errors are described as follows in Eq.
-
and Eq. (4) as below:
e1x absolute error L1 -norm of magnitude response
e2 x – squared error L2 norm of magnitude response
e x K H H , x
resemblance with real biological systems. Ant colony search, particle swarm optimization, predator prey optimization,
1 d i i
i0
(3)
genetic algorithm and differential evolution are the few drops
K
of nature inspired techniques [3, 4].
But as every coin has two sides, all the above
e2 (x)
2
2
i0
Hd i
-
H i , x
(4)
mentioned method offered some disadvantages like slow convergence speed, problem of local minima and dependency on initial parameters. So to overcome these disadvantages, hybrid evolution came in to existence. Hybrid means combining the better of two algorithms to sort out an optimization problem [5, 6].
This paper has been divided into V sections. Section II
where H i , x is the magnitude response of designed filter. The ripple magnitudes errors 1x and 2 x of pass- band and stop-band respectively are to be minimized. Ripple
magnitudes errors are described in Eq. (5) and Eq. (6) as follows:
1x maxHi, x minHi, x (5)
focuses on the FIR filter design problem where as Section III describe the algorithm of DE, HDE and PSO algorithm.
and
2 x maxHi, x
(6)
Results are enclosed in Section IV. Finally Section V concludes the final work.
Combining all objectives and stability constraints Minimize K1x e1x
(7)
-
-
-
PROBLEM FORMULATION
Minimize
Minimize
K2 x e2 x K3x e3x
(8)
(9)
FIR filters are digital filters with finite impulse response. Unlike IIR filters they do not have feedback and hence given
Minimize K4 x e4 x
(10)
Minimize K x
4 w K x
(11)
vt xt f
xt xt f
xt
-
xt
(16)
q q q 1
ij ij B Bj ij m r1 , j r2 , j
where
wq indicates the different weights and K(x) stands
MS-4: DE/best/2:
v
x
-
x
-
x
-
x
v
x
-
x
-
x
-
x
for objective function whose value is to be minimized [6].
t t
r1 j
r1 j
ij Bj
-
fm xt
t r2 j
t r3 j
t r4 j
(17)
v
v
x
x
(x
(x
)
)
-
HYBRID DIFFERENTIAL EVOLUTION
MS-5:DE/rand/2:
ALGORITHM
t t
ij r5 j
-
-
fm
t r1 j
t r2 j
t r3 j
t r4 j
(18)
-
x
-
x
-
x
-
x
-
x
-
x
In 1995, Storn and price introduced a new optimization technique named Differential Evolution Algorithm. It came as a blessing for non-linear and non differentiable function. Requirement of few control parameters, a simple technique with high convergence speed added stars to the fame of DE algorithm. [4, 9, 10]
DE algorithm is excellent in investigating the search
B. Crossover
Generation of trail vector by mixing the elements of donor vector with that of target vector is referred as the process of crossover. There are two types of crossover named binomial crossover and exponential crossover. In this paper binomial crossover has been discussed [9, 15]. Binomial crossover can be mathematically illustrated as shown in Eq. (19):
space and tracing the region of global optima but sometimes it
is time-consuming at fine tuning the solution. Some alteration on the basic DE algorithm can enhance its performance. Such as hybridizing DE algorithm with different optimizers such as
uij,G1 vij,G
xij,G
if randb(( j) CR if randb( j) CR
or and
j rnbr(i) j rnbr(i)
(19)
additional local searchers and other population based met heuristics.. This paper DE algorithm has been hybridized with Hooke Jeeves exploratory move and its performance has been compared with traditional DE algorithm. HDE algorithm comprises of same operators as that of DE named mutation,
where i=1,2,..,P and j= 1,2,..,H
randb(j) is the jth evaluation of a uniform random generator with outcome [0,1]. CR is the crossover constant [0,1] which has to be determined by the user, rnbr(i) is a randomly chosen index 1,2,H which ensures that
crossover, and selection and with an addition of exploratory
uij,G1
gets at least one parameter from
vij,G 1 . rnbr(i)
move [11, 12]. Let a function with H real parameters with population size P is to be optimized. The parameter is
ensures that vij,G1 xij,G
described by Eq. (12):
xi,G x1,i,G , x2,i,G,…………….,x
A. Mutation
H ,i,G
(12)
C. Selection
Finally a choice has to be made between the trail vector and the taret vector. The one which yields the lower value of objective function is kept, while the other is throw away [9,
Addition of the weighted difference of two vectors to the
10]. Selection can be mathematically expressed by following
third randomly chosen vector to generate a mutant or donor vector is named as mutation [9, 10]. It is mathematically described in Eq. (13):
Eq.
x uij
ij,G 1 x
ij,G 1 x
ij
if f uij,G 1 f xij,G
otherwise
(20)
1 2 3
1 2 3
vi,G1 xr ,G fm xr ,G xr ,G
(13)
D. Exploratory Move
where
fm is the mutation factor having a value in the range
This step is included to enhance the performance of
of [0,1].
xr ,G , xr ,G and
xr ,G are randomly chosen vectors
traditional DE algorithm. In the exploratory move the current
1 2 3
solution denoting filter coefficients is agitated in positive and
which are different from the
xij, g
known as target vector. DE
negative directions and the best point is witnessed. This move
makes use of different variants which are classified using the following notations named DE | | . describe the method
for selecting a parent chromosome that form the base
is a success if it can yield the lower value of objective function otherwise it is a failure. It can be mathematically illustrated as follows in Eq. (21):
foundation for the mutant vector. points to the number of
xn xo u j for (i=1,2,,P: j=1,2,,H); (21)
difference vectors used to work up the parent chromosome.
recognizes the recombination mechanism for generating offspring population. DE variants could be addressed using a
i i i i
i
i
where u j 1 if
0 if
i j
i j
particular notation. For e.g. DE/best/1/bin, in this particular nomenclature DE stands for Differential Evolution algorithm,
The objective function can be computed as described in
Eq. (22) as follows:
best means the vectors selected for mutation procedure is the best vector of current generation, 1 is the number of solution
xo iui
xi xo iui
; K xo iui K xo
; K xo iui K xo
(22)
pairs selected and bin indicates the binomial crossover [9, 13, 14, 15]. In this paper five mutation strategies of DE has been
n i
i
i i
i i
x
x
i
i
o ;otherwise
explored which are listed below:
ij
r
x
r
ij
r
x
r
-
PSO ALGORITHM
r2
r2
MS-1: DE/rand/1: vt
xt
1
-
-
fm t
-
xt
3
(14)
MS-2: DE/best/1: vt xt
-
f xt
-
-
xt
(15)
In 1995 J. Kennedy and R. Ebherhart introduced a new
ij B j
m r1
r2 , j
nature inspired technique named, Particle Swarm
MS-3: DE/current to best /1:
Optimization (PSO).It is motivated from the behavior of animals such as bird flocking [16]. . PSO algorithm is
4.4611
4.4411
4.4211
4.4011
4.3811
4.3611
4.3411
4.3211
4.3011
4.2811
4.4611
4.4411
4.4211
4.4011
4.3811
4.3611
4.3411
4.3211
4.3011
4.2811
HDE
DE
HDE
DE
Objective Function
Objective Function
initiated with a chosen population of random particles. Swarm is the name given to the population of PSO and each individual of that swarm is referred as particle. Each particle is allocated a random velocity initially. Mathematically the position and velocity matrix can be described by Eq. (23) and Eq. (24) as follows:
1 2 Q
1 2 Q
pi [ pi , pi ,……… ……, pi ]
(23)
vi [vi , vi ,……… ……., vi ]
(24)
i 2 Q
where Q is the dimension and i=[1,2,L] is number
of particles.
pbset is known as the local best and the best value
in the group is termed as gbest . Each particle in the search space alter its position by calculating the distance between the current position and local best and distance between the group best and current position. Amendments in the velocity of
particle according to the following Eq. (25) as follow:
MS-1 MS-2 MS-3 MS-4 MS-5
Mutation Strategy
MS-1 MS-2 MS-3 MS-4 MS-5
Mutation Strategy
Fig.1: Objective Function obtained for different mutation strategies
vt1 wvt
-
C rand() ( pbest
-
-
pt )
for HDE and DE algorithm on Filter Order 22
id id 1
id i
It is evident from the above Fig.1 that minimum value of
pt 1 pt
-
C2 Rand() (gbestid pt )
id
id
-
vt
-
(25)
objective function has been obtained as 4.43333 and 4.292996 for DE and HDE algorithm respectively with MS-2. Now
id id id
where C1 and C2 are acceleration constant and rand() and Rand() are the random numbers whose value lie in the range of 0 to 1.W is weighing function illustrated by Eq. (26)
parameters value of both DE and HDE algorithm has been varied to enhance the value of objective function. Keeping the MS-2 and filter order 22 population has been varied from 80 to 160 in steps of 20 for both HDE and DE algorithm. Results
w w
-
(w
-
w ) It
(26)
have been drawn in Fig.2 and Fig.3 as follows:
max
max
min MAXIt
4.29302
4.293
4.29298
4.29296
4.29294
4.29292
4.2929
4.29288
4.29286
80 100 120 140 160
Population Size
4.29302
4.293
4.29298
4.29296
4.29294
4.29292
4.2929
4.29288
4.29286
80 100 120 140 160
Population Size
where
wmax and
wmin are the maximum and minimum
Objective Function
Objective Function
value of weighing function. It stands for number of iterations and MAXIt point to the maximum number of iterations chosen for an optimization problem [16, 17, 18].
PSO Algorithm:-
-
A random position and velocity is allocated to each particle of the population.
-
Objective Function of each particle of the population is calculated and is designated as K.
-
If K >
pbest than
pbest is set as S.
-
Then
gbest
is computed by choosing the minimum
value of
pbest .
-
Velocity of particles is repaired by using Eq. (25).
-
Check maximum number of runs accomplished or not, if yes continue to step 7 otherwise revisit step 2.
-
Check maximum number of runs carried out or not. If yes terminate the program, otherwise return to step 1.
-
RESULTS
-
DE and HDE algorithm results
A low-pass FIR digital filter has been designed using HDE and traditional DE algorithm. Five mutation strategies described in Eq. (14) to Eq. (18) has been implemented on filter order 22. The performance has been depicted in Fig. 1 as follows:
Fig.2: Objective Function versus Population Size with MS-2 for Filter Order 22 for HDE algorithm
Objective Function
Objective Function
It is evident from the above Fig.2 that minimum value of objective has been obtained with population sixe 140.
4.4335
4.4334
4.4333
4.4332
4.4331
4.433
4.4335
4.4334
4.4333
4.4332
4.4331
4.433
80
100 120 140 160
80
100 120 140 160
Population Size
Population Size
Objective Function
Objective Function
From the above Fig.3 it has been that minimum value of objective function has been obtained with population size 120. Now keeping the size of population as 120 and 140 for DE and HDE respectively, the value of mutation factor has been varied from 0.4 to 1 in steps of 0.2. The results have been shown in Fig.4 and Fig.5 as below:
4.46
4.44
4.42
4.4
4.38
4.36
4.34
4.32
4.3
4.28
4.46
4.44
4.42
4.4
4.38
4.36
4.34
4.32
4.3
4.28
0.4
0.6
0.8
1
0.4
0.6
0.8
1
Mutation Factor Values
Mutation Factor Values
Fig.4: Objective Function Versus Mutation Factor values with Population Size 140 with MS-2 at Filter Order 22 for HDE algorithm
Objective Function
Objective Function
From the above Fig.4 it has been evident that minimum value has been obtained with mutation factor value 0.8.
4.4379
4.4369
4.4359
4.4349
4.4339
4.4329
4.4379
4.4369
4.4359
4.4349
4.4339
4.4329
0.4
0.6
0.8
1
0.4
0.6
0.8
1
Mutation Factor Values
Mutation Factor Values
Fig.5: Objective Function Versus Mutation Factor values with Population Size 120 with MS-2 at Filter Order 22 for DE algorithm
So minimum value of objective function has been obtained with mutation factor value as 0.8. Now the value of crossover constant has been varied for both HDE and DE algorithm. Their performance has been drawn in Fig. 6 and Fig. 7 respectively.
It is evident from Fig.4 and Fig.5 that crossover rate 0.4 and 0.3 yields the best possible value of objective function for both HDE and DE algorithms respectively.
-
PSO algorithm Results
A low-pass FIR digital filter has been also designed using PSO algorithm. Selected order for the design of low-pass FIR filter is 22. Initially the objective function is achieved as 4.835267. To improve the value of objective function parameter tuning has been investigated. Initially the population size has been varied from 80 to 160 in steps of 20. The Fig.8 depicts the performance.
It is evident from the above Fig. 8 that optimum value of objective function has been attained with population size 80. Now keeping the population size as 80 the value of acceleration constant has been varied from 0.4 to 2 in steps of
0.4. The Fig.9 shows the variance in objective function with varied value of acceleration constant.
4.29307
4.29302
4.29297
4.29292
4.29287
4.29282
4.29277
4.29272
4.29307
4.29302
4.29297
4.29292
4.29287
4.29282
4.29277
4.29272
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
Crossover Rate Values
Crossover Rate Values
Objective Function
Objective Function
Objective Function
Objective Function
Fig.6: Objective Function attained for different values of CR with mutation factor as 0.8 with MS-2 at Filter Order 22 for HDE algorithm
4.4332
4.43318
4.43316
4.43314
4.43312
4.4331
4.43308
4.4332
4.43318
4.43316
4.43314
4.43312
4.4331
4.43308
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
Croosover Rate Values
Croosover Rate Values
Objective Function
Objective Function
Fig.7: Objective Function attained for different values of CR with mutation factor as 0.8 with MS-2 at Filter Order 22 for DE algorithm
4.9788011
4.9288011
4.8788011
4.8288011
4.7788011
4.7288011
80 100 120 140 160
Population Size
4.9788011
4.9288011
4.8788011
4.8288011
4.7788011
4.7288011
80 100 120 140 160
Population Size
Fig.8: Objective Function versus Population Size for Filter Order 22 for PSO algorithm
-
Comparison between PSO, DE and HDE algorithm
A low-pass FIR digital filter has been designed using two nature inspired optimization techniques named DE and HDE algorithms. Table I draws a comparison between the parameter values of DE and HDE algorithm.
4.83
Objective Function
Objective Function
4.82
4.81
20
0
-20
4.8
4.79
4.78
4.77
0.4 0.8 1.2 1.6 2
Acceleration Constants (C1,C2)
-40
Magnitude (dB)
Magnitude (dB)
-60
-80
-100
-120
-140
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Normalized Frequency ( rad/sample)
Fig.10: Magnitude Response for Low-Pass FIR digital Filter with MS-2 at Filter Order 22
Fig.9: Objective Function versus Acceleration Constants with Population Size 80 for Filter Order 22 with PSO algorithm
Parameters
PSO
DE
HDE
Filter Order
22
22
22
Mutation Strategy
–
DE/best/1
DE/best/1
Population Size
80
120
140
Mutation Factor
–
0.8
0.8
Crossover Rate
–
0.3
0.43
Acceleration Constants
2.0,2.0
–
–
Parameters
PSO
DE
HDE
Filter Order
22
22
22
Mutation Strategy
–
DE/best/1
DE/best/1
Population Size
80
120
140
Mutation Factor
–
0.8
0.8
Crossover Rate
–
0.3
0.43
Acceleration Constants
2.0,2.0
–
–
Table-1: Parameters Value compared for PSO, DE and DE Algorithm
0
-100
-200
Phase (degrees)
Phase (degrees)
-300
-400
-500
-600
The following tables compare PSO, DE and HDE algorithms performance.
Table-2: Design Values For PSO, DE and HDE Algorithm
Parameters
PSO
DE
HDE
Magnitude Error-1
2.266943
2.0007
2.0066
Magnitude Error-2
0.284138
0.2554
0.2395
Pass-Band Performance
.9014
H
.8926
H
.8846
H
1.0208
1.0262
1.0285
Stop-Band Performance
H
.0765
H
0.0864
H
0.0583
To check the robustness of both algorithms standard deviation has been calculated and resuls have been depicted in Table-3 as follows:
Objective Function Value
PSO
DE
HDE
Maximum Value
4.7946
4.4332
4.2943
Minimum Value
4.7890
4.3308
4.2927
Average Value
4.7893
4.3314
4.2943
Standard Deviation
0.0006
0.5574
0.00024
Objective Function Value
PSO
DE
HDE
Maximum Value
4.7946
4.4332
4.2943
Minimum Value
4.7890
4.3308
4.2927
Average Value
4.7893
4.3314
4.2943
Standard Deviation
0.0006
0.5574
0.00024
Table-3: Maximum, Minimum and Average Value of Objective Function along with standard deviation
-700
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Normalized Frequency ( rad/sample)
Fig.11: Phase Response for Low-Pass FIR digital Filter with MS-2 at Filter Order 22
-
-
CONCLUSION
DE algorithm is an evolutionary algorithm with few control parameters, simple implementation and fast convergence speed. This paper compared traditional DE with hybrid differential algorithm and particle swarm optimization techniques for designing a low-pass FIR digital filter. Parameter tuning of all three algorithms has been investigated to improve the minimum value of objective function. Results depicted that HDE has a slight upper hand when compared to DE algorithm and PSO algorithm. Standard deviation of objective function for all three algorithms is less than 1 which shows the robustness of designed filter using HDE and DE and PSO algorithm.
From the results depicted in Table-3 it has been evident that HDE performs better than DE and PSO algorithm. Magnitude and Phase response of HDE algorithm has been plotted using MATLAB as follows in Fig.10 and Fig.11 respectively:
REFERENCES
-
E.C Ifeacher and B.W Jervis, Digital Signal Processing: A Practical Approach, Prentice Hall, South Asia, Second Edition, 2002.
-
John G. Proakis and Dimitris G. Manolakis, Digital Signal Processing, Pearson Prentice Hall, Fourth Edition, 2007.
-
Kalyanmoy Deb, Optimization for engineering Design, PHI Learning Pvt. Ltd. New Delhi, First Edition, 2004.
-
Balraj Singh, J.S. Dhillon and Y.S. Brar, A Hybrid Differential Evolution Method for the Design of Digital FIR Filter, International Journal on Signal and Image Processing, vol. 1, no. 1, pp: 1-10, 2013.
-
Bipuel Luitel and Ganesh K. Venayagamoorthy, Differential Evolution, Particle Swarm Optimization for Digital Filter Design, IEEE world congress on computational intelligence, Honkong, pp: 3954- 3961, 1-6 June 2008.
-
Ranjit Kaur and Manjit Singh Patterh and J.S. Dhillon, Digital IIR Filter Design using Real Coded Genetic Algorithm, International Journal Information Technology and Computer Science, vol. 5, no. 7, pp: 27-35, 2013.
-
S. Chattopadhyay, S.K. Sanyal and A. Chandra, Design of FIR Filter Using Differential Evolution Optimization & to Study its Effect as a Pulse-Shaping Filter in a QPSK Modulated System, vol. 10, no. 1, pp: 313-322, 2010.
-
S.M. Shamsul alam and Md. Tariq Hasan, Performance Analysis of FIR Filter Design by using Optimal, Blackman Window and Frequency Sampling Method, International Journal of Electrical and Computer Science (IJECS), vol. 10, pp: 9-14, February 2010.
-
Rainer Storn and Kenneth Price, Differential Evolution- A simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, vol. 11, no. 4, pp: 341-359, 1997.
-
Swagatam Das and Ponnuthuari Nagaratnam Suganthan, Differential Evolution: A Survey of the State of the Art, IEEE Transactions on Evolutionary Computation, vol. 15, no.1, pp: 1-28, February 2011
-
Chumeri Zhang, Jie Chen and Bin Xin, Distributed mesmetic differential evolution with the synergy of Lamarckian and Baldwinian learning, Applied Soft Computing, vol. 13, pp: 2947-2959.
-
Rajni and Balraj Singh, A Hybrid Differential Evolution Method for the Design of High Pass Digital FIR Filter International Journal of Computer Science and Mobile Computing, vol. 4, no. 7, pp: 438-445, 2015.
-
D.P Kothari, J.S. Dhillon, Power System Optimization, PHI learning Pvt. Ltd New Delhi, second edition.
-
Efren Mezura-Montes, Jesus Velazquez-Reyes and Carlos A. Coello Coello, Modified Differential Evolution for Constrained Optmization, IEEE Congress on Evolutionary Computation, Canada.
-
Abhijit Chandra and Sudipta Chattopadhay, Role of Mutation Strategies of Differential Evolution Algorithm in designing Hardware Efficient Multiplier-less LowPass FIR Filter, Journal of multimedia, vol. 7, no. 5, pp: 353-363, October 2012
-
Meisam Najjarzadeh and Ahmad Ayatoolahi, FIR Digital Filter Design, PSO: Utilizing LMS and Minimax Strategies, IEEE Symposium on Signal Processing and Information Technology, pp: 129-132, 2008.
-
Ranjit Kaur and Damanpreet Singh, Particle Swarm Optimization Algorithm for Designing Optimal IIR Digital Filter, International journal of emerging technologies in computational and applied sciences (IJETCAS), vol. 2, no. 7, pp: 225-230, 2014
-
Sangeeta Mandal, Prabisha Mallick, Durbadal Manda, Rajib Kaur, Sabti Prasad Ghoshal, Optimal FIR Band-Pass Filter design using Novel PSO Algorithm, IEEE Symposium on humanities, Science and Engineering Research, 2012.