臺灣博碩士論文加值系統

座標旋轉數位電腦演算法(CORDIC)是一種算術演算法，利用一連串的疊代運算來執行各種不同基本函數的運算；而雙旋轉座標旋轉數位電腦演算法則是以減少疊代次數與計算時間來達到提升座標旋轉的速度。
本篇論文將提出一個簡單的三維空間旋轉之硬體用於三維空間電腦繪圖和卡通繪製上，這一個簡單的架構是基於二維的座標旋轉數位電腦演算法。除此之外，我們使用自動擺放及繞線的工具實現出三維空間旋轉之晶片佈局圖。我們所提出之架構是利用二維的座標旋轉數位電腦演算法處理器作實現，此架構是簡單而又規則，非常適合用於超大型積體電路之實現。由本論文所提出的演算法與架構，三維空間的幾何旋轉也會被改善。

The COordinate Rotation DIgital Computer (CORDIC) algorithm is an arithmetic algorithm to evaluate various elementary functions through a series of iterative operations. However, the Double Rotation CORDIC Algorithm (DRCA) achieves to accelerate coordinate rotation by reducing the iterations and computation time.
The hardware primitives of 3-D rotation for high-speed 3-D computer graphics and animation are presented in this paper. The primitives are based on the 2-D CORDIC algorithm. Besides, we use Auto-Place and Route tool to implement 3-D rotation chip implementation. The proposed architecture is implemented by 2-D CORDIC processors; therefore, the architecture is not only simple and regular, but also suitable for VLSI implementation. The 3-D geometry rotation would be improved by the proposed algorithm and architecture.

中文摘要．．．．．．．．．．．．．．．．．．．．．．．．．I
英文摘要．．．．．．．．．．．．．．．．．．．．．．．．．II
誌謝．．．．．．．．．．．．．．．．．．．．．．．．．．．III
目錄．．．．．．．．．．．．．．．．．．．．．．．．．．．IV
圖目錄．．．．．．．．．．．．．．．．．．．．．．．．．．VI
表目錄．．．．．．．．．．．．．．．．．．．．．．．．．．XI
第一章 導論 ．．．．．．．．．．．．．．．．．．．．．．1
1.1 研究動機 ．．．．．．．．．．．．．．．．．．．．．1
1.2 研究方法 ．．．．．．．．．．．．．．．．．．．．．2
第二章 CORDIC演算法．．．．．．．．．．．．．．．．．．4
2.1 CORDIC函數的基本功能 ．．．．．．．．．．．．．．4
2.1.1 長度修正因子 ．．．．．．．．．．．．．．．．．．6
2.2 CORDIC的基本原理 ．．．．．．．．．．．．．．．．8
2.3 CORDIC的三種座標系統函數 ．．．．．．．．．．． 10
2.3.1 線性座標系統函數．．．．．．．．．．．．．．．．13
2.3.2 圓座標系統函數．．．．．．．．．．．．．．．．．16
2.3.3 雙曲線座標系統函數．．．．．．．．．．．．．．．19
2.4 CORDIC收斂性質．．．．．．．．．．．．．．．．．22
2.5 CORDIC演算法總覽．．．．．．．．．．．．．．．．24
2.6 雙旋轉CORDIC演算法．．．．．．．．．．．．．．．25
第三章 三維空間中的CORDIC旋轉．．．．．．．．．．．．27
3.1 球座標系統與笛卡爾座標系統之關連性．．．．．．．．27
3.2 三維空間中的CORDIC旋轉 ．．．．．．．．．．．．36
3.3 利用傳統CORDIC演算法來完成三維空間中的CORDIC
旋轉的VLSI架構圖．．．．．．．．．．．．．．．．39
3.4 ModelSim所作之模擬結果．．．．．．．．．．．．．．43
3.4.1 額外的座標產生器所作之ModelSim模擬．．．．．．．43
3.4.2 座標產生器所作之ModelSim模擬．．．．．．．．． 44
3.5 新的架構及演算法帶來的衝擊效應．．．．．．．．．．45
第四章 晶片實現與CORDIC誤差分析．．．．．．．．．．．46
4.1 晶片佈局圖．．．．．．．．．．．．．．．．．．．．46
4.1.1 結果分析．．．．．．．．．．．．．．．．．．．． 55
4.2 CORDIC誤差分析．．．．．．．．．．．．．．．．．56
第五章 結論．．．．．．．．．．．．．．．．．．．．．．72
參考文獻．．．．．．．．．．．．．．．．．．．．．．．．．74
發表論文列表．．．．．．．．．．．．．．．．．．．．．．．77

[1] D. Luebke, M. Reddy, J. D. Cohen, A. Varshney, B. Watson, R.
Huebner,Level of Detail for 3-D Graphics, Morgan Kaufmann Pub.,
2003.
[2] D. H. Eberly, 3-D Game Engine Design-A Practical Approach to
Real-Time Computer Graphics, Morgan Kaufmann Pub., 2001.
[3] J. E. Volder, “The CORDIC Trigonometric Computing Technique,”
IRE Transactions on Electronic Computers, Vol. EC-8, 1959, pp.
330-334.
[4] J. S. Walther, “A Unified Algorithm for Elementary Functions,”
Spring Joint Computer Conference Proceedings, Vol.38, 1971,
pp.379-385.
[5] O. Mencer, L. Semeria, M. Morf, J. Delosme, “Application of
Reconfigurable CORDIC Architecture,” The Journal of VLSI Signal
Processing, Special Issue on Reconfigurable Computing, March
2000.
[6] T. Lang, E. Antelo, “High-Throughput 3-D Rotations and
Normalizations,” Thirty-Fifth Asilomar Conference on Signal,
Systems and Computers, 2001, pp.846-851.
[7] J. Euh, J. Chittamuru, W. Burson, “CORDIC Based Interporator
for 3-D Graphics,” IEEE Workshop on Signal Processing
Systems,2002,pp.240-245.
[8] D. E. Thomas, P. H. Moorby, The Verilog Hardware Description
Language, Fifth Edition, Kluwer Academic Pub. 2002.
[9] Model ModelSim Products: http://www. model.com/products.
[10] Synopsys FPGA Express, http://www. synopsys.com/products.
[11] Xilinx FPGA products, http://www. xilinx.com/products.
[12] T. Lang, E. Antelo, “High-Throughput CORDIC-Based Geometry
Operations for 3-D Computer Graphics,” IEEE Transactions on
Computers, Vol. 54, No. 3, March 2005, pp. 347-361.
[13] O. Mencer, L. Semeria, M. Morf, J. Delosme, “Application of
Reconfigurable CORDIC Architectures,” The Journal of VLSI
Signal Processing, Special Issue on Reconfigurable Computing,
Vol. 24, Nos.2-3, March 2000, pp.211-221.
[14] E. Antelo, J. Villalba, J. D. Bruguera, E. L. Zapata, “High
Performance Rotation Architectures Based on the Radix-4 CORDIC
Algorithm,”IEEE Transactions on Computers, Vol. 46, No. 8,
August 1997,pp.855-870.
[15] S. F. Hsiao, J. M. Delosme, “Householder CORDIC Algorithm,”
IEEE Transactions on Computers, Vol. 44, No. 8, pp.990-1001,
August 1995.
[16] “TSMC 0.18 1P6M CMOS Design Libraries and Technical Data,
Version 3.1” Taiwan Semiconductor Manufacturing Company
(TSMC), Hsinchu, Taiwan, R.O.C., and Chip Implementation
Center(CIC), National Science Council, Hsinchu, Taiwan,
R.O.C.,Dec. 2005.
[17] 施明洲, “雙旋轉之座標旋轉演算法之高效能正弦及餘弦產生器
及三維空間旋轉之分析與製作”,中華大學碩士論文,2005.
[18] 林國珍, “CORDIC演算法之運算誤差分析”,中華工學院碩士論
文,1997.
[19] Milos D. Ercegovac and Tomas Lang, Digital Arithmetic, Morgan
Kaufmann Publisher, 2004.
[20] S. Wang, E. E. Swartzlander Jr., “Merged CORDIC Algorithm”,
Proc.Int’l Symp. Circuit and Systems, 1998, pp. 1988-1991.
[21] I. Koren, “Computer Arithmetic Algorithms, Second Edition”,
A. K. Peters, Natick, MA, 2002, Chapter 5.
[22] T. Y. Sung, Y. H. Hu, H. J. Yu, “Doubly pipelined CORDIC array
for digital signal processing algorithms”, IEEE ICASSP
Int’l Conf. on Acoustics,Speech and Signal Processing, Tokyo,
Japan, pp. 1169-1972,Apr. 1986.