在手持行動裝置中，回音干擾消除是維持良好通訊品質的一項重要技術。傳統上，我們通常使用適應性濾波器消除回音干擾，然而因為回音等效通道通常很長，因此適應性濾波器需要很多的抽頭係數來實現，才能將回音消除至可令人接受的程度。這種長抽頭係數的濾波器將使得適應性濾波器的運算複雜度大幅提升，這對電力有限的行動裝置的影響很大。既有的部分更新最小均方(Partial Update Least Mean Square, PU-LMS)演算法可有效降低運算複雜度，但卻也因為部分更新的緣故，使得LMS演算法的收斂速度降低。

為了改善這個問題，本論文提出一種新的方式，是以部分更新演算法理論為基礎，結合時變步階函數並使用一段時間內所估測出的錯誤訊號的均值，來作為調整步階函數的依據，再透過決策機制來切換步階函數的計算方式，這種方式我們稱之為切換式時變步階部分更新最小均方演算法(S-VSS PU-LMS)。藉由錯誤信號之間的相關性使得當一開始錯誤值較高時可以得到較大的步階值，以調快收斂速度，而且當誤差值變低時，演算法會自動調整為較小的步階值，使得最後的收斂誤差值較低。所謂『切換式』指的就是開始時我們用錯誤訊號與其內插值的關聯性去近似最佳步階值；隨著錯誤值變小，便切換為使用錯誤值與其單位延遲的錯誤值之關聯性去近似最佳步階值。我們提出的這個演算法必須在更新係數較高(大於50%)時，對於收斂速度才會有明顯的改善。

在電腦模擬中，我們採用數種標準的回音通道，且與既有的文獻比較，結果發現我們所提出的S-VSS PU-LMS演算法幾乎都可以得到令人滿意的表現，且此方式在『順序式 (Sequential)』與『M-最大 (M-max)』這兩類型的PU演算法，均可有效運作。此外我們使用德州儀器的數位訊號處理器TMS320C6713 發展版(DSK)實現S-VSS PU-LMS演算法，以證明其在硬體實作上之可實現性。

For power-limited mobile devices, how to prolong battery life is an important issue. The voice communication needs to implement high computation complexity echo cancellation to obtain a satisfied voice quality. Partial update least mean square (PU-LMS) adaptive algorithms are known solutions to reduce the computation complexity for long-tap adaptation, such as echo cancellation. However, the convergence rate is decreased due to the partial update algorithm only updates part of weights of the adaptive filters.

This thesis proposes a switching-based variable step-size (S-VSS) approach for PU-LMS algorithms. During the initial stage, the errors are dominated by the mismatch between the tap weights of the adaptive filter and its ideal weights. We correlate the error signals with linear interpolated error signals to gain a large step-size; on the other hand, during the steady state, the errors mainly come from the additive noise. Therefore, we switch the correlation to the other mode so that the effect of noise can be eliminated. This can be done by correlating the error signals with a delayed version of error signals and hence a small step-size is obtained during the late stages.

In computer simulation, we adopt several different echo channels to evaluate the effectiveness of our proposed S-VSS PU-LMS algorithm. For both the sequential and the M-max PU-LMS algorithms, the S-VSS approach outperforms some related works. In addition, we also implement our algorithm on the TMS320C6713 DSP Starter Kit (DSK) to verify that our algorithm is hardware implementable.

摘要.....................................................................I
Abstract...............................................................II
圖目錄.................................................................V
表目錄.................................................................VII
1 緒論..................................................................1
1.1 研究目的與動機.................................................2
1.2 文獻探討.............................................................2
1.3 研究方法.............................................................3
1.4 本文架構.............................................................4
2 適應性濾波器演算法介紹..............................................5
2.1 LMS演算法............................................................6
2.2 部分更新LMS演算法(PU-LMS)介紹...............................7
2.2.1 隨機式(Stochastic)...........................................7
2.2.2 週期式(Periodic)...................................................8
2.2.3 順序式(Sequential).................................................8
2.2.4 M-最大(M-Max).......................................................9
3 切換式時變步階部分更新演算法..........................................12
3.1 時變步階演算法.........................................................12
3.2 切換式時變步階部分更新演算法........................................15
4 模擬結果與討論...........................................................19
4.1 實驗背景與結果分析......................................................19
4.2 MATLAB GUI...........................................................42
5 S-VSS PU-LMS演算法實用實例..........................................44
5.1 TMS320C6713 DSK......................................................44
5.1.1 DSP架構介紹.........................................................45
5.1.2 DSK架構介紹.........................................................46
5.1.3 程式發展環境流程......................................................47
5.2 應用一:系統識別(System Identification)..........................49
5.3 應用二:回音干擾消除(Echo Cancellation)...........................52
6 結論與未來研究方向........................................................57
6.1 結論..................................................................57
6.2 未來研究方向...........................................................57
參考文獻...................................................................58

[1] Spectrum digital: C6713 dsp kit (dsk) for ti tms320c6713. [Online].
Available: http://www.element14.com/community/docs/DOC-39399/
l/spectrum-digital-c6713-dsp-kit-dsk-for-ti-tms320c6713
[2] Tms320c6713 dsp starter kit (dsk). [Online]. Available: http://www.ti.com/
tool/tmdsdsk6713
[3] Y.-R. Chien, W.-L. Mao, and H.-W. Tsao, “Design of a robust multi-channel
timing recovery system with imperfect channel state information for 10gbaset,”
IEEE Trans. on Circuits and Syst. I, vol. 57, pp. 886–896, 2010.
[4] M. K. A. Enteshari, J. Fadlullah, “Joint channel and echo impulse response
shortening for high-speed data transmission,” IEEE Syst., vol. 3, pp. 270–
276, 2009.
[5] C. Breining, P. Dreiscitel, E. Hansler, A. Mader, B. Nitsch, H. Puder,
T. Schertler, G. Schmidt, and J. Tilp, “Acoustic echo control—an application
of very-high-order adaptive filters,” IEEE Signal Process.Mag., vol. 16,
pp. 42–69, 1999.
[6] G. Deng, “Partial update and sparse adaptive filters,” IET Signal Processing.,
vol. 1, no. 1, pp. 9–17, 2007.
[7] J. Yang, X. Zhu, G. Sobelman, and K. K. Parhi, “Sparseness-controlled adaptive
tap algorithms for partial update adaptive filters,” in 7th International
Conference on Information, Communications and Signal Processing, 2009,
pp. 1–5.
[8] H. Deng and M. Doroslovacki, “New sparse adaptive algorithms using partial
update,” in in Proc. IEEE Int. Conf. Acoustics., Speech, Signal Process(
ICASPP’04), vol. 2, 2004, pp. 845–848.
[9] K. Doğançay, Partial-Update Adaptive Signal Processing :Design, Analysis
and Implementation, 1st ed. Academic Press, 2008.
[10] T. Aboulnasr and K. Mayyas, “A robust variable step size lms-type algorithm:
Analysis and simulations,” IEEE Trans. Signal Processing, vol. 45,
pp. 631–639, 1997.
[11] S. Douglas, “Adaptive filters employing partial updates,” IEEE Trans. Circuits
Syst. II, Analog Digit. Signal Process., vol. 44, no. 3, pp. 209–216,
1997.
[12] M. Godavarti and A. Hero, “Partial update lms algorithms,” IEEE Trans.
Signal Process., vol. 53, no. 7, pp. 2382–2399, 2005.
[13] T. Aboulnasr and K. Mayyas, “Complexity reduction of the nlms algorithm
via selective coefficient update,” IEEE Trans. Signal Processing, vol. 47,
no. 5, pp. 1421–1427, 1999.
[14] K. Dogancay and O. Tanrikulu, “Adaptive filtering algorithms with selective
partial updates,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal
Process., vol. 48, no. 8, pp. 762–769, 2001.
[15] G. Carter, “Special issue on time delay estimation,” in IEEE Trans. Acoust.,
Speech, Signal Processing, vol. 49, no. 1, pp. 12–12, 1980.
[16] J. Ianniello, “Large and small error performance limits for multipath time
delay estimation,” IEEE Trans. Acoust., Speech, Signal Process., vol. 34,
no. 2, pp. 245–251, 1986.
[17] ——, “High-resolution multipath time delay estimation for broad-band random
signals,” IEEE Transactions on Acoustics, Speech and Signal Processing,
vol. 36, no. 3, pp. 320–327, 1988.
[18] H. Amindavar and P. Moghaddam, “Estimation of propeller shaft rate and
vessel classification in multipath environment,” in in Proc. IEEE Sensor
Array Multichannel Signal Process. Workshop,, Cambridge,MA, 2000, pp.
125–128.
[19] P. Moghaddam, H. Amindavar, and R. Kirlin, “A new time-delay estimation
in multipath,” IEEE Trans. Signal Processing., vol. 51, no. 5, pp. 1129–1142,
2003.
[20] K. Mayyas, “A variable step-size selective partial update LMS algorithm,”
Digital Signal Processing., vol. 23, no. 1, pp. 75–85, 2013.
[21] M. S. E. Abadi and J. H. Husoy, “Mean-square performance of the family of
adaptive filters with selective partial updates,” Signal Processing., vol. 88,
no. 8, pp. 2008 – 2018, 2008.
[22] M. S. E. Abadi and F. Moradiani, “A unified approach to tracking performance
analysis of the selective partial update adaptive filter algorithms in
nonstationary environment,” Digit. Signal Process., vol. 23, no. 13, pp. 817
– 830, 2013.
[23] B. Widrow and M. Hoff, “Adaptive switch circuits,” WESCON Conv.Rec,
no. 4, pp. 96–140, 1960.
[24] I. Pitas, “Fast algorithms for running ordering and max/min calculation,”
IEEE Trans.Circuits and Systems, vol. 36, no. 6, pp. 795–804, June 1989.
69