本論文中，我們針對快速傅立葉演算架構中的數位計算機座標旋轉演算法提出改良型定義域摺疊式暨查表補償誤差法數位計算機座標旋轉演算法(MFE-CORDIC)與硬體架構，以較快的運算方法來做出正、餘弦函數產生器。

為尋求演算速度和記憶體使用率上的平衡，在改良型數位計算機座標旋轉演算法的主體旋轉架構中使用11級旋轉運算，將兩級合為一階，在將三階合為一單元。透過只需3次疊代就可以完成11級運算，來減少四次疊代所產生的延遲，以提升電路的速度。後級使用查表補償架構，來補償前級運算的誤差及取代後5級角度運算。在旋轉座標的起始點，我們使用一定值，減少比例因子的產生時間和起點值的運算。

在這演算法中我們主要針對面積、運算延遲時間分別提出改善之道。在電路面積使用率改進，管線及角度分解架構共使用了22個移位器、22個加法器及在查表架構的記憶體補償查表使用208位元。另外，在運算延遲的改進方面，是將起始點採用定值，所以節省產生起點值的運算時間，且將主旋體電路管線、角度分解及查表架構三者搭配使用來減少疊代次數，提升運算速度。藉由以Verilog硬體描述語言設計及ModelSim模擬其結果，再藉由Xilinx virtex-II pro FPGA 實驗板與軟體 Xilinx ISE 10.1合成電路實現驗證其可行性。透過晶片輸出腳讀取信號，以驗證電路的實際計算值。

In this paper, we introduced the design of improved Modified CORDIC Algorithm using Domain Folding and Error Lookup Table (MFE-CORDIC) and hardware architecture on FFT algorithm, to generate the sine and cosine function by that efficiency algorithm.

To reach the balance between calculating speed and memory usage, the 11 rotating operation is used in the main rotary structure of modified coordinate rotation digital computer algorithms, the two merged into one order, then combine as a unit. In this design, 11 rotating operations can be completed through 3 iteration, circuit speed can be highly improved. In last steps, using look-up table structure to compensate for the error which generated from previous operations, then replace the error of last 5 steps point operations. In addition, we set a constant value for starting point of the rotating, to reduce the production time of scale factor from the value of computing and skip the calculation time of starting point.

In the algorithm, we present improve method for both circuit area measure -ment and calculation delay. For circuit area utilization improvement, pipeline and angel decomposition structure applied only total 22 shifters, 22 adders and 208 bit (the look-up table). Second, for computing delay improvement, we set a constant value at starting point, so to save the operation time of starting value, and to reduce the number of iteration and improve processing speed by adopting circuit lines, angle decomposition, and look-up table structure.

To realize this design, we used Verilog hardware describing language for design, Modelsim for simulating the results, and Xilinx virtex-II pro FPGA test board applied with Xilinx ISE 10.1 software synthesis circuit for verifying the feasibility. Finally, by analyzing signal generated from chip, we obtain the value.

摘要
ABSTRACT
誌謝
目錄
表目錄
圖目錄
一、 簡介
1. 1 序論
1. 2 研究動機與目的
1. 3 問題描述
1. 4論文架構
二、背景與相關研究
2. 1以CORDIC實現的正、餘弦波形產生器
2.1. 1座標旋轉運算
2.1. 2 基底為二的近似定理( The Radix-2 Approximating Theorem )
2.1. 3 CORDIC架構
2. 2 Similar CORDIC-Type I 演算法
2.2. 1冗餘進位節省演算法(Redundant Carry-Save Algorithm)
2.2. 2 Similar CORDIC-Type I 架構
2. 3 Similar CORDIC-Type II 演算法
2. 4 MDF-CORDIC演算法
2. 5 MEDF-CORDIC演算法
2. 6觀念使用及缺點改正
三、所提出之演算法和硬體設計
3. 1正、餘弦產生器架構
3.1. 1定義域折疊
3.1. 2管線架構
3. 2改良型定義域摺疊式暨查表補償誤差法數位計算機座標旋轉演算法
3.2. 1角度分割與前級運算
3.2. 2後級查表補償
3. 3 MFE-CORDIC電路架構(16bit)
3. 4未來工作
3. 5 MFE-CORDIC電路架構(32bit)
3. 6各演算法架構的差異
四、模擬結果
4. 1 MFE-CORDIC 之Modelsim模擬結果
4. 2二分法補償數學模擬
4. 3 FPGA 實現
五、結論與貢獻
5. 1結論
參考文獻
附錄
附錄1：程式

[1]D. A. Sunderland, R. A. Strauch, S. S. Wharfield, H. T. Peterson, and C. R. Cole,“CMOS/SOS frequency synthesizer LSI circuitfor spread spectrum communica -tions,” IEEE J. Solid-State Circuits, vol. SC-19, pp. 497-506, Aug.1984.

[2]H. T. Nicholas, H. Samueli, and B. Kim, “The optimization of direct digital frequen -cy synthesizer performance in the presence of finite word length effects,” in Proc. 42nd Annu. Freq. Contr. Symp., Baltimore, MD, May 1988, pp. 357-363.

[3] Jacob, Applications and Design with Analog Integrated Circuits, 2nd ed., Regents / Prentice-Hall, Inc., 1993, pp. 378-396.

[4] J. Volder, “The CORDIC trigonometric computing technique,” IEEE Trans. Comput., vol. 8, pp. 330-334, 1959.

[5] S. Wang, V. Piuri, and E. E. Swartzlander, Jr., “Hybrid CORDIC algorithms,” IEEE Trans. Compu., vol. 46, no. 11, pp. 1202-1207, Nov. 1997.

[6] A.Torosyan, D. Fu, and A. N. Willson, Jr., “A 300 MHz quadrature direct digital synthesizer/mixer in 0.25 μm CMOS,” IEEE J. Solid-State Circuits, vol. 38, pp.875-887, June 2003.

[7] M. D. Ercegovac and T. Lang, “Redundant and on-line CORDIC: application to matrix triangularization and SVD,” IEEE Trans. Comput., vol. 39, pp. 725-740, June 1990.

[8] N. Takagi, T. Asada, and S. Yajima, “Redundant CORDIC methods with a constant scale factor for sine and cosine computation,” IEEE Trans. Comput., vol. 40, pp.989-995, Sept. 1991.

[9] A.Madisetti, A.Y. Kwentus, and A.N. Willson, Jr., “A 100-MHz, 16-b, direct digital frequency synthesizer with a 100-dBc spurious-free dynamic range,”IEEEJ. Solid-State Circuits, vol. 34, no. 8, pp. 1034-1043, Aug. 1999.

[10]K. Maharatna, A. Troya, M. Krsti´c, E. Grass,and U. Jagdhold,“A cordic like processor for computation of arctangent and absolute magnitude of a vector,”in Proc. 2004 IEEE Int. Symp. Circuits Syst., Vancouver, Canada, May 2004,pp.II-713-II-716.

[11]林正原，“改良型數位計算機旋轉演算法及架構設計，”雲林科技大學碩士論文，2005

[12] K. Maharatna, A.Troya, M. Krsti´c, E. Grass, and U. Jagdhold,“A cordic like processor for computation of arctangent and absolute magnitude of a vector,”in Proc. 2004 IEEE Int. Symp. Circuits Syst., Vancouver, Canada, May 2004, pp.

[13] A. M. Sodagar and G. R. Lahihi,”A novel architecture for ROM-less sine-output direct digital frequency synthesizers by using the 2nd-order parabolic approximation,” in Proc. 2000 IEEE Int. Frequency Control Symp. Exhibition, Kansas, MO,June 2000, pp. 284–289.

[14] J. C. Chih, K. L. Chen, and S.G. Chen,“A CORDIC processor with efficient table-lookup schemes for rotations and on-line scale factor compensations”, in Proc.2005 IEEE Int. Symp. Circuits Syst., Kobe, Japan, May 2005, vol. 4, pp. 3315-3318.

[15] D. D. Caro, E. Napoli, and A. G. M. Strollo, “ROM-less direct digital frequency synthesizers exploiting polynomial approximation,” in Proc. 9th Int. Conf.Electronics, Circuits Systems, Dubrovnik, Croatia, Sept. 2002, vol. 2, pp.15–18.

[16]N. Takagi, T. Asada, and S. Yajima,“Redundant CORDIC methods with a constant scale factor for sine and cosine computation,” IEEE Trans. Comput., vol. 40, pp.989-995, Sept. 1991.

[17] T. Zaidi, Q. Chaudry, and S. A. Khan, “An area and time efficient collapsed modified CORDIC DDFS architecture for high rate digital receivers,” in Proc. 2004 IEEE Int.Multitopic Conf., Lahore, Pakistan, Dec. 2004, pp. 677-681.

[18] Jacob, Applications and Design with Analog Integrated Circuits, 2nd ed., Regents Prentice-Hall, Inc., 1993, pp. 378-396.

[19] Y. H. Hu and S. Naganathan, “An angle recording method for CORDIC algorithm implementation,” IEEE Trans. Compu., vol. 42, pp. 99-102, Jan. 1993.

[20] S. W. and E. E. Swartzlander, Jr., “Merged CORDIC algorithm,” IEEE Trans. Circuits Syst., vol. 3, pp.1988-1991, May 1995.

[21] A. Madisetti, A. Y. Kwentus, and A. N. Willson, 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.

[22]S. Wu and A .Y. Wu, “Modified vector rotational CORDIC (MVR-CORDIC)algorithm and architecture,” IEEE Trans. Circuits Syst., vol.48, pp.548–561, June. 2001.

[23]C. S. Wu and A.Y. Wu,“A high-performance/low-latency vector rotational CORDIC architecture based on extended elementary angle set and trellis-based searching schemes,” IEEE Trans. Circuits Syst., vol.50, pp.589–601, Sept. 2003.

[24]C. S. Wu and A .Y. Wu,“Mixed-scaling-rotation CORDIC (MSR-CORDIC)algorithm and architecture for high-performance vector rotational DSP applications,” IEEE Trans. Circuits Syst., vol.52, pp.2385-2396, Nov. 2005.

[25]J.C.Chih and S. G. Chen,“A fast CORDIC algorithm based on a novel angle recoding scheme,” in Proc. 2000 IEEE Int. Symp. Circuits Syst., Geneva,Switzerland, May 2000, vol. 4, pp.621 – 624.

[26]J. Walther,“A unified algorithm for elementary functions,” in Proc. Spring Joint Computer Conf., 1971, pp. 379-385. II-713-II-716.