進化演算法之動態分析及應用於數位濾波器之設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：44

、訪客IP：18.218.71.21

姓名

李建民(Chien-Min Lee) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

進化演算法之動態分析及應用於數位濾波器之設計
(The Dynamic Analysis of Evolutionary Algorithm and Its Application to the Design of Digital Filters)

相關論文

★ 以調適性類神經網路系統實現預先失真器補償 RF 功率放大器之非線性效應	★ 進化演算法應用在數位濾波器之最佳化設計
★ WDM同步光纖網路加入/取出多工器效應之評估	★ PN碼對多重路徑的估測
★ 多層感知等化器-使用進化演算法	★ Lp Norm 倒傳遞演算法使用在調適性濾波器
★ 利用進化演算法在多層感知機結構上之判別回授等化器	★ 模糊類神經網路結合進化演算法運用在基頻通道等化器上
★ 使用進化演算法的模糊化類神經網路等化器	★ 新式的電信網路主參考信號源
★ 應用進化演算法於類神經網路之判別回授等化器與探討各參數對performance的影響	★ 進化演算法結合多層感知機架構運用在4-QAM決策迴授等化器上
★ 進化演算法應用在多層感知迴授等化器上之效能分析	★ 複數訊號多層感知決策回授等化器-使用進化演算法
★ 頻移相位同調光纖通信系統的效能分析	★ 多層感知器對輸入與權值誤差的敏感度分析及倒傳遞(BP)演算法與進化策略(ES)演算法的改善

檔案

[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

推文