以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：16 、訪客IP：18.204.2.53

姓名李建民(Chien-Min Lee) 查詢紙本館藏 畢業系所電機工程學系 論文名稱進化演算法之動態分析及應用於數位濾波器之設計

(The Dynamic Analysis of Evolutionary Algorithm and Its Application to the Design of Digital Filters)相關論文檔案[Endnote RIS 格式] [Bibtex 格式] [相關文章] [文章引用] [完整記錄] [館藏目錄] 至系統瀏覽論文 ( 永不開放) 摘要(英)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.關鍵字(中)★ 線性相位

★ 最小相位延遲

★ 數位濾波器

★ 二冪次方和係數

★ 進化演算法

★ 動態分析關鍵字(英)★ minimum-phase

★ linear-phase

★ multiplier-free

★ dynamic analysis

★ digital filters

★ Evolutionary algorithm論文目次Chapter 1 Introduction 1

1.1 Overview of Evolutionary Algorithm 1

1.1.1 Evolution Strategies (ES) 2

1.1.2 Evolutionary Programming (EP) 2

1.1.3 Genetic Algorithm (GA) 3

1.2 The Operators of Evolutionary Algorithm 1

1.2.1 Recombination Operator 2

1.2.2 Mutation Operator 4

1.2.2.1 The typical mutation scheme: 5

1.2.2.2 The violent mutation scheme: 5

1.2.3 Selection Operator 6

1.2.3.1 The Regular Selection 6

1.2.3.2 The Enlarged Selection 7

1.2.3.3 Comparison of and selection 8

1.3 The Survey of the Design of Digital Filters 12

Chapter 2 The Dynamic Analysis of Evolutionary Algorithm 17

2.1 How EA works? 17

2.2 The Dynamic Analysis of the Recombination Operator 21

2.3 The Dynamic Analysis of the Mutation Operator 24

2.3.1 The common type mutation scheme 24

2.3.2 The violent mutation scheme 24

The one-stage mutation scheme 24

The two-stage mutation scheme 28

2.4 Summary 35

Chapter 3 The Digital Filters with Infinitely-Precision Coefficient 36

3.1 The Comparison of Quality with Traditional Techniques 38

3.1.1 The Finite Impulse Response (FIR) Digital Filters 38

3.1.1.A The FIR Digital filters with Minimum-Ripple 38

3.1.1.B The FIR Digital filters with Specified Magnitude Response 45

3.1.2 The Infinite Impulse Response (IIR) Digital Filters 49

3.1.3 Raised-cosine Filters 51

3.1.4 2-D Quadrantal Symmetric Filters 54

3.1.4.A 2-D Rectangular Low-Pass Filter 55

3.1.4.B 2-D Circular/Elliptic Low-Pass Filter 56

3.1.4.C 2-D Circular Band-Pass Filter 57

3.1.4.D 2-D Filter with Minimum-Energy Stop-bands 58

3.1.4.E 2-D Circular Conic Filter 58

3.1.4.F 2-D Fan-Type Filter 59

3.2 The IIR Digital Filter with the Property of the Minimum-phase 60

3.2.1 Problem Formulation 60

3.2.2 Design Examples 61

3.3 The IIR Digital Filter with the Property of the Linear-phase 66

3.3.1 Exist Techniques 66

3.3.2 The Design Procedure 68

3.3.3 Design Examples 69

Example 1 69

Example 2 71

Example 3 72

3.4 Summary 75

Chapter 4 The Digital Filters with Multiplier-Free Coefficient 77

4.1 The Multiplier-Free Coefficient 79

4.2 The Cascade-Form of FIR Digital Filter with SPT-AS Coefficients 81

4.2.1 Problem formulation 81

4.2.2 Comparison with existed techniques 82

4.2.3 FIR filter with magnitude specification 85

4.2.4 Cascade-form of SPT-AS FIR filters 87

4.3 SPT-AS IIR Filter with the Property of Minimum-Phase 94

4.3.1 Problem formulation 94

4.3.2 Design Examples 95

4.4 SPT-AS IIR Filter with the Property of Linear-Phase 113

4.4.1 Existing Techniques 113

4.4.2 Design Procedures 114

4.4.3 Design Examples 116

4.4.3.1 Step1: The Min.-Phase IIR Filter & comparison with past GA design 116

4.4.3.2 Step2: The Linear-phase SPT-AS IIR digital filters 122

4.5 The Two-Channel Filter Banks 132

4.5.1 The QMF Filter Banks 132

4.5.2 Design Examples 134

4.6 Summary 142

Chapter 5 Conclusions 144

Reference 147

Index 154參考文獻[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.指導教授賀嘉律、蕭師基

(Chia-Lu Ho、Sammy Siu)審核日期2005-12-28 推文facebook plurk twitter funp google live udn HD myshare reddit netvibes friend youpush delicious baidu 網路書籤Google bookmarks del.icio.us hemidemi myshare