本論文係以選擇最佳的二進位的樹狀架構並且每2 P 層插入延遲元件建構適於硬體設計的心律式陣列架構為基礎。發展一新型樹狀心律式處理單元(PE)和最佳化樹狀層數法則, 可建構出高效率DLMS心律式適應性數位濾波器架構｡ 應用這樹狀心律式PE， 可獲得比傳統的DLMS 架構更高的收斂性， 並且擁有心律式陣列架構的特性。在字元級(word level)方面,不僅在高傳輸量下操作, 且考慮有限的驅動/更新回饋錯誤信號。而且，根據我們提議的最佳化樹狀層數法則，可建構出最小延遲數目和高規律性，此有效的N-層心律式數位濾波器容易被在最大的回饋錯誤信號的驅動之限制條件下確定。此新型適應性數位濾波器架構､保持令人滿意的收斂特性､最快的輸出､有限的驅動/更新的能力､高度的模組化與區域性連接和不增加額外的面積等特性。 我們利用電腦模擬透過一個可適性等化器的例子驗證我們的心律式的陣列架構。最後，我們再利用Xilinx FPGA和UMC 0.18um 1P6M cell-based 設計，來驗證實際架構。

Selecting optimized binary tree structure and inserting the delay element every 2P tap to construct the systolic array suitable for hardware design are investigated in this thesis. We develop an efficient systolic architecture for the delay least-mean-square (DLMS) adaptive finite impulse response (FIR) digital filter based on a new tree-systolic processing element (PE) and an optimized tree-level rule. Applying tree-systolic PE, a higher convergence rate than that of the conventional DLMS structures can be obtained without sacrificing the properties of the systolic-array architecture. It is not only to operate at the highest throughput in the word-level but also to consider finite driving/update of the feedback error signal. Moreover, based on our proposed optimized tree-level rule that takes account of minimum delay and high regularity, an efficient N-tap systolic adaptive FIR digital filter can be easily determined under the constraint of maximum driving of the feedback error signal. The efficient systolic architecture that maintains satisfactory convergence performance has the same lowest critical period and finite driving/update, as well as high degrees of modularity and locality at no extra area cost. We verify our systolic array structure via example of adaptive equalizers by computer simulation. Finally, we imitate architecture and utilize Xilinx FPGA as well as UMC 0.18um 1P6M Cell-based Design.

Chapter 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Overview of Research Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.2 Overview of Research Method and Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Overview of Thesis Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

Chapter 2 Overview of Adaptation Algorithm and Adaptive DLMS Filters Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1 LMS Adapter Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Transversal Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 The LMS Adaptation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 LMS Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
2.5 The DLMS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

Chapter 3 An Efficient Systolic Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 A new Generalized tree-systolic Processing Element (PE) Constructed by Inserting Delay Elements. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
3.3 Overall Systolic Architecture with Cascaded tree-systolic PEs. . . . . . . . . . . . . . .12
3.4 A new Systolic Array Structure Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.5 Minimum Delay D Versus Different Values p. . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.6 Reduces the Critical Path. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.7 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

Chapter 4 Applications of the Efficient Systolic DLMS Adaptive Digital Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

4.1 Comparisons of the Different N-tap Adaptive FIR Filter Architecture. . . . . . . . . 19
4.2 Application of the Efficient Systolic DLMS Adaptive Equalization Filter. . . . . . .22

Chapter 5 Design Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25

5.1 FPGA Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
5.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
5.1.2 Development Environment and Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
5.1.3 FPGA Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27
5.1.4 FPGA Verify Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
5.2 Chip Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
5.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
5.2.2 Development Environment and Flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.3 Chip layout and summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35
5.2.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37

Chapter 6 Conclusions & Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

References
[1]. S. Haykin, Adaptive Filter Theory, 3rd ed. Englewood Cliffs, NJ: Prentice-Hall, 1996, ch. 9.

[2]. B.Widrow, J. M. McCool, M. G. Larimore, and C. R. Johnson, Jr., “Stationary and nonstationary learning characteristics of the LMS adaptive filter,” Proc. IEEE, vol. 64, pp. 1151–1162, Aug. 1976.

[3]. Lan-Da Van and Wu-Shiung Feng, “An Efficient Systolic Architecture for the DLMS Adaptive Filter and Its Applications,” IEEE Trans., Analog and Digital Signal Processing, vol. 48, pp. 359–366, April 2001.

[4]. Oppenheim, Alan V. / Schafer, Ronald W. et al. Discrete-Time Signal Processing, Second Edition, NJ: Prentice-Hall, Dec. 1998.

[5]. G. Long, F. Ling, and J. G. Proakis, “The LMS algorithm with delayed coefficient adaptation,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 37, pp. 1397–1405, Dec. 1999.

[6]. Keshab K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation, NJ: John Wiley, Dec. 1998.

[7]. H. Herzberg, R. Haimi-Cohen, and Y. Be’ery, “A systolic array realization of an LMS adaptive filter and the effects of delayed adaptation,” IEEE Trans. Signal Processing, vol. 40, pp. 2799–2803, Nov. 1992.

[8]. M. D. Meyer and D. P. Agrawal, “A high sampling rate delayed LMS
filter architecture,” IEEE Trans. Circuits Syst. II, vol. 40, pp. 727–729,
Nov. 1993.

[9]. K. Matsubara, K. Nishikawa, and H. Kiya, “Pipelined adaptive filters
based on delayed LMS algorithm,” IEICE Trans., vol. J79-A, pp. 1050–1057, May 1996.

[10] “Pipelined LMS adaptive filter using a new look-ahead transformation,” IEEE Trans. Circuits Syst. II, vol. 46, pp. 51–55, Jan. 1999.

[11]. PACT, Application Note, Adaptive Filter Based on the LMS-Algorithm.

[12]. Emmanuel C. lfeachor Barrie W. Jerves, Digital Signal Processing, A practical Approach Second Edition, NJ: Prentice-Hall, Sep. 2001.

[13]. Uwe Meyer-Baese , Digital Signal Processing with Field Programmable Gate Arrays, NJ: Springer-Verlag, Sep. 2001.

[14]. Sinead Mullins, Conor Heneghan, Alternative Least Mean Square Adaptive Filter Architectures for Implementation on Field Programmable, Digital Signal Processing Group, Department of Electronic and Electrical Engineering, University College Dublin, Dublin 4, Ireland.

[15]. Peter M. Athanas, Chair, Mark T. Jones, Jeffrey H. Reed. “Design and Implementation of an FPGA-based Adaptive filter Single-User Receiver”, the Virginia Polytechnic Institute and State University of Electrical Engineering, Sep. 1999, Blacksburg, Virginia.

[16]. Lok-Kee Ting, Beng., Algorithms and FPGA Implementations of Adaptive LMS-based Predictors for Radar Pulse Identification, thesis Submitted for the Degree of Doctor of Philosophy to the Faculty of Engineering Queen’s University Belfast, July 2001.

[17]. 張智星, MATLAB 程式設計與應用. 清蔚科技出版, 2000年9月.

[18]. Xilinx, Virtex-II™ V2MB1000 Development Board User’s Guide, Version 3.0, December 2002.

[19]. Xilinx, Virtex-II Platform FPGAs : Complete Data Sheet, DS031 (v3.4) March 1, 2005.