Title page for 90541015


[Back to Results | New Search]

Student Number 90541015
Author Chien-Min Lee(李建民)
Author's Email Address s0541015@cc.ncu.edu.tw
Statistics This thesis had been viewed 1616 times. Download 0 times.
Department Electrical Engineering
Year 2005
Semester 1
Degree Ph.D.
Type of Document Doctoral Dissertation
Language English
Title The Dynamic Analysis of Evolutionary Algorithm and Its Application to the Design of Digital Filters
Date of Defense 2005-12-22
Page Count 155
Keyword
  • minimum-phase
  • linear-phase
  • multiplier-free
  • dynamic analysis
  • digital filters
  • Evolutionary algorithm
  • Abstract The Evolutionary algorithm is a self-adaptive searching strategy, applicable stochastic search and optimization technique based on the evolutionary theory. The algorithm maintains a population of individual solutions, each of which has a fitness value representing the quality of the solution. It adopts the operators of iterative recombination, mutation, evaluation and selection to extend the search into an undiscovered area of the search space. We investigate the phenomena of dynamics of the genetic operators and provide the contributions to the designing of the digital filters.
    The digital filters may be implemented via two structures: finite-impulse response (FIR) and infinite-impulse response (IIR). Typical design methods have been described in the documents of digital signal processing. And the digital filters with multiplier-free coefficients are also investigated in many studies, which have the benefit of implementation. In this work we provide several new methods to improve the quality of existing FIR/IIR designs. Moreover, the phase of the IIR digital filter will be studied and the related drawback will be improved. The contributions of this study are listed as follows:
    1.The IIR digital filters with the property of minimum-phase.
    2.The minimum-phase IIR digital filters with the property of linear-phase.
    3.The cascade-form of multiplier-free FIR digital filters with allocation scheme.
    4.The IIR digital filters with the multiplier-free coefficients and minimum-phase property.
    5.The IIR digital filters with the multiplier-free coefficients and linear-phase property.
    The proposed linear-phase IIR filters not only improve the nonlinearity of the phase response but provide lower group delay than existing techniques. Moreover, we limit the coefficients by discrete valued (signed sum of power-of-two, SPT) to improve the implementation values. The proposed design is efficient and the related research is rare. The most similar technique first designs the infinite-precision linear-phase IIR filter and then optimizes the finite-precision linear-phase IIR filter by quantizing the coefficients by the sums of signed powers-of-two (SPT) term. This method may bring some problems. The stability, linearity of phase and the amplitude response of the IIR filter will lose control when the coefficients have been quantized. Moreover, it is difficult to look for the appropriate SPT terms to simultaneously hold the requirements of the filter. Because of the property of multi-objects, this design is difficult to achieve by conventional techniques. The proposed EA can efficiently achieve the requirements.
    Table of Content Chapter 1 Introduction1
    1.1Overview of Evolutionary Algorithm1
    1.1.1Evolution Strategies (ES)2
    1.1.2Evolutionary Programming (EP)2
    1.1.3Genetic Algorithm (GA)3
    1.2The Operators of Evolutionary Algorithm1
    1.2.1Recombination Operator2
    1.2.2Mutation Operator4
    1.2.2.1The typical mutation scheme:5
    1.2.2.2The violent mutation scheme:5
    1.2.3Selection Operator6
    1.2.3.1The Regular Selection6
    1.2.3.2The Enlarged Selection7
    1.2.3.3Comparison of  and  selection8
    1.3The Survey of the Design of Digital Filters12
    Chapter 2 The Dynamic Analysis of Evolutionary Algorithm17
    2.1How EA works?17
    2.2The Dynamic Analysis of the Recombination Operator21
    2.3The Dynamic Analysis of the Mutation Operator24
    2.3.1The common type mutation scheme24
    2.3.2The violent mutation scheme24
    The one-stage mutation scheme24
    The two-stage mutation scheme28
    2.4Summary35
    Chapter 3 The Digital Filters with Infinitely-Precision Coefficient36
    3.1The Comparison of Quality with Traditional Techniques38
    3.1.1The Finite Impulse Response (FIR) Digital Filters38
    3.1.1.AThe FIR Digital filters with Minimum-Ripple38
    3.1.1.BThe FIR Digital filters with Specified Magnitude Response45
    3.1.2The Infinite Impulse Response (IIR) Digital Filters49
    3.1.3Raised-cosine Filters51
    3.1.42-D Quadrantal Symmetric Filters54
    3.1.4.A2-D Rectangular Low-Pass Filter55
    3.1.4.B2-D Circular/Elliptic Low-Pass Filter56
    3.1.4.C2-D Circular Band-Pass Filter57
    3.1.4.D2-D Filter with Minimum-Energy Stop-bands58
    3.1.4.E2-D Circular Conic Filter58
    3.1.4.F2-D Fan-Type Filter59
    3.2The IIR Digital Filter with the Property of the Minimum-phase60
    3.2.1Problem Formulation60
    3.2.2Design Examples61
    3.3The IIR Digital Filter with the Property of the Linear-phase66
    3.3.1Exist Techniques66
    3.3.2The Design Procedure68
    3.3.3Design Examples69
    Example 169
    Example 271
    Example 372
    3.4Summary75
    Chapter 4 The Digital Filters with Multiplier-Free Coefficient77
    4.1The Multiplier-Free Coefficient79
    4.2The Cascade-Form of FIR Digital Filter with SPT-AS Coefficients81
    4.2.1Problem formulation81
    4.2.2Comparison with existed techniques82
    4.2.3FIR filter with magnitude specification85
    4.2.4Cascade-form of SPT-AS FIR filters87
    4.3SPT-AS IIR Filter with the Property of Minimum-Phase94
    4.3.1Problem formulation94
    4.3.2Design Examples95
    4.4SPT-AS IIR Filter with the Property of Linear-Phase113
    4.4.1Existing Techniques113
    4.4.2Design Procedures114
    4.4.3Design Examples116
    4.4.3.1Step1: The Min.-Phase IIR Filter & comparison with past GA design116
    4.4.3.2Step2: The Linear-phase SPT-AS IIR digital filters122
    4.5The Two-Channel Filter Banks132
    4.5.1The QMF Filter Banks132
    4.5.2Design Examples134
    4.6Summary142
    Chapter 5 Conclusions144
    Reference147
    Index154
    Reference [1]Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs, Berlin, New York, Springer-Verlag, 1992.
    [2]Thomas Bäck, Evolutionary Algorithms in Theory and Practice, New York: Oxford university press, 1996.
    [3]Mitsuo Gen, and Runwei Cheng, Genetic algorithms and engineering design, New York: Wiley, 1997.
    [4]James Edward Smith, “Self adaptation in evolutionary algorithms,” Ph.D. dissertation, Dept. of Computer Studies and Mathematics, University of the West of England, Bristol, July 1998.
    [5]H.-G. Beyer, The Theory of Evolution Strategies, Berlin, Germany: Springer-Verlag, 2001.
    [6]Xiaofeng Qi, and F. Palmieri, “Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space. Part I: Basic properties of selection and mutation,“ Neural Networks, IEEE Transactions on, vol. 5, issue 1, pp. 102-119, Jan. 1994.
    [7]Xiaofeng Qi, and F. Palmieri, “Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space. Part II: Analysis of the diversification role of crossover,“ Neural Networks, IEEE Transactions on, vol. 5, issue 1, pp. 120-129, Jan. 1994.
    [8]Thomas Bäck, “Generalized Convergence Models for Tournament- and -Selection,” Proceedings of the 6th International Conference on Genetic Algorithms, pp. 2-8, 1995.
    [9]Adam Prügel-Bennett, ”Modeling Evolving Populations,” Journal of Theoretical Biology, pp. 81-95, 1997.
    [10]P. Power; F. Sweeney; C.F.N. Cowan, “EA crossover schemes for a MLP channel equalizer, ” Electronics, Circuits and Systems, Proceedings of ICECS '99, the 6th IEEE International Conference on, vol. 1, Sept. 1999, pp. 407-410.
    [11]H.-G. Beyer, “On the Dynamics of EAs without Selection,” Foundations of Genetic Algorithms, 1999, pp. 5-26.
    [12]A. Rogers, and A. Prugel-Bennett, “Genetic drift in genetic algorithm selection schemes,” IEEE Trans on Evolutionary computation, vol. 3, no. 4, pp. 298-303, Nov. 1999
    [13]H.-G. Beyer, and K. Deb, ”On Self-Adaptive Feature in Real- Parameter Evolutionary Algorithms ”, IEEE Trans. Evolutionary computation, vol.5, no. 3, pp. 250-270, June 2001.
    [14]H.-G. Beyer, ”On the Performance of -Evolution Strategies for the Ridge Function Class,” IEEE Transactions on Evolutionary Computation, vol. 5, no 3, pp.218-235, 2001.
    [15]H.-G. Beyer, and K. Deb, ”On Self-Adaptive Features in Real-Parameter Evolutionary Algorithms,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 3, pp. 250-270, 2001.
    [16]D. V. Arnold, and H.-G. Beyer, ”Local Performance of the (1+1)-ES in a Noisy Environment,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 30-41, 2002.
    [17]Ronald E. Crochiere, and Lawrence R. Rabiner, Multirate Digital Signal Processing, Prentice-Hall, 1983
    [18]John G. Proakis, Digital communications, New York: McGraw-Hill, 1989.
    [19]Wu-Sheng Lu and Andreas Antoniou, Two-Dimensional Digital Filters, Marcel dekker 1992.
    [20]Emmanuel C. Ifeachor, and Barrie W. Jervis, Digital signal processing: A practical approach, Addison-Wesley. 1993.
    [21]P. P. Vaidyanathan, Multirate Systems and Filter Banks, Prentice-Hall, 1993.
    [22]N. J. Fliege, Multirate Digital Signal Processing, John Wiley, 1994.
    [23]Sophocles J. Orfanidis, Introduction to signal processing, Prentice Hall, 1996.
    [24]Boaz Porat, A course in digital signal processing, Wiley, 1997.
    [25]V. K. Ingle, and J. G. Proakis, Digital Signal Processing-Using MATLAB V.4, PWS Publishing, 1997.
    [26]Paul A. Lynn, and Wolfgang Fuerst, Introduction to signal processing: with computer applications, Wiley, 1998.
    [27]Frederic J. Harris, Multirate signal processing for communication systems, Upper Saddle River, N.J. : Prentice Hall PTR, 2004.
    [28]J.-R.Ohm, Multimedia communication technology: representation, transmission, and identification of multimedia signals, Berlin; New York: Springer, 2004.
    [29]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, Feb. 1992.
    [30]Kit-sang Tang, Kim-fung Man, and Sam Kwong, “Design and Optimization of IIR Filter Structure Using Hierarchical Genetic Algorithms,” IEEE Trans. Industrial electronics, vol. 45, no. 3, pp. 481-487, June 1998.
    [31]Jui-Chung Hung, and Bor-Sen Chen, “Genetic Algorithm Approach to Fixed-Order Mixed  Optimal Deconvolution Filter Designs,” IEEE Trans on signal processing, vol. 48, no. 12, Dec. 2000.
    [32]Chien-Min Lee, and Chia-Lu Ho, "Optimal digital filters by evolutionary search approach," 2003 Conference on electronic communication and applications, pp.151-156, Penghu, Taiwan, May 2003.
    [33]M. Donadio, “Lost Knowledge Refound: Sharpened FIR Filters,” Signal Processing Magazine, IEEE, vol. 20, issue 5, pp. 61-63, Sep. 2003.
    [34]Chien-Min Lee, and Chia-Lu Ho, "Design the Discrete valued IIR filters with Minimum Phase by using Evolutionary Algorithm," The Ninth Conference on Artificial Intelligence and Applications, Taiwan, Nov. 2004.
    [35]Soo-Chang Pei, and Jong-Jy Shyu, “2-D FIR Eigenfilters: A Least-Squares Approach,” IEEE Trans. Circuit and systems, vol.37, no.1, Jan. 1990.
    [36]D. B. H. Tay, and N. G. Kingsbury, “Flexible design of multidimensional perfect reconstruction FIR 2-band filters using transformations of variables,” Image Processing, IEEE Transactions on, vol. 2, issue 4, pp. 466-480, Oct. 1993.
    [37]A. G. Deczky, “Synthesis of recursive digital filters using the minimum p-error criterion,” IEEE Trans. Audio and Electroacoustic, vol. AU-20, pp. 257-263, Oct. 1972.
    [38]J. L. Sullivan, and J.W. Adams, “PCLS IIR digital filters with simultaneous frequency response magnitude and group delay specifications,” Signal Processing, IEEE Transactions on. vol. 46, no. 11, pp. 2853-2861, Nov. 1998.
    [39]Luowen Li, Lihua Xie, Wei-Yong Yan, and Yeng-Chai Soh, “Design of low-order linear-phase IIR filters via orthogonal projection,” Signal Processing, IEEE Transactions on, vol. 47, no. 2, pp. 448-457, Feb. 1999.
    [40]R.W. Aldhaheri, “Design of linear-phase IIR digital filters using singular perturbational model reduction”, Vision, Image and Signal Processing, IEE Proceedings- , vol. 147, issue: 5, pp.409-414, Oct. 2000.
    [41]M. Abo-Zahhad, and S.M. Ahmed, “Design of IIR filters with simultaneous amplitude and group-delay characteristics using genetic algorithm,” Proceedings of the 2003 10th IEEE International Conference on Electronics, Circuits and Systems, ICECS 2003, vol.3, Dec.2003, pp.1148-1151.
    [42]A. Kurosu, S. Miyase, S. Tomiyama, and T. Takebe, “A Technique to Truncate IIR Filter Impulse Response and Its Application to Real-Time Implementation of Linear-Phase IIR Filters,” IEEE Trans on Signal Processing, vol. 51, no. 5, pp.1284-1292, May 2003.
    [43]Lee Chien-Min, and Ho Chia-Lu, "Design the IIR Filter with phase and magnitude specifications ," 2004 Conference on electronic communication and applications, Taiwan, May 2004.
    [44]Chien-Min Lee, and Chia-Lu Ho, "Designing the IIR Digital Filter with Phase and Magnitude Specifications by EA," International Journal of Electrical Engineering, vol.12, no.2, pp. 207-214, Aug, 2005.
    [45]Y. C. Lim, and S. R. Parker, “FIR filter design over a discrete power-of two coefficient space,” IEEE Trans. Acoust. Speech, signal Processing, vol. ASSP-31, pp. 583-591, June 1983.
    [46]Yong Lim, and S. Parker, ”Discrete coefficient FIR digital filter design based upon LMS criteria,” IEEE Trans. Circuit Syst., vol. CAS-30, pp. 723-739, Oct. 1983.
    [47]K. Nakayama, “A discrete optimization method for higher-order FIR filters with finite wordlength coefficients,” IEEE Trans. Acoust. Speech, Signal Processing, vol. ASSP-35, pp. 1215–1217, Aug. 1987.
    [48]B. Jaumard, M. Minoux, and P. Siohan, “Finite precision design of FIR digital filters using a convexity property,” IEEE Trans. Acoust. Speech, signal Processing, vol. 36, pp. 407-411, Mar. 1988.
    [49]Q. Zhao, and Y. Tadokoro, “A simple design of FIR filters with power of-two coefficients,” IEEE Trans. Circuits Syst., vol. 35, pp. 566–570, May 1988.
    [50]Y. C. Lim, and B. Liu, “Design of cascade form FIR filters with discrete value coefficients,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 36, pp. 1735-1739, Nov. 1988.
    [51]H. Samueli, “An improved search algorithm for the design of multiplierless FIR filters with power-of-two coefficients,” IEEE Trans. Circuits Syst., vol. 36, pp. 1044–1047, July 1989.
    [52]Y. C. Lim, “Design of discrete-coefficient-calue linear phase FIR filters with optimum normalized peak ripple magnitude,” IEEE Circuits Syst., vol. 37, pp. 1480-1486, Dec. 1990.
    [53]R. Cemes, and D. Ait-Boudaoud, “Genetic approach to design of multiplierless FIR filters,” IEE Electronics Letters, vol. 29, Issue: 24, Nov. 1993.
    [54]P. Gentili, F. Biazza, and A. Uncini, “Evolutionary design of FIR digital filters with power-of-two coefficients, “ Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, 27-29, vol.1, June 1994, pp. 110-114.
    [55]S. S. Rao, and A. Ramasubrahmanyan, “Design of discrete coefficient FIR filters by simulated evolution,” IEEE Signal Processing Letters. vol. 3, no. 5, pp. 137-140, May 1996.
    [56]Hyuk Jun Oh, Woo Jin Oh, Yong Hoon Lee, “Design of cascade-form IIR filters with powers-of-two coefficients using mixed integer linear programming”, ISCAS '96 , vol. 2, May 1996, pp. 221-224.
    [57]Chao-Liang Chen, and A. N. Willson Jr., “A Trellis Search Algorithm for the Design of FIR Filters with Signed-Powers-of-Two Coefficients,” IEEE Trans on Circuits and Systems II, vol. 46, no. 1, pp. 29-37, Jan. 1999.
    [58]Yong Ching Lim, Rui Yang, Dongning Li, and Jianjian Song, “Signed Power-of-Two Term Allocation Scheme for the Design of Digital Filters,” IEEE Trans. Circuit and system II, vol. 46, no. 5, pp. 577-584, May 1999.
    [59]H.H. Dam, S. Nordebo, K.L. Teo, and A. Cantoni, “FIR filter design over discrete coefficients and least square error,” Vision, Image and Signal Processing, IEE Proceedings-, vol. 147, issue 6, pp.543-548, Dec. 2000.
    [60]R. Thamvichai, T. Bose, and R. L. Haupt, “Design of 2-D multiplierless IIR filters using the genetic algorithm,” IEEE Trans on circuits and systems I, vol. 49, no. 6, June 2002.
    [61]R. Thamvichai, T. Bose, and R. L. Haupt,” Design of 2-D multiplierless IIR filters using the genetic algorithm”, Circuits and Systems I, IEEE Trans. on, Vol. 49, issue: 6, pp. 878–882, June 2002
    [62]Yong Ching Lim, Y. Sun, and Yu Ya Jun, “Design of Discrete-Coefficient FIR Filters on Loosely Connected Parallel Machines”, IEEE Trans on signal processing, vol. 50, no. 6, June 2002.
    [63]Dongning Li, Yong Ching Lim, Yong Lian, and Jianjian Song, “A Polynomial- Time Algorithm for Designing FIR Filters With Power-of-Two Coefficients,” IEEE Trans. Signal Processing, Vol. 50, No.8, pp. 1935-1941, August 2002.
    [64]S. C. Chan, and P. M. Yiu, “An Efficient Multiplierless Approximation of the Fast Fourier Transform Using Sum-of-Powers-of-Two (SOPOT) Coefficients,” IEEE Signal Processing Letters, vol. 9, no. 10, Oct. 2002.
    [65]Liang Li; M. Ahmadi, M. Sid-Ahmed, and K. Wallus, “Design of canonical signed digit IIR filters using genetic algorithm”, The Thirty-Seventh Asilomar Conference on Signals, Systems & Computers, vol. 2, Nov. 2003, pp.2043-2047.
    [66]Chien-Min Lee, and Chia-Lu Ho, "Design of Cascade Form FIR Filters with SPT-AS coefficients by Group search approach," International Journal of Electrical Engineering, vol.13, no.3, pp. 305-312, May 2005.
    [67]J. Yli-Kaakinen, T. Saramaki, “An Algorithm for the Design of Multiplierless Approximately Linear-Phase Lattice Wave Digital Filters,” IEEE Proc. ISCAS2000, May, 2000, pp. 77-80.
    [68]J. D. Johnston, “A filter family designed for use in quadrature mirror filter banks,” IEEE In Proc. Of Int’l Conf. on ASSP, 1980, pp. 291-294.
    [69]P. P. Vaidyanathan, and P.-Q. Hoang, “Lattice structures for optimal design and robust implementation of two-channel perfect-reconstruction QMF banks,” IEEE Acoustics, Speech, and Signal Processing, vol. 36, no. 1, pp. 81-94, Jan. 1988.
    [70]B.-R.Horng, and A.N. Willson Jr., “Lagrange multiplier approaches to the design of two-channel perfect-reconstruction linear-phase FIR filter banks,” Signal Processing, IEEE Transactions on, vol. 40, issue 2, pp. 364-374, Feb. 1992.
    [71]S. Sriranganathan, D. R. Bull, and D. W. Redmill, “The design of Low Complexity Two-Channel Lattice-Structure Perfect-Reconstruction Filter Banks Using Genetic Algorithm”. Proc. ISCAS97, vol.4, pp.2393-2396.
    [72]Yuan-Pei Lin, P. P. Vaidyanathan, “A Kaiser window approach for the design of prototype filters of cosine modulated filter banks,” Signal Processing Letters, IEEE, vol. 5, no. 6, pp.132-134, June 1998.
    [73]Chee-Kiang Goh, and Yang Ching Lim, ”An Efficient Algorithm to Design Weighted Minmax Perfect Reconstruction Quadrature Mirror Filter Banks”, IEEE Trans. Signal Processing, vol. 47, no.12, Dec. 1999.
    [74]Yong Ching Lim, and Ya Jun Yu, “A width-recursive depth-first tree search approach for the design of discrete coefficient perfect reconstruction lattice filter bank,” Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on, vol. 50, no. 6, pp. 257-266, June 2003.
    [75]Chien-Min Lee, and Chia-Lu Ho, "Design the QMF bank with discrete valued coefficients," 2004 Workshop on consumer Electronics and Signal Processing, Taiwan, Nov. 2004.
    [76]Iowegian International Corporation (dspGuru), Digital Signal Processing Central, http://www.dspguru.com/index.htm, 2004.
    [77]Julius O. Smith III, Introduction to Digital Filters: with Audio Applications, http://ccrma-www.stanford.edu/~jos/filters/, May 2004.
    [78]W. E. Higgins, and D. C. Munson, “Infinite impulse response digital filter design,” Handbook for Digital Signal Processing, S. K. Mitra and J. F. Kaiser, Eds. New York: Wiley, 1993, ch. 5.
    [79]A. V. Oppenheim, and R. W. Schafer, Discrete-Time Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1989.
    [80]L. Fogel, A. Owens, and M. Walsh, Artificial intelligence through simulated evolution, John Wiley, 1966.
    [81]H.-P. Schwefel, Numerical optimization of computer models. John Wiley and Sons, 1981.
    Advisor
  • Sammy Siu(蕭師基)
  • Chia-Lu Ho(賀嘉律)
  • Files
  • 90541015.pdf
  • disapprove authorization
    Date of Submission 2005-12-28

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.