臺灣博碩士論文加值系統

在眾多用於訊號處理的特殊應用積體電路 (ASIC)中，比如有限脈衝響應濾波器(FIR filter) 、無限脈衝響應濾波器(IIR filter) 、離散餘弦轉換 (DCT)和快速傅立葉轉換(FFT)，多常數乘法是一項廣泛用於取代一般乘法器的做法。只用加法器、減法器和平移的多常數乘法模組可以大幅度減少硬體面積。對高速的應用而言，因為基於進位傳遞加法器 (carry propagation adder)的多常數乘法有著冗長的進位傳遞，所以基於進位儲存加法器(carry save adder)的架構的多常數乘法就發展出來。目前的基於進位儲存加法器的架構的多常數乘法只發展到將進位儲存加法器的數量最佳化，卻忽略了每個進位儲存加法器在實作上的差異。然而，不像進位傳遞加法器，一般的正負號延伸 (sign extension)並不適用於進位儲存加法器。而且，在每個進位儲存加法器之間，字元長度的變異性是很強烈的。在本篇論文中，我們提出一個叫做智慧型正負號延伸的系統化的正負號延伸方法來減少字元長度。將其和精確位元計算技術結合後，再用整數線性規畫(ILP)來做多常數乘法設計的面積最佳化。實驗結果顯示，和傳統的多常數方法比較，面積的改善幅度最高可達30%。

Multiple constant multiplication (MCM) method is widely adopted as a replacement of general purpose multiplier in many ASIC signal processing systems such as FIR filter, IIR filter, DCT and FFT. The MCM block that consists only adders, subtractors and shifters can reduce area cost significantly. For high-speed applications, carry save adder (CSA) based MCM is proposed because the long carry propagation path in traditional carry propagation adder (CPA) is reduced. Currently, all published algorithms of CSA-based MCM problem only count to word level without touching the details of implementation. However, unlike CPA, trivial sign extension is not suitable for CSA. Also, the word length variation in different CSA's is large. In this thesis, we propose a new systematic method called smart sign extension to reduce adder bits and combine it with accurate bit counting while doing MCM area optimization by an ILP (Integer Linear Programming) tool. Experimental results show an area improvement up to 30% compared to the conventional MCM method.

Content
目錄
摘要 ....................................................................................................................i
Abstract ............................................................................................................ ii
Acknowledgement .................................................................................................... iii
Content ............................................................................................................ iv
List of Tables ............................................................................................................. vi
List of Figures ............................................................................................................ vii
Chapter 1. Introduction ......................................................................................................... 1
1.1 Multiple Constant Multiplication (MCM) .................................................... 1
1.2 Introduction to MCM Algorithms ............................................... 7
1.2.1 Common Subexpression Elimination (CSE) Algorithm .......................................... 7
1.2.2 Graph Algorithm ................................................ 9
1.3 MCM Using Carry Save Adder for Addition Implementation ...................................... 13
Chapter 2. Previous Work ....................................................................................................... 15
2.1 CPA-Based Algorithms ................................................................................................. 15
2.2 CSA-Based Algorithms ................................................................................................. 16
Chapter 3. Proposed Algorithm ............................................................................................... 18
3.1 Bit Level Area Optimization Using CSA-Based Structure ........................................... 18
3.2 Problem Formulation ..................................................................................................... 22
3.3 Overall Flow ................................................................................................................ 22
3.4 Find AGN representations for Constants....................................................................... 25
3.5 Construct Boolean Network .......................................................................................... 27
3.6 Calculation of Number of Adder Bits for All Additions ............................................... 30
v
3.6.1 Calculation of Number of Adder Bits..................................................................... 30
3.6.2 Smart Sign Extension ............................................................................................. 32
3.6.3 Bit Propagation for OR Operation .......................................................................... 42
3.7 Transform Boolean Network to 0-1 ILP Problem ......................................................... 43
Chapter 4. Experimental Results ............................................................................................. 46
Chapter 5. Conclusion .......................................................................................................... 52
Reference ........................................................................................................... 53

Reference
[1] N. Weste and D. Harris, “ Datapath subsystems, ” in CMOS VLSI Design: A Circuits and Systems Perspective, 3rd ed. Pearson Education, 2005, ch. 10, pp. 667.
[2] P.R. Cappello and K. Steiglitz, “ Some complexity issues in digital signal processing, ” IEEE Trans. Acoust. Speech, Signal Process, vol. ASSP-32, no. 5, pp. 1037–1041 , Oct., 1984.
[3] L. Aksoy, E. Costa, P. Flores, and J. Monteiro, “Minimum number of operations under a general number representation for digital filter synthesis,” in Proc. IEEE Eur. Conf. Circuit Theory Des., Aug., 2007, pp. 252–255.
[4] L. Aksoy, E. Gunes, and P. Flores, “Search algorithms for the multiple constant multiplications problem: exact and approximate, ” Elsevier J. Microprocess. Microsyst, vol. 34, no. 5, pp. 151–162, Aug., 2010.
[5] L. Aksoy, E. Gunes, and P. Flores, “An exact breadth-first search algorithm for the multiple constant multiplications problem, ” in Proc. IEEE Norchip Conference, Nov., 2008, pp. 41–46.
[6] O. Gustafsson and L.Wanhammar, “ILP modelling of the common subexpression sharing problem,” in Proc. Int. Conf. Electron., Circuits Syst., Sept., 2002, pp. 1171–1174.
[7] R. Hartley, “Subexpression Sharing in Filters using Canonic Signed Digit Multipliers,” IEEE Trans. Circ. Syst, vol. 43, no. 10, pp. 677–688, Oct., 1996.
[8] R. Pasko, P. Schaumont, V. Derudder, S. Vernalde, and D. Durackova, “A new algorithm for elimination of common subexpressions,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 18, no. 1, pp. 58–68, Jan., 1999.
[9] Y.H. Ho, C.U. Lei, H.-K. Kwan, and N. Wong, “Global optimization of common subexpressions for multiplierless synthesis of multiple constant multiplications, ” in Proc. IEEE Design Automation Conf., Asia and South Pacific, Jan., 2008, pp. 119–124.
[10] I.C. Park and H.J. Kang, “Digital filter synthesis based on minimal signed digit representation,” in Proc. Des. Autom. Conf., Aug., 2001, pp. 468–473.4.
[11] A. Dempster and M. Macleod, “Use of Minimum-Adder Multiplier Blocks in FIR Digital Filters, ” IEEE Trans. Circ. Syst, vol.42, no. 9, pp. 569– 577, Sept., 1995.
[12] Y. Voronenko and M. Pschel, “Multiplierless multiple constant multiplication,” ACM Trans. Algorithms, vol. 3, no. 2, pp. 1–38, May., 2007.
[13] M. Kumm, M. Faust, P. Zipf, and C.H. Chang, “ Pipelined Adder Graph Optimization for High Speed Multiple Constant Multiplication, ” in Proc. IEEE Int. Symp. Circuits Syst, May, 2012, pp. 49–52.
[14] L. Aksoy, C. Lazzari, E. Costa, P. Flores, and J. Monteiro, “Design of Digit-Serial FIR Filters: Algorithms, Architectures, and a CAD Tool, ” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 21, pp.498–511, Mar., 2013.
[15] T. Noll, “Carry-Save Arithmetic for High-speed Digital Signal Processing,” in Proc. IEEE Int. Symp. Circuits Syst’90, May., 1990, vol. 2, pp. 982-986.
[16] V. A. Bartlett and A. G. Dempster, “Using carry-save adders in low-power multiplier blocks,” in Proc. IEEE Int. Symp. Circuits Syst., May, 2001, pp. 222–225.
[17] O. Gustafsson, H. Ohlsson, and L. Wanhammar, “Minimum-adder integer multipliers using carry-save adders,” in Proc. IEEE Int. Symp. Circuits Syst., May, 2001, pp. 709–712.
[18] A. Hosangadi, F. Fallah, and R. Kastner, “Optimizing High Speed Arithmetic Circuits using Three-Term Extraction,” in Proc. Design, Automation and Test in Europe , Mar., 2006, pp. 1294–1299.
[19] A. Hosangadi, F. Fallah, and R. Kastner, “Multiplier Blocks using Carry-Save Adders,” in Proc. IEEE Int. Symp. Circuits Syst., May., 2004, pp.473-476.
[20] O. Gustafsson and L. Wanhammar, “Low-complexity constant multiplication using carry-save arithmetic for high-speed digital filters,” in Proc. Image and Signal Processing and Analysis, Sept., 2007, pp. 212–217.
[21] L. Aksoy and E. Gunes, “Area Optimization Algorithms in High-Speed Digital FIR Filter Synthesis,” in Proc. 21st Annu. Symp. on Integr. Circuits Syst. Des., Sept., 2008, pp. 64–69.
[22] ALGOS. Group, INSEC-ID. (Jan. 28, 2013). Filter Benchmarks [Online]. Available: http://algos.inesc-id.pt/multicon/index.php?Downloads:Filter_Benchmarks#BenchmarksBySpec
[23] C.H. Chang and M. Faust (Oct. 03, 2011). FIR Filter data found in the literature [Online]. Available: http://www.firsuite.net/FIR/FromPublication
[24] K. Johansson, "Low power and low complexity shift-and-add based computations," Ph.D. dissertation, Department of Electrical Engineering, Linköping University, Linköping, Sweden, 2008.
[25] M. Aktan, A. Yurdakul, and G. Dündar, “An algorithm for the design of low-power hardware-efficient fir filters,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 55, no. 7, pp. 1536–1545, Jul., 2008.
[26] A. P. Vinod, E. M. K. Lai, A. B. Premkuntar, and C. T. Lau, “FIR filter implementation by efficient sharing of horizontal and vertical common subexpressions, ” Electron. Lett., vol. 39, no. 2, pp. 251–253, Jan., 2003.
[27] T. Yoshino, R. Jain, P. T. Yang, H. Davis, W. Gass, and A. H. Shah, “A 100-MHz 64-Tap FIR Digital Filter in 0.8-pm BiCMOS Gate Array, ” IEEE J. Solid-State Circuits, vol. 25, no. 6, pp. 1494–1501, Dec., 1990.
[28] Y. C. Lim and S. Parker, “Discrete coefficient FIR digital filter design based upon an LMS criteria, ” IEEE Trans. Circuits Syst., vol. 30, no. 10, pp. 723–739, Oct., 1983.