Supremacy of Differential Evolution Algorithm in Designing Multiplier-Less Low-Pass FIR Filter

Authors: Abhijit Chandra, Sudipta Chattopadhyay

Abstract:

In this communication, we have made an attempt to design multiplier-less low-pass finite impulse response (FIR) filter with the aid of various mutation strategies of Differential Evolution (DE) algorithm. Impulse response coefficient of the designed FIR filter has been represented as sums or differences of powers of two. Performance of the proposed filter has been evaluated in terms of its frequency response and associated hardware cost. Supremacy of our approach has been substantiated by comparing our result with many of the existing multiplier-less filter design algorithms of recent interest. It has also been demonstrated that DE-optimized filter outperforms Genetic Algorithm (GA) based design by a large margin.  Hardware efficiency of our algorithm has further been validated by implementing those filters on a Field Programmable Gate Array (FPGA) chip.

Keywords: Convergence speed, Differential Evolution (DE), error histogram, finite impulse response (FIR) filter, total power of two (TPT), zero-valued filter coefficient (ZFC).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1091376

References:

[1] A. Antoniou, Digital Filters: Analysis, Design and Applications, McGraw Hill, 2001.
[2] N. Benvenuto, M. Marchesi and A. Uncini, "Applications of Simulated Annealing for the Design of Special Digital Filters,” IEEE Trans. Signal Processing, vol. 40, pp. 323-332, 1992.
[3] R. Cemes and D. Ait Boudaoud, "Genetic Approach to Design of Multiplier-less FIR Filters,” Electronics Letters, vol. 29, no. 24, pp. 2090-2091, 1993.
[4] L. Cen and Y. Lian, "Complexity Reduction of High-speed FIR Filters using Micro-Genetic Algorithm,” Proceedings of the First International Symp. on Control, Communications and Signal Processing, pp. 419-422, 2004.
[5] L. Cen, Y. Lian, "A Modified Micro-Genetic Algorithm for the Design of Multiplierless Digital FIR Filters,”Proceedings of IEEE International Conference on Digital Techniques in Electrical Engineering, pp.52-55, 2004.
[6] S. Chattopadhyay, S. K. Sanyal and A. Chandra, "Design of FIR Pulse-Shaping Filter: Superiority of Differential Evolution Optimization over Convex Optimization,” Proceedings of the 5th European Conference on Circuits and Systems for Communications (ECCSC’10), pp.189-192, 2010.
[7] C. Chen and A. N. Willson, "A Trellis Search Algorithm for the Design of FIR Filters with Signed-Powers-of-Two Coefficients,” IEEE Trans. on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 46, no.1, pp.29-39, 1999.
[8] S. Das, A. Abraham and A. Konar, "Particle Swarm Optimization and Differential Evolution Algorithms: Technical Analysis,” Applications and Hybridization Perspectives. Studies in Computational Intelligence (SCI), vol. 116, pp. 1-38, 2008.
[9] S. Das and P. N. Suganthan, "Differential Evolution: A Survey of the State-of-the-art,” IEEE Trans. on Evolutionary Computation, vol. 15, no. 1, pp. 4-31, 2011.
[10] P. Genetili, F. Piazza and A. Uncini, "Efficient Genetic Algorithm Design for Power-of-two FIR Filters,” Proceedings of the International Conference on Acoustics, Speech and Signal Processing, vol. 2, pp. 1268-1271, 1995.
[11] R. Guo, L. S. DeBrunner and K. Johansson, "Truncated MCM using Pattern Modification for FIR Filter Implementation,” Proceedings of the 2010 IEEE International Symp. on Circuits and Systems (ISCAS), pp. 3881-3884, 2010.
[12] O. Gustafsson, "A Difference Based Adder Graph Heuristic for Multiple Constant Multiplication Problems,” Proceedings of the 2007 IEEE International Symp. on Circuits and Systems (ISCAS), pp. 1097-1100, 2007.
[13] R. M. Hewlitt and E. S. Swartzlander, "Canonical Signed Digit Representation for FIR Digital Filters,” Proceedings of the 2000 IEEE Workshop on Signal Processing Systems (Sips 2000), pp. 416-426, 2000.
[14] K. Jheng, S. Jou and A. Wu, "A Design Flow for Multiplierless Linear-Phase FIR Filters: From System Specification to Verilog Code,” Proceedings of the. 2004 IEEE International Symp. on Circuits and Systems, vol. 5, pp. 293-296, 2004.
[15] J. Y. Kaakinen and T. Saramaki, "A Systematic Algorithm for the Design of Multiplierless FIR Filters,” Proceedings of the 2001 IEEE International Symp. on Circuits and Systems, vol. 2, pp. 185-188, 2001.
[16] N. Karaboga and B. Cetinkaya, "Design of Digital FIR Filters using Differential Evolution Algorithm,” Circuits Systems and Signal Processing, vol. 25, no. 5, pp. 649-660, 2006.
[17] N. Karaboga, "Digital Filter Design using Differential Evolution Algorithm,” EURASIP Journal of Applied Signal Processing, vol. 8, pp. 1269-1276, 2005.
[18] D. Li, J. Song and Y. C. Lim, "A Polynomial-Time Algorithm for Designing Digital Filters with Power-of-Two Coefficients,” Proceedings of the IEEE International Symp. on Circuits and Systems, vol. 1, pp. 84-87, 1993.
[19] Y. Lian and L. Cen, "A Genetic Algorithm for the Design of Low Power High-speed FIR Filters,” Proceedings of the Seventh International Symp. on Signal Processing and Its Applications, vol. 1, pp. 181-184, 2003.
[20] Y. C. Lim and S. R. Parker, "FIR Filter Design over a Discrete Powers-of-Two Coefficient Space,” IEEE Trans. on Acoustic, Speech, Signal Processing (ASSP), vol. 31, pp. 583-591, 1983.
[21] Y. C. Lim, "Design of Discrete-Coefficient-Value Linear Phase FIR Filters with Optimum Normalized Peak Ripple Magnitude,” IEEE Trans. on Circuits and Systems, vol. 37, pp. 1480-1486, 1990.
[22] B. Luitel and A. P. Engelbrecht, "Differential Evolution Particle Swarm Optimization for Digital Filter Design,” Proceedings of the IEEE World Congress on Computational Intelligence, pp. 3954-3961, 2008.
[23] S. K. Mitra, Digital Signal Processing: A Computer-based Approach, 2nd Edition, McGraw Hill, 2001.
[24] H. Samueli, "An Improved Search Algorithm for the Design of Multiplier-less FIR Filters with Power-of-Two Coefficients,” IEEE Trans. on Circuits and Systems, vol. 36, pp. 1044-1047, 1989.
[25] B. Somanathan Nair, Digital Signal Processing: Theory, Analysis and Digital Filter Design, Prentice-Hall, 2004.
[26] R. Storn and K. Price: Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces. International Computer Science Institute, Berkeley. TR-95-012 (1995).
[27] R. Storn, "Differential Evolution Design of an IIR Filter,” Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 268-273, 1996.
[28] 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. 341-359, 1997.
[29] R. Storn and K. Price, "Differential Evolution: A Simple Evolution Strategy for Fast Optimization,” Dr. Dobb’s J. Software Tools, vol. 22, no. 4, pp.18–24, 1997.
[30] R. Storn, K. Price and J. Lampinen, "Differential Evolution- A Practical Approach to Global Optimization,” Springer, 2005.
[31] R. Storn, "Designing Nonstandard Filters with Differential Evolution,” IEEE Signal Processing Magazine, vol. 22, no. 1, pp. 103-106, 2005.
[32] L. Tan, Digital Signal Processing: Fundamentals and Applications, 1st Edition, Academic Press, 2008.
[33] C. Yao, "A Study of SPT Term Distribution of CSD Numbers and Its Application for Designing Fixed-point Linear Phase FIR Filters,” Proceedings of the 2001 IEEE International Symp. on Circuits and Systems, vol. 2, pp. 301-304, 2001.