臺灣博碩士論文加值系統

在本篇論文中，我們將探討將座標旋轉(CORDIC)演算法與其在直接數位頻率合成器(DDFS)上的應用。CORDIC是一種可以利用移位器與加法器來處理旋轉運算的演算法，然而二進位的CORDIC處理器的速度瓶頸受限於加法器的進位傳遞，利用冗餘二進位(redundant binary)算術法即可改善此問題。在本論文中我們提出二個較有效率之改善架構，基本的構想是要減少角度旋轉運算的範圍以使旋轉運算級減少，然而因為旋轉範圍減小，所以還需要額外的查表器來儲存旋轉的起始點，這個構想我們以雙旋轉法與重新編碼法來實現。最後這二種改良的架構皆由Verilog硬體描述語言設計，並藉由Avant! 0.35μ標準電路單元以Synopsys合成工具合成。在原有八級的設計下移除前二級的旋轉級，分別可以節省硬體面積達30%與50%以上。在適當的路徑下使用管線式架構，使得此二種改良架構皆可在350MHz的時脈頻率下正常運作。

In this thesis, we discuss the CORDIC algorithm and its applications on the direct digital frequency synthesizer (DDFS). The CORDIC algorithm is a well-known iterative method for the vector rotation computations, which can be implemented by regular shifters and adders. However, the throughput of conventional binary arithmetic CORDIC processor is limited by the carry-propagation of the adders. Recent researches have taken advantage of the carry-free characteristic of redundant number arithmetic to speed up CORDIC operations. In this thesis, we propose two efficient redundant CORDIC algorithms. Our idea is to reduce the angle rotation range such that the number of processing stage can be reduced. Since the rotation range is reduced, multiple initial vectors are required, which are stored in a lookup table. This idea is then realized using the double rotation and recoding CORDIC algorithms. Finally, the two proposed architectures are designed by Verilog hardware description language, and then synthesized by Synopsys Design Complier using Avant! 0.35μm standard cell library. Removing two stages from original designed eight-stage-CORDIC, we can reduce the hardware area more than 30% and 50%, respectively. Both architectures can be operated in 350MHz clock frequency using appropriate data-path pipelining.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 簡介 1
第二章 座標旋轉演算法 6
2.1 二進位座標旋轉演算法 6
2.2 二進位冗餘算術之座標旋轉演算法 10
2.2.1 二進位冗餘算術法 10
2.2.2 Redundant座標旋轉演算法 18
第三章 DDFS改進方式之提案 22
3.1 改進方法一：DDFS6 23
3.2 改進方法二：DDFS6_rec 26
第四章 DDFS之架構與實現 32
4.1 DDFS之整體架構 32
4.1.1 二進位CORDIC 32
4.1.2 Redundant CORDIC之雙旋轉法 34
4.1.3 改良方法一 (DDFS6) 36
4.1.4 改良方法二 (DDFS6_rec) 38
4.2 DDFS之細部元件 40
4.2.1 有限狀態機 40
4.2.2 查表器 43
4.2.3 二進位數值-RB數值轉換器 45
4.2.4 RB數值比較器 45
4.2.5 旋轉運算級 46
4.2.6 弦波轉換處理器 51
4.2.7 RB數值-二進位數值轉換器 54
4.3 DDFS設計之模擬 55
4.4 DDFS各設計之效能比較 56
第五章 結論 59
參考文獻 60
自傳 63

參考文獻：
[1] J. E. Volder, “The CORDIC trigonometric computing technique,” IRE Trans. Electron. Comput., vol. EC-8, pp.330-334, Sept. 1959.
[2] J.S. Walther, “A Unified Algorithm for Elementary Functions,” AFIPS Spring Joint Computer Conf., vol. 38, pp.379-385, 1971.
[3] Y.H. Hu, “CORDIC-based VLSI architectures for digital signal processing,” IEEE Signal Processing Magazine, pp.16-35, Jul.1992.
[3] S. Note, J. van Meerbergen, F. Catthoor, and H. de Man, “Automated Synthesis of a High Speed CORDIC Algorithm with Cathedral-III Compilation System,” Proc. IEEE ISCAS ’88, pp.581-584, 1988.
[4] J.R. Cavallaro and F.T. Luk, “Floating Point CORDIC for Matrix Computations,” Proc. IEEE Int’l Conf. Computer Design, pp.40-42,1988.
[5] A.A. de Lange, A.J. van der Hoeven, E.F. Deprettere, and J. Bu, “An Optimal Floating-Point Pipeline CMOS CORDIC Processor,” Proc. IEEE ISCAS ’88, pp.2043-2047, 1988.
[6] M.D. Ercegovac and T. Lang, “Redundant and On-Line CORDIC: Application to Matrix Triangularisation and SVD,” IEEE Trans. Computers, vol. 38, no.6, pp.725-740, June 1990.
[7] M.D. Ercegovac and T. Lang, “Implementation of Fast Angle Calculation and Rotation Using On-Line CORDIC,” Proc. IEEE ISCAS ’88, pp.2703-2706, 1988.
[8] T. Noll, “Carry-Save Architectures for High-Speed Digital Signal Processing,” J. VLSI Signal Processing, vol. 3, pp.121-140, June 1991.
[9] R. Künemund, H. Söldner, S. Wohlleben, and T. Noll, “CORDIC Processor with Carry-Save Architecture,” Proc. ESSCIRC ’90, pp. 193-196, 1990.
[10] N. Takagi, T. Asada, and S. Yajima, “A hardware Algorithm for Computing Sine and Cosine Using Redundant Binary Representation,” Systems and Computers in Japan, vol.18, no.8, pp.1-9, Aug. 1987.
[11] N. Takagi, T. Asada, and S. Yajima, “Redundant CORDIC Methods with a Constant Scale Factor for Sine and Cosine Computation,” IEEE Trans. Computers, vol .40, no.9, pp.989-995, Sept. 1991.
[12] H.X. Lin and H.J. Sips, “On-Line CORDIC Algorithms,” IEEE Trans. Computers, vol.38, no.8 ,pp.1038-1052, Aug. 1990.
[13] T. Noll, “Carry-Save Arithmetic for High-Speed Digital Signal Processing,” Proc. IEEE ISCAS ’90, vol.2, pp. 982-986, 1990.
[14] H. Yoshimura, T. Nakanishi, and H. Yamauchi, “A 50 MHz CMOS Geometrical Mapping Processor,” IEEE Trans. Circuits and Systems, vol. 36, no. 10, pp. 1360-1363, 1989.
[15] D. Cochran, “Algorithms and Accuracy in the HP-35,” Hewlett-Packard Journal, pp.10-11, Jun. 1992.
[16] J. Vankka, M. Kousunen, J. Hubach, and K. Halonen, “A CORDIC-based multicarrier QAM modulator,” Global Telecomm. Conf. ’99, vol. 1a, pp. 173-177, 1999.
[17] J. Vankka, M. Kousunen, I. Sanchis, and K.A.I. Halonen, “A multicarrier QAM modulator,” IEEE Trans. Circuits and Systems II, vol.47, pp. 1-10, Jan. 2000.
[18] J. Tierney, C. M. Rader, and B. Gold, “A digital frequency synthesizer,” IEEE Trans. Audio Electroacoust., vol. AU-19, pp. 48-56, Mar. 1971.
[19] H. T. Nicholas and H. Samueli, “ A 150 MHz direct digital frequency synthesizer in 1.25μm CMOS with —90 dBc spurious performance,” IEEE J. Solid-State Circuits, vol. 26, pp. 1959-1969, Dec. 1991.
[20] S. Nahm, K. Han, and W. Sung, “A CORDIC-based digital quadrature mixer: comparison with a ROM-based architecture,” IEEE ISCAS ’98, vol.4, pp. 385-388, 1998.
[21] M. Park, K. KIM, and J. Lee, “CORDIC-based direct digital frequency synthesizer: Comparison with a ROM-based architecture in FPGA Implementation,” IEICE Trans. Fundamentals, vol. E83-A, No.6, June 2000.
[22] K. K. Parhi, “VLSI digital signal processing systems — design and implementaion,” John Wiley & Sons, Inc., ch.14, pp.529-557, 1999.
[23] A. Madisetti, A.Y. Kwentus, and A.N. Willsion, Jr., “A 100-MHz, 16-b, Direct Digital Frequency Synthesizer with a 100-dBc Spurious-Free Dynamic Range,” IEEE J. Solid-State Circuits, vol.34, No.8, pp. 1034-1043, Aug. 1999.
[24] Y.H. Hu and S. Naganathan, “An angle recording method for CORDIC algorithm implementation,” IEEE Trans. Computers, vol.42, pp.99-102, Jan. 1993.
[25] I. Janiszewski, B. Hoppe and H. Meuth, “Precision and performance of numerically controlled oscillators with hybrid function generators,” IEEE int’l Frequency Control Symposium and PDA Exhibition, pp.744-752, 2001.