臺灣博碩士論文加值系統

算術單元為數位系統中進行基本運算的最主要部份，特別是在計算機微處理器以及數位訊號處理器。而在算術單元的設計上，不同數字系統的選用通常會影響算術單元的組成架構、計算的精準度、電路面積、計算時間延遲以及電路的功率消耗。本論文針對浮點數及對數等二種不同的數字系統，在32位元算術單元的設計之下進行算術運算上的比較與分析。其中，在對數加、減法的部份，我們提出了一種新的架構，在此架構之下我們只要透過訊號線的控制，即可輕易利用同一份的硬體電路來求得 、 、 、 、 及 等六種不同的複雜函數，以達到硬體共用及減少成本付出的目的。

我們使用硬體描述語言實做了浮點數與對數這二種不同數字系統的算術單元，再經ModelSim模擬驗證後並以客製化指令的方式將此二種不同的算術單元加入Nios SOPC的系統發展環境中，以供應用程式直接呼叫使用。為了得到這二種不同數字系統的執行效率及硬體成本的比較分析，我們設計了三個簡單的應用實例(動能、勢能函數和正弦函數)，架構在這二種不同的數字系統上執行，最後根據這些比較數據的結果，我們可以推出浮點數數字系統與對數數字系統的優缺點，與它們在算術系統的使用時機為何。

Arithmetic units used for performing basic operations, especially for microprocessors and digital signal processors, are the most important components in the digital systems. When arithmetic units are designed, their architecture, precision, area of circuit, delay, and power consumption of the circuit will usually be affected by different number systems selected. My thesis compared and analyzed the Floating-Point (FLP) Number System, and Logarithmic Number Systems (LNS) based on the design of a 32-bit arithmetic unit. We proposed a new architecture in the addition and subtraction of LNS. As long as we can take control of the signal line under this architecture, we can easily get six different kinds of complicated functions, , , , , and by using the same hardware circuit, and achieve the objectives of sharing hardware and reducing the payable cost. We implemented the arithmetic units of FLP and LNS by using hardware description language. After simulation and verification by ModelSim, we integrated FLP and LNS into the development environment of Nios SOPC system by utilizing custom instructions so that they can be called by application software.
We designed three simple application instances (Kinetic Energy, Potential Function, and Sine Function) carried out via FLP and LNS to get the comparative analyses of the FLP and LNS in terms of their execution efficiency and hardware cost. Finally, we can infer some benefits and drawbacks of the FLP and LNS and when we can use them in the arithmetic system, according to the results of the comparative data.

致謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 viii
表目錄 xi
第一章 導論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 原理和方法 5
1.4 研究方向及工作 7
1.5 論文架構 8
第二章 浮點數數字系統 9
2.1 IEEE 浮點數數字系統標準格式及其可表示的範圍與精準度 9
2.2 浮點數之四則運算 12
2.2.1 浮點數之加減法原理 12
2.2.2 浮點數之乘法原理 14
2.2.3 浮點數之除法原理 15
2.2.4 高效率浮點數除法演算法及電路設計 16
2.2.4.1 牛頓勒普森理論介紹 17
2.2.4.2 級數展開理論介紹 18
2.2.4.3 高效能除法器 20
2.3 浮點數中計算 的演算法 21
第三章 對數數字系統 23
3.1 對數數字系統格式及其可表示的範圍與精準度 23
3.2 對數數字系統之四則運算 27
3.3 快速對數運算之硬體演算法 29
3.3.1 倒數演算法 30
3.3.1.1 倒數的產生 30
3.3.1.2 正規化因子的推導 31
3.3.2 對數的運算 32
3.4 一種應用於快速指數運算的加法正規化方法 34
3.4.1 演算法 35
3.4.2 新正規因子 36
第四章 指數函數與對數函數的硬體實做 38
4.1 指數函數硬體電路之設計 38
4.2 對數函數硬體電路之設計 47
第五章 一個多功能的對數數字系統加減法單元架構 52
5.1 、 、 、 及 演算法 52
5.2 五大硬體單元設計 56
5.2.1 第一乘法單元硬體元件之設計 61
5.2.2 指數單元硬體元件之設計 63
5.2.3 加減單元硬體元件之設計 64
5.2.4 對數單元硬體元件之設計 67
5.2.5 第二乘法單元硬體元件之設計 68
5.2.6 一個多功能的對數數字系統加減單元完整電路圖 72
第六章 三個應用實例 74
6.1 動能的簡介 74
6.1.1 動能的定義 74
6.1.2 動能在FLP與LNS中的運算 75
6.2 二體勢能的簡介 77
6.2.1 二體勢能的定義 77
6.2.2 Lennard-Jones二體勢能函數在FLP與LNS中的運算 79
6.3 正弦函數的簡介 80
6.3.1 正弦函數的泰勒展開式 80
6.3.2 正弦函數在FLP與LNS中的運算 84
第七章 Nios II系統發展環境的介紹 86
7.1 Nios II嵌入式軟核處理器介紹 87
7.2 Nios II發展環境 88
7.2.1 發展版介紹 88
7.2.2 客製化指令 90
7.2.2.1 客製化邏輯電路區塊可為下列種類的組合 92
7.2.3 使用者自訂邏輯 96
7.2.4 客製化指令的使用 99
7.2.5 系統頻率的影響 100
7.2.6 系統時間分析 102
第八章 實驗結果 110
8.1 自訂客製化指令 110
8.2 實現FLP於Nios II處理器 111
8.3 實現LNS於Nios II處理器 113
8.4 三個應用實例的實驗結果 114
8.4.1 動能在FLP與LNS中的運算結果 114
8.4.2 Lennard-Jones二體勢能函數在FLP與LNS中的運算結果 115
8.4.3 正弦函數在FLP與LNS中的運算結果 116
8.5在LNS與FLP中分別以硬體方式來計算 的實驗結果 117
8.6 實驗結果分析 118
第九章 結論與未來展望 121
9.1 結論 121
9.2 未來展望 122
參考文獻 124

[1] J. N. Coleman and E. I. Chester, “Arithmetic on the European Logarithmic Microprocessor,” IEEE Transactions on Computers, vol. 49, no. 7, pp. 702-715, JULY. 2000.
[2] Israel Koren, Computer Arithmetic Algorithms, New Jersey: Prentice-Hall, Inc., chapter 4, pp.45-70, 1993.
[3] G. L. Sicuranza, “On efficient implementations of 2-D digital filters using logarithmic number system,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-31, pp. 877-885, 1983.
[4] E. E. Swartzlander Jr., D. V. S. Chandra, H. T. Nagle Jr., and S. A. Starks, "Sign/logarithm arithmetic for FFT implementation," IEEE Transactions on Computers, vol. C-32, pp. 526-534, June 1983.
[5] Debasish Das, Krishnendu Mukhopadhyaya, and Bhabani P. Sinha, “Implementation of four common functions on an LNS co-processor,” IEEE Transaction on Computers, vol. 44, no. 1, pp. 155-161, Jan. 1995.
[6] T. Stouraitis and V. Paliouras, “Considering the alternatives in low-power design,” IEEE Circuits and Devices Magazine, July 2001, pp. 22-29.
[7] Chichyang Chen, Rui-Lin Chen, and Chih-Huan Yang, “Pipelined Computation of Very Large Word-Length LNS Addition/Subtraction with Polynomial Hardware Cost,” IEEE Transactions on Computers, vol. 49, no. 7, pp. 716-726, July 2000.
[8] Albert A. Liddicoat and Michael J. Flynn, “High-Performance Floating Point Divide,” Proc. Euromicro Symposium on Digital Systems, pp. 354-361, 2001.
[9] Chichyang Chen, Rui-Lin Chen, “A hardware algorithm for fast logarithmic computation”, Journal of the Chinese Institute of Engineer, 2005.
[10] Chichyang Chen and Kuo-Sheng Cheng, “ An Efficient Exponential Algorithm with Exponential Convergence Rate,” Proceedings of the EUROMICRO Systems on Digital System Design, pp.548-555, Aug. 2004.
[11] Yu-Chi Lin, “Implementation of Speech Recognition Using a System-on-a-Programmable-Chip System,” Thesis of Feng-Chia University, 2004.
[12] T. A. Brubaker and J. C. Becker, “Multiplication using logarithms implemented with read-only memory,” IEEE Transactions on Computers, Vol. C-24, pp. 761-765, Aug. 1975.
[13] F. J. Taylor, R. Gill, J. Joseph, and J. Radke, “A 20 bit logarithmic number system processor,” IEEE Transactions on Computers, Vol. 37, Issue 2, pp. 190-200, 1988.
[14] M. L. Frey and F. J. Taylor, “A table reduction technique for logarithmically architected digital filters,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-33, no. 3, pp. 718-719, June 1985.
[15] David M. Lewis, “An architecture for addition and subtraction of long word length numbers in the logarithmic number system,” IEEE Transactions on Computers, vol. 39, no. 11, pp. 1325-1336, Nov. 1990.
[16] Lawrence K. Yu and David M. Lewis, “A 30-b integrated logarithmic number system processor," IEEE Journal of Solid-State Circuits, vol. 26, pp. 1433-1440, Oct. 1991.
[17] David M. Lewis, “Interleaved memory function interpolators with applications to an accurate LNS arithmetic unit,” IEEE Transactions on Computers, vol. 43, no. 8, pp. 974-982, Aug. 1994.
[18] Hartmut Henkel, “Improved addition for logarithmic number system,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, no. 2, pp. 301-303, Feb. 1989.
[19] J. N. Coleman and E. I. Chester, “A 32-bit logarithmic arithmetic unit and its performance compared to floating-point,” Proceedings of 14th IEEE Symposium on Computer Arithmetic, Australia, pp. 142-151, 1999.
[20] Mark G. Arnold, Thomas A. Bailey, John R. Cowles, and Jerry J. Cupal, “Redundant logarithmic arithmetic," IEEE Transactions on Computers, vol. 39, pp. 1077-1086, Aug. 1990.
[21] Jean-Michel Muller, Alexandre Scherbyna, and Arnaud Tisserand, “Semi-Logarithmic number systems,” IEEE Transactions on Computers, vol. 47, no. 2, pp. 145-151, Feb. 1998.
[22] Fang-shi Lai and Ching-Farn Eric Wu, “A hybrid number system processor with geometric and complex arithmetic capabilities,” IEEE Transactions on Computers, vol. 40, no. 8, pp. 952-962, Aug. 1991.
[23] Chichyang Chen, Rui-Lin Chen, “Performance-improved computation of very large word-length LNS addition/subtraction using signed-digit arithmetic,” Proceedings of IEEE International Conference on Application-Specific Systems, Architectures, and Processors, pp. 337-347, Jul. 2003.
[24] J. –A. Pineiro, M. D. Ercegovac, J. D. Bruguera, “High-radix logarithm with selection by rounding,” Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors (ASAP’02), 2002, pp. 101-110.
[25] J. F. Hart et al., Computer Approximations. New York: John Wiley & Sons, 1968.
[26] I. Koren and O. Zinaty, “Evaluating elementary functions in a numerical co-processor based on rational approximations,” IEEE Transactions on Computers, vol. 39, no. 8, pp. 1030-1037, Aug. 1990.
[27] Vitit kantabutra, “On hardware for computing exponential and trigonometric functions,” IEEE Transactions on Computers, vol. 45, no. 3, pp 328-339, March 1996.
[28] N. Tagagi, T. Asada, and S. Yamjima, “Redundant CORDIC methods with a constant scale factor,” IEEE Transactions on Computers, vol. 40, no. 9, pp. 989-995, Sept. 1991.
[29] P. W. Baker, “Parallel multiplicative algorithms for some elementary functions,” IEEE Transactions on Computers, pp. 322-525, 1973.
[30] M. Ercegovac, “Radix-16 evaluation of certain elementary functions,” IEEE Transactions on Computers, vol. 22, pp. 561-566, 1973.
[31] J.H. Irving and J.G.Kirkwood, “The statical mechanical theory of transport property. IV. The equation of hydro-dynamics”, J.Chem.phys., 18 , p.817-823, 1950.
[32] Hsueh-Chieh Chen, A hardware algorithm for fast Digit On-line logarithmic computation.Thesis of Feng-Chia University, 2004.