常數乘法之演算法與其硬體實現

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：31

、訪客IP：3.12.34.178

姓名

鞠萍章(Ping-Chang Jui) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

常數乘法之演算法與其硬體實現
(Efficient Algorithms for Constant Multiplications and Their Hardware Implementation)

相關論文

★ 用於類比/混和訊號積體電路可靠度增強的加壓測試	★ 應用於電容陣列區塊之維持比值良率的通道繞線法
★ 應用於2.5G/5GBASE-T乙太網路傳收機之高成本效益迴音消除器	★ 應用於IEEE 802.3bp車用乙太網路之硬決定與軟決定里德所羅門解碼器架構與電路設計
★ 適用於 10GBASE-T 及 IEEE 802.3bz 之高速低密度同位元檢查碼解碼器設計與實現	★ 基於蛙跳演算法及穩定性準則之高成本效益迴音消除器設計
★ 運用改良型混合蛙跳演算法設計之近端串音干擾消除器	★ 運用改良粒子群最佳化演算法之近端串擾消除器電路設計
★ 應用於多兆元網速乙太網路接收機類比迴音消除器之最小均方演算法電路設計	★ 高速無進位除法器設計
★ 應用於數位視頻廣播系統之頻率合成器及3.1Ghz寬頻壓控震盪器	★ 地面數位電視廣播基頻接收器之載波同步設計
★ 適用於通訊系統之參數化數位訊號處理器核心	★ 以正交分頻多工系統之同步的高效能內插法技術
★ 正交分頻多工通訊中之盲目頻域等化器	★ 增強CMOS鎖相迴路可靠度

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

整數常數乘法器用於執行整數常數值與輸入數值的相乘，相乘的執行不需乘法器而僅用加法及移位即可。一般而言，移位可以固線(hardwired)方式於板塊間連接，就硬體實現成本而言被視為是免費的；因此所需加法器的數量決定整數常數乘法器硬體實現的成本。
整數常數乘法為數位信號處理演算法最普遍的運算之一，常應用於數字信號處理、影像處理、高精度的算術運算、加密等；整數常數乘法也可應用於信息冗餘設計所需的算術編碼技術如AN碼、乘法布斯編碼技術、高基數的SRT除法等。
常數乘法器的設計已經研究了數十年，其重點在於如何減少單一或多個常數乘法所需的加法器數量，對所需的加法器類型並不關心。本論文著眼於高速常數乘法之高效演算法和硬體實現的研究，並以常數(2^k+-1)的快速乘法為範疇。
(2^k+1)N的運算值可由N值加上2^kN值 (將N值向左移k位元) 而得；另一方面，(2^k-1)N的運算值可由2^kN值減去N值，或加 (-N) 值而得。本論文提出一快速的加法基本單元 (UCA)，並據以建構UCA為主之加法器。UCA與常用的全加器（FA）相比，UCA僅需一個單位的邏輯閘延遲，而FA需要二個單位延遲。模擬結果顯示，所提出的基於UCA的加法器，如漣波進位加法器 (RCA)、超前進位加法器 (CLA)，以及混合RCA/CLA加法器（HyA），相較於基於FA的相同型加法器有較快速的性能及較低的硬體實現成本。所提出的UCA設計理念可很容易的應用於其他不同類型的整數常數乘法。

摘要(英)

Integer constant multiplier performs a multiplication of a data-input with an integer constant value. The multiplication by a fixed-point constant can be done “multiplier-less” using additions and shifts only. Since the shifters are implemented as hard-wired inter-block connections, they are considered “free.” Thus, the number of adders determines the implementation cost.
The integer constant multiplication is a common operation in digital signal processing (DSP) algorithms with the following applications: digital signal processing, image processing, multiple precision arithmetic, cryptography, etc. It can also be applied for the arithmetic coding technique, such as AN code for information redundant design, Booth encoding technique for multiplications, and high-radix SRT division, etc.
Constant multiplier designs have been investigated for several decades. However, the emphasis was placed on minimizing the number of additions required to achieve the multiplications with single constant or multiple constants. Moreover, the types of adders to be implemented are not of concern. This motivates to this study developing efficient algorithms and hardware implementation for fast constant multiplications. This study focuses on the development of fast multiplications of the constants in the form of (2^k+-1).
The value of (2^k+1)N can be computed by adding N to its k-bit left-shifted value 2^kN. On the other hand, the value of (2^k-1)N can be computed by subtracting N from its k-bits left-shifted value 2^kN, or adding (-N) to 2^kN. The fast unit cells for additions (UCAs) are introduced to construct the UCA-based adders. The proposed UCA cells requires only one gate delay, while the conventional full adder (FA) needs two gate delays. Simulation results will show that the proposed UCA-based adders, such as ripple carry adders (RCAs), carry lookahead adders (CLAs), and hybrid RCA/CLA adders (HyAs), achieve faster speed performance with reasonably small hardware cost than the FA-based ones. The UCA design concept is readily applied to the multiplications with the constants in other forms.

關鍵字(中)

★ 常數乘法
★ 乘法器
★ 漣波進位加法器
★ 超前進位加法器
★ 混合加法器

關鍵字(英)

★ Constant multiplication
★ multiplier
★ ripple carry adders
★ carry lookahead adders
★ hybrid adders

論文目次

Chinese Abstract i
English Abstract ii
Acknowledgement iv
Table of Contents v
List of Figures viii
List of Tables x
Chapter 1. Introduction 1
1.1 Motivation 1
1.2 Research Motivation 3
1.3 Thesis Organization 4
Chapter 2. Background 5
2.1 Chapter Overview 5
2.2 Constant Multiplication 5
2.3 Adder Design 7
2.3.1 Ripple Carry Adders (RCAs) 7
2.3.2 Carry Lookahead Adders (CLAs) 8
Chapter 3. 3N and N/3 Operations 11
3.1 Introduction to 3N and N/3 Operations 11
3.2 Algorithm Development for 3N Operation 13
3.2.1 Finite State Machine 13
3.2.2 Shannon Expansion Theorem 15
3.3 Fast Hardware Implementation 16
3.3.1 Basic Cells 16
3.3.2 Ripple Carry Adders (RCAs) 17
3.3.3 Carry Look-Ahead Adders (CLAs) 18
3.3.4 Performance Evaluation 20
3.4 Hybrid Adders (HyA) 23
3.4.1 Hardware Implementation 23
3.4.2 Performance Evaluation 25
3.5 Algorithm Development for N/3 Operation 28
3.5.1 Finite State Machine 28
3.5.2 Shannon Expansion Theorem 31
3.5.3 Hardware Implementation 32
3.6 Summary 34
Chapter 4. (2^k±1)N Operations 35
4.1 Introduction to (2^k±1)N Operations 35
4.2 Algorithm Development for (2^k+1)N Operations 35
4.2.1 5N Operations 36
4.2.2 9N Operations 39
4.2.3 (2^k+1)N Operation 43
4.3 Hardware Implementation for (2^k+1)N Operations 45
4.3.1 5N Operation 46
4.3.2 (2^k+1)N Operation 48
4.3.3 Performance Evaluation 52
4.4 Algorithm Development for (2^k-1)N Operation 57
4.4.1 7N Operation 58
4.4.2 (2^k-1)N Operation 60
4.4.3 Hardware Implementation 62
4.5 2^r(2^k+-1)^sN Operations 64
4.5.1 2^kN Operations 64
4.5.2 (2^r3^k)N Operations 64
4.5.3 2^r(2^k±1)^sN Operations 67
4.6 Summary 67
Chapter 5. Conclusions and Future Research Works 69
5.1 Summary 69
5.2 Conclusions and Contributions 70
5.3 Future Research Works 72
References 74

參考文獻

[1] P. R. Cappello and K. Steiglitz, “Some complexity issues in digital signal processing,” IEEE Trans. on Acoustics, Speech, and Signal Processing, Vol.ASSP-32, No. 5, pp.1037-1041, May 1984.
[2] A. K. Oudjida and N. Chaillet, “Radix-2r arithmetic for multiplication by a constant,” IEEE Trans. On Circuits and Systems – II: Express Briefs, Vol. 61, No.5, pp.349-353, May 2014.
[3] D. Pradhan, Fault-tolerant Computer System Design, Prentice Hall, 1996.
[4] B. Johnson, Design and Analysis of Fault-Tolerant Digital Systems, Addition Wesley, 1989
[5] N. Gaitanis, “Totally self-checking checker for 3N arithmetic codes,” Electronics Letter, Vol. 17, pp.685-686, 1983.
[6] K. Huang, Computer Arithmetic: Principles, Architecture, and Design, Wiley & Sons, Inc., 1979.
[7] I. Koren, Computer Arithmetic Algorithms, Prentice-Hall, Inc., New Jersey, 1993.
[8] M. J. Flynn and S. F. Oberman, Advanced computer arithmetic design, John Wiley, 2001.
[9] M. D. Ercegovac and T. Lang. Digital Arithmetic. Morgan Kaufmann, 2003.
[10] R. Brent and P. Zimmermann, Modern computer arithmetic, Cambridge University Press, 2010.
[11] C. L. Wey, "Built-In Self-Test (BIST) Design of High-Speed Carry-free Dividers," IEEE Trans. on VLSI Systems, Vol. 4, No. 1, pp. 141-145, March 1996.
[12] C. L. Wey and C.-P. Wang, "A Fast Radix-4 SRT Divider and Its VLSI Implementation," IEE Proceedings, Computers and Digital Techniques. Vol. 146, No.4, pp.205-210, July 1999.
[13] C. L. Wey, "Design of Fast High-Radix SRT Dividers and Their VLSI Implementation," IEE Proceedings, Computers and Digital Techniques, Vol.147, No.4, pp.275-282, July 2000.
[14] R. Bernstein, “Multiplication by integer constants,” Software – practice and experience, Vol. 16, No. 7, pp. 641–652, July 1986.
[15] V. Lefevre, “Multiplication by an integer constant,” INRIA, Technical Research Report 4192, May 2001.
[16] A. G. Dempster and M. D. Macleod, “Constant integer multiplication using minimum adders,” IEE Proc. Circuits, Devices, and Systems, Vol. 141, No. 5, pp. 407–413, 1994.
[17] V. Dimitrov, L. Imbert, and A. Zakaluzny. “Multiplication by a constant is sublinear,” Proc. of IEEE 18th Symposium on Computer Arithmetic, pp. 261–268. 2007.
[18] Y. Voronenko and M. Puschel, “Multiplierless multiple constant multiplication,” ACM Trans. on Algorithms, Vol. 3, No. 2, May 2007.
[19] Y. Takshashi, T. Sekine, and M. Yokoyama, “A comparison of multiplierless multiple constant multiplication using common subexpression elimination method,” Proc. IEEE Midwest Symp. on Circuits and Systems, pp.298-301, 2008.
[20] A. D. Booth, “A signed binary multiplication technique,” Quarterly Journal of Mechanics and Applied Mathematics, vol. 4, no. 2, pp. 236– 240, 1951, reprinted in E. E. Swartzlander, Computer Arithmetic, Vol. 1, IEEE Computer Society Press Tutorial, Los Alamitos, CA, 1990.
[21] R. I. Hartley, “Subexpression sharing in filters using canonic signed digit multipliers,” IEEE Trans. on Circuits and Systems II: Analog and Digital Signal Processing, vol. 43, no. 10, pp. 677–688, October 1996.
[22] S.-K. Chang and C. L. Wey, “A Fast 64-bit Hybrid Adder Design in 90nm CMOS Process,” Proc. of IEEE Midwest Symp. on Circuits and Systems, Boise, Idaho, pp.414-417, August 2012.
[23] R. P. Brent and H. T. Kung, “A regular layout for parallel adders,” IEEE Trans. on Computers, vol. 31, no. 3, pp. 260–264, Mar. 1982.
[24] C. L. Wey, P.-C. Jui, and G.-N. Sung, “Efficient Multiply-by-3 and Divide-by-3 Algorithms and Their Fast Hardware Implementation,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E97-A, No. 2, pp.616-623, February 2014.
[25] P.-C. Jui, G.-N. Sung, and C. L. Wey, “Efficient algorithm and hardware implementation of 3N for arithmetic and for radix-8 encodings,” Proc. of IEEE Midwest Symp. on Circuits and Systems, Boise, Idaho, pp.418-421, August 2012.

指導教授

魏慶隆、薛木添(Chin-Long Wey Muh-Tian Shiue)

審核日期

2015-5-27

推文