臺灣博碩士論文加值系統

最少均方演算法（Least Mean Square algorithm, LMS）由於具有簡單的運算結構與數值計算穩定的特質，使得它在近年來廣泛地被應用在各種含有可調適數位濾波器的場合。然而，以聲學迴音消除的應用為例，其輸入信號為具有高關聯度的語音信號，此導致可調適濾波器收斂緩慢而不符規格需求；因此，本文針對上述的問題進行研究，探討六種提升LMS演算法收斂速度的改善技巧。同時，為了提升收斂速度而導致計算量增加的問題，亦訂為研究工作的重點方向，總共探討了三種精簡計算量的架構。另外，在決定演算法的相關參數方面，如LMS演算法中的調整步階，則引入粒子群優（Particle Swarm Optimization, PSO）的最佳化技術，建構一具可變調整步階（variable step size）的LMS演算法。上述的研究工作除了基本的理論探討外，也包含相關應用例的電腦模擬結果來證實這些技巧的可用性。

The least mean square (LMS) algorithm has been received much attention in recent years due to its attractive properties of the simple configuration and numerical stability. However, the adaptive finite impulse response (FIR) filter using the LMS algorithm has a slow convergence rate when high correlative signals are utilized for training, for example, on the application of the acoustic echo cancellation. Accordingly, this work explores the enhancing schemes or modified version of the LMS algorithm with respect to the convergence rate and computational complexity. Total six schemes are proposed to speed up the convergence rate of the adaptive filter using the LMS algorithm. In the meanwhile, based on the viewpoint of reducing the computational complexity of the LMS algorithm, additional three schemes are studied and provided to achieve the goal. Furthermore, this work also investigates the schemes of evolutionary optimization at the attempt of dynamically adjusting the parameters of the LMS algorithm such as the step size, where the genetic algorithm and particle swarm optimization are involved. All the proposed schemes are discussed in the related sections and go along with computer simulation to validate their feasibilities on the various applications.

Abstract
Acknowledgements
1 Introduction
2 Improvement of the convergence rate
2.1 Quasi-orthogonal initialization
2.1.1 Optimized Learning Vectors Of NLMS Algorithm
2.1.2 The Quasi-orthonormal Initialization Scheme
2.1.3 Computer Simulations
2.2 Predictive Updating of the Filter Coefficients
2.2.1 Conventionally Repetitive Update Scheme
2.2.2 The Proposed Predictive Update Scheme
2.2.3 Computer Simulations
2.2.4 Summary
2.3 Chaotic Transform Based Modeling for the Active Noise Cancellation
2.3.1 Chaotic Transformation
2.3.2 Secondary Path Modeling
2.3.3 Determining the Tap Number
2.3.4 Noise Cancellation
2.3.5 Summary
2.4 Unified distribution scheme
2.4.1 DC Offset and Dynamic Range Effects of the LMS Algorithm
2.4.2 Modifying the Dynamic Range of Impulse Response of an Unknown System
2.4.3 Computer Simulations
2.5 Data-reusing NLMS Algorithm with Adaptive Updating Times
2.5.1 The Proposed Adaptive Data-reusing Scheme
2.5.2 Computer Simulations
2.5.3 Summary
2.6 Variable Step Size NLMS Algorithm using the Particle Swarm Optimization
2.6.1 Particle Swarm Optimization
2.6.2 Acoustic Echo Cancellation
2.6.3 Summary
3 Reduction of the Computational Complexities
3.1 Fast Data-reusing Normalized Least Mean Squared Algorithm
3.1.1 Fast Data-reusing Normalized Least Mean Square
3.1.2 Analysis of FDRNLMS Convergence Performance
3.1.2.1 Convergence Rate
3.1.2.2 Steady-state Errors
3.1.2.3 Number of Reusing Times in the Steady State
3.1.2.4 Variance Effect of an Input Signal Vector
3.1.3 Computer Simulations
3.1.3.1 Convergence Rate
3.1.3.2 Steady-state Error
3.1.3.3 Effects of Input Signal Vectors’ Variances
3.1.3.4 Acoustic Echo Cancellation
3.1.4 Summary
3.2 Affine Projection Algorithm with Adaptive Projection Dimensions
3.2.1 Affine Projection Algorithms
3.2.1.1 The Conventional Affine Projection Algorithm
3.2.1.2 Fast Affine Projection Algorithms
3.2.1.3 Impact of Projection Dimension, M
3.2.2 The Adaptive Projection Dimension Scheme
3.2.3 Proposed Algorithm Applied in AEC
3.2.4 Summary
3.3 Population Fitness Probability for Effectively Terminating Evolution Operations of a Genetic Algorithm
3.3.1 Probability of Population Fitness
3.3.2 Computer Simulations
3.3.3 Summary
4 Modified Particle Swarm Optimizations and Its Applications
4.1 Particle Swarm Optimization incorporating a Preferential Velocity-Updating Mechanism
4.1.1 Particle Swarm Optimization Incorporating a Preferential Velocity-updating Mechanism
4.1.2 Simulation Results
4.1.2.1 Comparison of DPVU-PSO and CPVU-PSO with Self-evolving PSOs
4.1.2.2 Comparison of DPVU-PSO and CPVU-PSO with Cross-evolving PSOs
4.1.3 Applications in Digital Filter Design via the Proposed LDPSO
4.1.3.1 Parameter Identification of IIR filter
4.1.3.2 Identification of the Room Response in Acoustic Echo Cancellation
4.1.4 Summary
4.2 Particle Swarm Optimization Incorporating Decomposed Objective Functions
4.2.1 Particle Swarm Optimization with Decomposed Objective Functions (PSO-DOF)
4.2.2 Optimization of the Equivalent Circuit for a CPW-fed Monopole Antenna
4.2.3 Summary
5 Conclusion
Appendix A
Appendix B
References

[1] H. Yasukawa, I. Furukawa and Y. Ishiyama, “Acoustic echo control for high quality audio teleconferencing,” Proc. of ICASSP, vol. 3, pp. 2041-2044, 1989.
[2] L. Paarmann and M. Korenberg, “Estimation of the parameters of an ARMA signal model based on an orthogonal search,” IEEE Trans. on Automatic Control, vol. 37, iss. 3, pp. 347-352, 1992.
[3] T. Adail and S. Ardalan, “On the effect of input signal correlation on weight misadjustment in the RLS algorithm,” IEEE Trans. on Signal Processing, vol. 43, no. 4, pp. 988-991, Apr. 1995.
[4] R. Kwong and E. Johnston, “A variable step sized LMS algorithm,” IEEE Trans. on signal Processing, vol. 40, no. 7, pp. 1633-1642, Jul. 1992.
[5] T Aboulnasr and K. Mayyas, “A robust variable step-size LMS-type algorithm: analysis and simulations,” IEEE Trans. on Signal Processing, vol. 45, no. 3, pp. 631-639, Mar. 1997.
[6] S. Peters and A. Antoniou, “A self-tuning NLMS adaptive filter using parallel adaptation,” IEEE Trans. on Circuits and Systems I : Analog and Digital Signal Processing, vol. 44, no. 1, pp. 11-21, Jan .1997.
[7] J. Bermudez and N. Bershad, “Transient and tracking performance analysis of the quantized LMS algorithm for time-varying system identification,” IEEE Trans. on Signal Processing, vol. 44, no. 8, pp. 1990-1997, Aug. 1996.
[8] B. Farhang-Boroujeny and S. Gazor, “Selection of orthonormal transforms for improving the performance of the transform domain normalized LMS algorithm,” IEE Proceeding-F, vol. 139, no. 5, pp. 327-335, Oct. 1992.
[9] T. Chinen, H. Kiya, M. Sagawa, “A new gradient algorithm for FIR adaptive digital filters using multirate technique,” IEEE 33rd Midwest Symposium on CAS 1990, PP. 13-16.
[10] Kiyoshi NISHIKAWA and Hitoshi KIYA, “A technique to improve convergence speed of the LMS algorithm,” ---, pp. 405-408.
[11] J. Nagumo and A. Noda, “A learning method for system identification,” IEEE Trans. On Auto. Control, vol. AC-12, pp.282-287, June 1967.
[12] Deng Julong, “Control problems of grey system,” System and Control Letters, vol. 5, pp. 288-294, 1982.
[13] Mathworks, “Language reference manual (version 5),” Matlab®, 1997.

[14] D. H. Crawford, R. W. Stewart and E. Toma, “Digital signal processing strategies for active noise control,” Journal of Electronics & Communication Engineering, pp. 81-89, April 1997.
[15] S. M. Kuo and D. R. Morgan, Active noise control systems: algorithms and DSP implementations, John Wiley & Sons, Inc., 1996.
[16] J. H. Yun, Y. C. Park and D. H. Youn, “An active noise control algorithm with on-line system identification based on a delayless subband adaptive filter architecture,” IEEE Proceedings of the 40th Midwest Symposium on Circuits and Systems, pp. 1370-1373, 1997.
[17] J. Homer, R. R. Bitmead and I. Mareels, “ Quantifying the effects of dimension on the convergence rate of the LMS adaptive FIR estimator,” IEEE Trans. on Signal Processing, Vol. 46, No. 10, pp. 2611-2615, October 1998.
[18] Heng-Chou Chen, Oscal T.-C. Chen, “The NLMS Alogorithm Using a Quasi-Orthonormal Initialization Scheme for Acoustic Echo Cancellation,” Proc. of IEEE ISCAS, TAA 4-7, 1998
[19] H. Leung and J. Lam, “Design of demodulator for the chaotic modulation communication system,” IEEE Trans. on Circuit and system-I: fundamental theory and applications, vol. 44, no. 3, pp.262-267, March 1997.
[20] S. Haykin, Adaptive filter theory, Prentice-Hall, 1996, third ed.
[21] A. Shoval, D. A. Johns and W. M. Snelgrove, “Comparison of dc offset effects in four LMS adaptive algorithms,” IEEE Tran. on Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 42, No. 3, pp. 176-185, March 1995.
[22] Heng-Chou Chen and Oscal T.-C. Chen, “A predictive updating scheme to improve the NLMS algorithm for Acoustic echo cancellation,” The 1999 IEEE International Symposium on Circuit and System,vol. III, pp. 552-555.
[23] S. Roy and J. Shynk, “Analysis of the data-reusing LMS algorithm,” Proceedings of the 32nd Midwest Symposium on Circuits and Systems, vol. 2, pp. 1127 –1130, 1990.
[24] R. Soni, K. Gallivan and W. Jenkins “Rapid convergence in fault tolerant adaptive algorithms,” Proc. of IEEE International Symposium on Circuits and Systems, vol. 3, pp. 150 –153, 1999.
[25] M. de Campos, P. Diniz and J. Apolinario Jr, “On normalized data-reusing and affine-projections algorithms,” Proceedings of ICECS , vol. 2, pp.843 –846. 1999.
[26] M. de Campos, J. Apolinario Jr. and P. Diniz, “MSE analysis of the binormalized data-reusing LMS algorithm using a discrete-angular- distribution model for the input signal,” Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 3, pp. 1677 –1680, 1998.
[27] B. Schnaufer and W. Jenkins, “New data-reusing LMS algorithms for improved convergence,” Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers, vol. 2, pp. 1584 –1588, 1993.
[28] H. Hahn, B.J . Hosticka and D. Timmermann, “Alternative signal processor arithmetic for modified implementation of a normalized adaptive channel equalizer,” IEE Proceedings F - Radar and Signal Processing, vol. 139, no. 1, pp. 36 – 42, Feb. 1992.
[29] M. J. Reed and M. O. J. Hawksford, “Acoustic echo cancellation with the fast affine projection,” Proc. of IEE Colloquium on Audio and Music Technology: The Challenge of Creative DSP, pp. 16/1 - 16/8, Nov. 1998.
[30] S. Weiss, D. Garcia-Alis and R. W. Stewart, “A subband adaptive equalization structure,” Proc. of IEE Colloquium on Novel DSP Algorithms and Architectures for Radio Systems, pp. 4/1 - 4/7, Sept. 1999.
[31] B. Rafaely and S. J. Elliott, “Adaptive design of robust feedback controllers for active noise control,” Proc. of IEE Colloquium on Active Sound and Vibration Control, pp. 1/1 - 1/4, Nov. 1997.
[32] H. C. So and P. C. Ching, “Comparative study of five LMS-based adaptive time delay estimators,” IEE Proceedings - Radar, Sonar and Navigation, vol. 148, no. 1, pp. 9 – 15, Feb. 2001.
[33] Heng-Chou Chen and Oscal T.-C. Chen, “The NLMS algorithm using a quasi-orthonormal initialization scheme for acoustic echo cancellation,” Proc. of IEEE ISCAS, vol. 4, pp. 213-216, 1998.
[34] M. L. R. de Campos, J. A. Apolinário Jr. and P. S. R. Diniz, “Colored input-signal analysis of normalized data-reusing LMS algorithms,” Proc. of IEEE International Conference on Electronics, Circuits and Systems, vol. 1, pp. 213–216, 1998.
[35] R. Soni, W. Jenkins and K. Gallivan, “Acceleration of normalized adaptive filtering data-reusing methods using the Tchebyshev and conjugate gradient methods,” Proc. of IEEE ISCAS, vol. 5, pp. 309 –312, 1998.
[36] S. Gay and S. Tavathia, “The fast affine projection algorithm,” Proc. of IEEE, ICASSP, pp. 3023 –3026, 1995
[37] M. Rdde and M. Hawksford, “Acoustic echo cancellation with the fast affine projection,” Proc. of IEE Colloquium on Audio and Music Technology: The Challenge of Creative DSP, pp. 16/1 -16/8, 1998.
[38] G. Golub and C. Loan, Matrix Computions, John Hopkins University Press, 1990.
[39] H. Ding, “A stable fast affine projection adaptation algorithm suitable for low-cost processors,” Proc. of IEEE ICASSP, pp. 360 –363, 2000.
[40] J. H. Holland, Adaptation in Natural and Artificial systems, Ann Arbor, MI: Univ. Michigan Press, 1975.
[41] D. E. Goldberg, “Genetic and evolutionary algorithms come of age,” Communications of the ACM, vol. 37, pp. 113-119, no. 3, 1994.
[42] D. H. Goldberg, Genetic algorithm in Search, Optimization, and Machine Learning, New York: Addison Wesley Publishing Company, 1989.
[43] H.-Q Cao, L.-S. Kang, T. Guo, Y.-P. Chen and H. de Garis, “A two-level hybrid evolutionary algorithm for modeling one-dimensional dynamic systems by higher-order ODE models,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 30, issue 2, pp. 351–357, April 2000.
[44] M. N. Howell, T. J. Gordon and F. V. Brandao, “Genetic learning automata for function optimization,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 32, issue 6, pp. 804–815, Dec. 2002.
[45] Y. T. Chan, J. M. Riley and J. B. Plant, “Modeling of time delay and its application to estimation of nonstationary delays,” IEEE Trans. on Acoustic, Speech, Signal Processing, vol. ASSP-29, pp. 577-581, 1981.
[46] D. Dasgupta and D. R. McGregor, “Nonstationary function optimization using the structured genetic algorithm,” Proc. of Parallel Problem Solving from Nature, pp. 145-154, Amsterdam: North Holland, 1992.
[47] M. Antonini, M. Barland, D. Mathieu and I. Daubechies, “Image coding using wavelet transform,” IEEE Trans. on Image Proc., pp. 205-220, April 1992.
[48] B. Goertzel, “A convergence theorem for the simple GA with population size tending to infinity,” IEEE International Conference on Evolutionary Computation, vol. 1, pp. 74, 1995.
[49] Y. Tsujimura and M. Gen, “Entropy-based genetic algorithm for solving TSP,” Proc. of Second International Conference on Knowledge-Based Intelligent Electronic Systems, pp. 285-290, 1998.
[50] D. Adler, “Genetic algorithms and simulated annealing: a marriage proposal,” Proc. of IEEE International Conference on Neural Networks, vol. 2, pp. 1104-1109, 1993.
[51] M. Srinivas and L. M. Patnaik, “Adaptive probabilities of crossover and mutation in genetic algorithms,” IEEE Transactions on Systems, Man and Cybernetics, vol. 24, no. 4, pp. 656-667, 1994.
[52] D. T. Pham and G. Jin, “Genetic algorithm using gradient-like reproduction operator,” Electronics Letters, vol. 31 , no. 18 , pp. 1558–1559, 1995.
[53] Y. Leung, Y. Gao and Z.-B. Xu, “Degree of population diversity-a perspective on premature convergence in genetic algorithms and its markov chain analysis,” IEEE Transactions on Neural Networks, vol. 8, no. 5, pp. 1165-1176, 1997.
[54] R. R. Hill, “A monte carlo study of genetic algorithm initial population generation methods,” Proc. of Winter Simulation Conference, vol. 1, pp. 543-547, 1999.
[55] H.-S. Kim and S.-B. Cho, “An efficient genetic algorithm with less fitness evaluation,” Proc. of the Congress on Evolutionary Computation, vol. 2, pp. 887-894, 2001.
[55] L. Schnitman and T. Yoneyama, “A clustering method for improving the global search cpability,” Proceedings of the Sixth Brazilian Symposium on Neural Networks, pp. 32-37, 2000.
[57] K. Yahiaoui, Y. Hamam and F. Rocaries, “Constrained genetic algorithm-based computer-aided control system design: fixed versus variable size population,” Proceedings of IEEE International Symposium on Intelligent Control, pp. 425-430, 1997.
[58] X. H. Shi, L. M. Wan, H. P. Lee, X. W. Yang, L. M. Wang, and Y. C. Liang, “An improved genetic algorithm with variable population-size and a PSO-GA based hybrid evolutionary algorithm,” Proc. of International Conference on Machine Learning and Cybernetics, vol. 3, pp. 1735–1740, 2003.
[59] A. Hernández-Aguirre and B. P. Buckles, “The probably approximately correct (PAC) population size of a genetic algorithm,” Proceedings of the 12th IEEE International Conference on Tools with Artificial Intelligence, pp. 199-202, 2000.
[60] J. A. Borrie, Stochastic Systems for Engineers: Modeling, Estimation & Control, New Jersey: Prentice Hall, 1992.
[61] D. Beasley, D. R. Bull and R.R. Martin, “An overview of genetic algorithms, Part 1: Fundamentals,” University Computing, vol. 15, no. 2, pp. 58-69, 1993.
[62] G. Rudolph, “Convergence analysis of canonical genetic algorithms,” IEEE Trans. on Neural Networks, vol. 5, pp. 96-101, Jan. 1994.
[63] J. Grefenstette, “Optimization of control parameters for genetic algorithms,” IEEE Trans. on Syst. Man, Cybern., vol. SMC-16, pp. 122-128, Jan./Feb. 1986.
[64] O. Hajji, S. Brisset and P. Brochet, “A stop criterion to accelerate magnetic optimization process using genetic algorithms and finite element analysis,” IEEE Trans. on Magnetics, vol. 39, no. 3, pp. 1297-1299, May 2003.
[65] M. J. Porsani and T. J. Ulrych, “Levinson-type algorithms for polynomial fitting and for Cholesky and Q factors of Hankel and Vandermonde matrices,” IEEE Trans. on Signal processing, vol. 43, no. 1, pp. 63-70, Jan. 1995.
[66] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Networks, pp. 1942-1948, 1995.
[67] W.C. Liu, “Design of a multiband CPW monopole antenna using a particle swarm optimization approach,” IEEE Transactions on Antenna and Propagation, vol. 53, no. 10, pp. 3273-3279, 2005.
[68] R. C. Eberhart and Y. Shi, “Tracking and optimizing dynamic systems with particle swarms,” Proc. of IEEE Congress on Evolutionary Computation, pp. 94-97, Seoul, Korea, 2001.
[69] B. Zao, C.X. Guo and Y.J. Cao, “Improved particle swam optimization algorithm for OPF problems,” Proceedings of the IEEE Power Systems Conference and Exposition, vol. 1, pp. 233-238, Oct. 2004.
[70] J. Robinson and Y. Rahmat-Samii, “Particle swarm optimization in electromagnetics,” IEEE Transactions on Antenna and Propagation, vol. 52, no. 2, pp. 397-407, Feb. 2004.
[71] C.-F. Juang, “A hybrid of genetic algorithm and particle swarm optimization for recurrent network design,” IEEE Transactions on Systems, Man, and Cyberntics- Part B: Cybernetics, vol. 34, no. 2, pp. 997-1006, April 2004.
[72] W.-P. Huang, L.-F. Zhou and J.-X. Qian, “FIR filter design: frequency sampling filters by particle swarm optimization algorithm,” Proceedings of the IEEE Third International Conference on Machine Learning and Cybernetics, pp. 2322-2327, Aug. 2004.
[73] D.J. Krusienski and W. K. Jenkins, “Design and performance of adaptive systems based on structured stochastic optimization strategies,” IEEE Circuits and Systems Magazine, pp. 8-20, First Quarter 2005.
[74] S. Baskar, A. Alphones, P.N. Suganthan and J. J. Liang, “Design of Yagi-Uda antennas using comprehensive learning particle swarm optimization,” IEE Proceedings of Microwave Antennas Propagation, vol. 152, no. 5, pp. 340-346, Oct. 2005.
[75] A. Ratnaweera, S. K. Halgamuge and H. C. Watson, “Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients,” IEEE Transactions on Evolutionary Computation, vol. 8, no. 3, pp. 240-255, June 2004.
[76] S. Janson and M. Middendorf, “A hierarchical particle swarm optimizer and its adaptive variant,” IEEE Transactions on Systems, Man and Cybernetics- Part B: Cybernetics, vol. 35, no. 6, pp. 1272-1282, Dec. 2005.
[77] G. Ciuprina, D. Ioan and I. Munteanu, “Use of intelligent- particle swarm optimization in electromagnetics,” IEEE Transactions on Magnetics, vol. 35, no. 2, pp. 1037-1040, March 2002.
[78] M.D. Migliore, D. Pinchera and F. Schettino, “A simple and robust adaptive parasitic antenna,” IEEE Transactions on Antennas and Propagation, vol. 53, no. 10, pp. 3262-3272, October 2005.
[79] M.A. Tuko, M. Naghed and I. Wolff, “Novel 18/36 GHz MMIC GaAs FET frequency doublers in CPW techniques under the consideration of the effects of coplanar discontinuities,” IEEE Transactions on Microwave Theory Techniques, vol. 45, pp. 1307-1315, Aug. 1993.
[80] G. Tzeremes, T. S. Liao, P. K. L. Yu and C. G. Christodoulou, “Computation of equivalent circuit models of optically driven CPW-fed slot antennas for wireless communications,” IEEE Antennas and Wireless Propagation Letter, vol. 2, pp.140-142, 2003.
[81] Y. S. Lin and C. H. Chen, “Lumped-component impedance-transforming uniplanar transitions and their antenna applications,” IEEE Transactions on Microwave Theory and Techniques, vol. 52, no. 4, pp. 1157-1165, April 2004.
[82] Y. Tsutsumi, H. Kanaya and K. Yoshida, “Design and performance of an electrically small slot loop antenna with a miniaturized superconducting matching circuit,” IEEE Transactions on Applied Superconductivity, vol. 15, no. 2, pp. 1020-1023, June 2005.
[83] K. V. Puglia, “Electromagnetic simulation of some common balun structures,” IEEE Microwave Magazine, pp. 56-61, Sept. 2002.
[84] I Pele, A. Chouseeaud and S. Toutain, “Simultaneous modeling of impedance and radiation pattern antenna for UWB pulse modulation,” Proc. of IEEE International Symposium on Antennas and Propagation, vol. 2, pp. 1871-1874, June 2004.
[85] K. Veeramachaneni, L. A. Osadciw and P. K. Varshney, “An adaptive multimodal biometric management algorithm,” IEEE Transactions on System, Man and Cybernetics-Part C, vol. 35, no. 3, pp. 344-356, 2005.