基於 Expanding Subexpression Space 之整係數 FIR 濾波器設計與實現

簡易檢索 / 詳目顯示

回結果列表

研究生：	沙中霖 Chung-Lin Sha
論文名稱：	基於 Expanding Subexpression Space 之整係數 FIR 濾波器設計與實現 Fixed-point FIR Filter Design and Implementation in the Expanding Subexpression Space
指導教授：	姚嘉瑜 Chia-Yu Yao
口試委員:	許新添 Hsin-Teng Hsu 簡江儒 Chiang-Ju Chien 王乃堅 Nai-Jian Wang
學位類別：	碩士 Master
系所名稱：	電資學院 - 電機工程系 Department of Electrical Engineering
論文出版年：	2009
畢業學年度：	97
語文別：	英文
論文頁數：	98
中文關鍵詞：	FIR濾波器、HDL程式產生器、Common Subexpression Elimination (CSE) 、定點式係數、線性規劃、Expanding Subexpression Space
外文關鍵詞：	FIR Filter, HDL Code Generator, Common Subexpression Elimination (CSE), fix-point coefficient, linear programming, Expanding Subexpression Space
相關次數：	點閱：261 下載：7
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本論文提出了一個整合整係數濾波器的設計與實現於一個設計流程的方法。本論文所提出的方法是在 expanding subexpression space 的架構下設計整係數濾波器的係數，在濾波器設計的同時，也同時評估硬體實現的複雜度，並回授到演算法內讓演算法可以根據硬體的複雜度反覆的重新設計濾波器係數。論文中的例子顯示出我們可以得到比之前其他研究結果較低的硬體複雜度。此外本論文亦提供自動將濾波器實現轉換成 Verilog 或 VHDL 程式碼的 HDL 產生器，並與Matlab 之 fdatool 產生的 HDL 程式碼性能做比較。

This thesis presents a method of combining the design and the implementation of fixed-point FIR filters into one design flow. The proposed method designs the fixed-point coefficients in an expanding subexpression space. During the design process, the implementation cost is estimated as well and the cost is fed back to the design routine such that the algorithm can redesign the fixed-point coefficients iteratively. Design examples show that we can obtain better hardware-cost-effective FIR filters than the results reported by other researchers. This thesis also contributes an HDL generator of FIR filters designed by the proposed method. It can generate Verilog or VHDL code of the FIR filter. Comparison of the HDL code performance with the code designed by Matlab’s fdatool is also given in this thesis.

摘要	                                                                   I
Abstract	                                                                 III
致謝	                                                                   V
Table of Contents	                                                        VII
List of Figures	                                                         IX
List of Tables	                                                       XIII
Chapter 1 Introduction	                                                 1
1.1 The Advantage of FIR Filters	                                        1
1.2 Background and Motivation	                                        1
1.3 Overview of The Proposed Method	                                        3
Chapter 2 Theory                                                             5
2.1 FIR Filter Structure                                                     5
2.2 Replacing Multipliers by Adder/Subtracter Units                          7
2.3 Using CSD to Implement The Coefficients                                  7
2.4 Common Subexpression Elimination                                         9
2.5 Subexpression Space                                                     10
Chapter 3 The Proposed Method                                               13
3.1. Expanding Subexpression Space                                          13
3.2. Problem Formulation                                                    14
3.2.1. Determining the Upper and Lower Bounds of Each Coefficient           15
3.2.2 Searching the Coefficients                                            17
3.2.3 Acceleration of Solving Linear Programming                            18
3.3 The Proposed Algorithm                                                  20
3.4 The Prediction Strategy                                                 25
3.4.1 Predicting The Number of Adders of The Remaining Coefficients	   25
3.4.2 Comparing with the Up-To-Date Solution at the Current Level	   27
3.5 Design of Long FIR Filters                                              27
3.6 The Bit Width of Adders and Registers                                   29
3.7 A Workout Example                                                       30
3.7.1 Comparison with MATLAB’s Fdatool                                     36
Chapter 4 Experimental Results                                              38
4.1 Comparison with the Result of Previous Paper                            38
4.2 Baseband Filters for CDMA 2000                                          58
4.2.1 A Baseband Filter for Spreading Rate 1 of CDMA 2000                   58
4.2.2 A Baseband Filter for Spreading Rate 3 of CDMA 2000                   66
Chapter 5 Conclusions                                                       73
References                                                                  75
Author                                                                      80

                                

[1] Y. C. Lim and S. R. Parker, “FIR filter design over a discrete powers-of-two coefficient space,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP31, pp.583591, June 1983.
[2] Y. C. Lim and S. R. Parker, “Discrete coefficient FIR digital filter design based upon an LMS criteria,” IEEE Trans. Circuits Syst., vol. CAS30, pp 723739, Oct. 1983.
[3] H. Samueli, “An improved search algorithm for the design of multiplierless FIR filters with powers-of-two coefficients,” IEEE Trans. Circuits Syst., vol. 36, pp. 10441047, July 1989.
[4] Y. C. Lim and S. R. Parker, “Design of discrete-coefficient-value linear phase FIR filters with optimum normalized peak ripple magnitude,” IEEE Trans. Circuits Syst., vol. 37, pp. 14801486, Dec. 1990.
[5] R. Cemes and D. Ait-Boudaoud, “Genetic approach to design of multiplierless FIR filters,” Electronics Letters, vol. 29, pp. 20902091, Nov. 25, 1993.
[6] H. Shaffeu, M. M. Jones, H. D. Griffiths, and J. T. Taylor, ” Improved design procedure for multiplier-less FIR digital filters,” Electronics Letters, vol. 27, pp. 11421144, June 20, 1991.
[7] C.-L. Chen and A. N. Willson Jr., “A trellis search algorithm for the design of FIR filers with signed powers-of-two coefficients,” IEEE Trans. Circuits Syst. II, vol. 46, pp. 2939, Jan. 1999.
[8] Y. C. Lim, R. Yang, D. Li, and J. Song, “Signed-power-of-two term allocation scheme for the design of digital filters,” IEEE Trans. Circuits Syst. II, vol. 46, pp. 577584, May 1999.
[9] C.-Y. Yao, “A Study of SPT-term Distribution of CSD numbers and its application for Designing Fixed-point Linear Phase FIR Filters,” Proc. 2001 IEEE Int’l Symp. on Circuits and Systems, Sydney, Australia, May 2001, vol. II, pp. 301304.
[10] C.-Y. Yao and C.-J. Chien, “A Partial MILP Algorithm for the Design of Linear Phase FIR Filters with SPT Coefficients,” IEICE Trans. Fundamentals of Electronics, Communications, and Computer Sciences, vol. E85A, no. 10, pp. 23022310, Oct. 2002.
[11] M. Aktan, A. Yurdakul, and G. Dundar, “An Algorithm for the Design of Low-Power Hardware-Efficient FIR Filters”, IEEE Trans. Circuits Syst. I, vol. 55, pp. 15361545, July 2008.
[12] R. I. Hartley, “Subexpression sharing in filters using canonic signed digit multipliers,” IEEE Trans. Circuits Syst. II, vol. 43, pp. 677688, Oct. 1996.
[13] P. Paško, P. Schaumont, V. Derudder, S. Vernalde, and D. Ďuračková, “A new algorithm for elimination of common subexpressions,” IEEE Trans. Computer-Aided Design, vol. 18, pp. 5868, Jan. 1999.
[14] M. Martínez-Peiró, E. I. Boemo, and L. Wanhammar, “Design of high-speed multiplierless filters using nonrecursive signed common subexpression algorithm,” IEEE Trans. Circuits Syst.II, vol. 49, pp. 196203, Mar. 2002.
[15] C.-Y. Yao, H.-H. Chen, T.-F. Lin, C.-J. Chien, and C.-T. Hsu, “A novel commonsubexpression-elimination method for synthesizing fixed-point FIR filters,” IEEE Trans. Circuits Syst. I., vol. 51, no. 11, pp. 22152221, Nov. 2004.
[16] C.-Y. Yao, H.-H. Chen, C.-Y. Chien, and C.-T. Hsu, “A high-level synthesis procedure for linear-phase fixed-point FIR filters with SPT coefficients,” International Journal of Electrical Engineering, vol. 12, no. 1, pp. 7584, Feb. 2005.
[17] D. R. Bull and D. H. Horrocks, “Primitive operator digital filters,” Proc. IEE, pt. G, vol. 138, pp. 401412, Mar. 1991.
[18] A. G. Dempster and M. D. Macleod, “Constant integer multiplication using minimum adders,” IEE Circuits Devices Syst., vol. 141, pp. 407413, Oct. 1994.
[19] D. Li, “Minimum number of adders for implementing a multiplier and its application to the design of multiplierless digital filters,” IEEE Trans. Circuits Syst. II, vol. 42, pp. 453460, July 1995.
[20] A. G. Dempster and M. D. Macleod, “Use of minimum adder multiplier blocks in FIR digital filters,” IEEE Trans. Circuits Syst. II, vol. 42, pp. 569577, Sep. 1995.
[21] H.-J. Kang and I.-C. Park, “FIR filter synthesis algorithms for minimizing the delay and the number of adders,” IEEE Trans. Circuits Syst. II, vol. 48, pp. 770777, Aug. 2001.
[22] O. Gustafsson and L.Wanhammar, “Design of linear-phase FIR filters combining subexpression sharing with MILP,” in Proc. MWSCAS’02, 2002, pp. 9–12.
[23] Y. J. Yu and Y. C. Lim, “Design of linear phase FIR filters in sub- expression space using mixed integer linear programming”, IEEE Trans. Circuits Syst. I, vol. 54, pp. 23302338, Oct. 2007.
[24] W. H. Press, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C. New York: Cambridge University Press, 1992, pp. 430443.
[25] H. Samueli, “On the design of optimal equiripple FIR digital filters for datatransmission applications”, IEEE Trans. Circuits and Systems, vol. 35, pp. 15421546, Dec. 1988.
[26] J. H. McClellan, T. W. Parks, and L. R. Rabiner, “A computer program for designing optimum FIR linear phase digital filters,” IEEE Trans. Audio Electroacoust., vol. AU21, pp. 506–526, Dec. 1973.
[27] Physical Layer Standard for cdma2000 Spread Spectrum Systems- Revision D. Technical Specification Group C, 3GPP2, Sep. 2005.

簡易檢索 / 詳目顯示

相關論文