臺灣博碩士論文加值系統

由於通訊系統有線與無線資料傳輸需求，傅立葉轉換仍是通訊信號處理的研究與發展重點之一。在即時訊號處理系統中，加速離散傅立葉轉換(Discrete Fourier Transform, DFT)的運算速度是非常重要的，因此發展出許多種類的快速傅立葉轉換的演算法，並由於其演算法的規則性，使得快速傅立葉(fast Fourier Transform, FFT )演算法非常適合在硬體電路中實現。各種演算法的主要目的為降低傅立葉轉換電路中的計算複雜度，以本論文所使用的Radix-22演算法為例，其計算的複雜度從O(N2)減少至O(NlogN)。
本論文研究中，我們比較各種快速傅利葉轉換電路(fast Fourier Transform, FFT) 演算法架構之硬體運算單元規則性、所需記憶體及運算次數等優缺點，最後採用 Radix-22演算法及單一路徑回授(Single-path Delay Feedback, SDF)架構實現一高效率之快速傅立葉轉換電路。電路實現上，使用了傳統複數乘法器、標準符號格式(Canonical Signed Digit, CSD)複數乘法器與座標軸旋轉數位計算器(Coordinate Rotation Digital Computer, Cordic)架構來分別實現快速傅立葉轉換之電路，並運用了四捨六入五成雙近似的方式去降低電路的誤差。最後並使用ISE軟體進行硬體設計與模擬，將其模擬結果與理想上計算結果加以比較，證明在取樣點數為16點之情況下，使用標準符號格式複數乘法器所實現的快速傅立葉運算電路具有低使用面積與適度精確度的優點。

Due to the popularity of the communication systems, the Fourier transform is still one of research and development topics of wired and wireless communication. The high-speed computing of the discrete Fourier transform is very important in the real-time signal processing system. So many fast Fourier transform (FFT) algorithm are developed. Because of the regularity of FFT algorithm, it is very suitable for the implementation by using hardware circuits. Most of the developed algorithms reduce the computational complexity. In this thesis, we use radix-22 algorithm which can reduce the computational complexity from to .
In this study, we compare various circuit architectures of fast Fourier transform in the view of hardware regularity, needed memory space and the number of computing operation. Finally, we adopt the radix-22 algorithm and the single-path delay feedback (SDF) architecture to implement the high-performance FFT processor. The conventional complex multiplier, multiplier-less canonical signed digit (CSD) complex multiplier and coordinate rotation digital computer (Cordic) architecture are used to realize pipelined fast Fourier transform processors. To reduce the error, we also realize our complex multiplier computing circuits with the double rounding technique. The Xilinx ISE software is used to synthesis the hardware, it shows that the 16-point FFT processor based on the multiplier-less canonical signed digit (CSD) complex multiplier can achieve the advantages of less needed hardware and moderate accuracy.

摘 要 I
Abstract II
致謝 III
目 錄 IV
圖目錄 VI
Chapter 1 緒論 1
1.1 前言 1
1.2 研究動機 2
1.3 論文架構 2
Chapter 2 快速傅立葉演算法 3
2.1 前言 3
2.2 雙轉子因子(Twiddle Factor) 3
2.3 FFT演算法 6
2.3.1 Decimation-in Frequency Radix-2演算法 6
2.3.2 Decimation-in Time Radix-2演算法 10
2.3.3 Radix-4 演算法 12
2.3.4 Radix-22演算法 16
2.3.5 Radix-2/4演算法 19
2.4 各種演算法之差異 20
Chapter 3 快速傅立葉轉換處理器架構 22
3.1 概論 22
3.1.1 垂直投影架構原理 22
3.1.2 水平投影架構原理 23
3.2 管線式架構 24
3.2.1 Radix-2 Multi-Path Delay Commutator (MDC) 24
3.2.2 Radix-4 Multi-Path Delay Commutator (MDC) 25
3.2.3 Radix-2 Single-Path Delay Feedback(SDF) 26
3.2.4 Radix-4 Single-Path Delay Feedback(SDF) 26
3.2.5 Radix-22 Single-Path Delay Feedback(SDF) 27
3.3 各種Pipelined架構之比較 28
Chapter 4 快速傅立葉電路設計 30
4.1 電路簡介 30
4.2 複數乘法器 31
4.2.1 傳統複數乘法器 31
4.2.2 CSD複數乘法器 34
4.2.3 座標軸數位旋轉計算器CORDIC 38
4.3 蝴蝶運算器 43
4.4 控制電路單元 45
4.5 內建記憶體 47
Chapter 5 快速傅立葉轉換處理器硬體電路 48
5.1 系統設計流程 48
5.2 電路合成與模擬 48
5.2.1 複數乘法器 48
5.2.2 CSD複數乘法器 50
5.2.3 Cordic 51
5.2.4 FFT模擬結果 54
5.3 電路port腳定義與資料寬度 58
5.4 相關電路比較與整體面積 59
Chapter 6 結論與未來展望 64
參考文獻 65

[1]V. Nee, R. Prasad, “OFDM Wireless Multimedia Communications”, Artech House, Boston, 2000.
[2]C. Lin, Y. Yu, and L. Van, “A low-power 64-point FFT/IFFT design for IEEE802.11a WLAN application” in Proc. International Symposium on circuit and systems, pp.4523-4526, 2006..
[3]J. Mar, Y. Lin, T. Lung, and T. Wei, “Realization of OFDM Midulator and Demodulator for DSRC Vehicular Communication System Using FPGA Chip,” International Symposium on Intelligent Signal Processing and Communications (ISPACS’06), pp.477-480, 2006.
[4]J. K. Cooley and J. W. Tuley, “An algorithm for the machine calculation of complex Fourier series.” Math. Comput. , Vol. 19, pp. 297-301 Feb.1965.
[5]U. Meyer-Baese, “Digital Signal Processing with Field Programmable Gate Arrays,” Springer Publication, pp. 344-386.
[6]V. Szwarc and L. Desormeaux. “A Chip Set for Pipeline and Parallel Pipeline FFT Architectures”, Joural of VLSI Signal Processing, vol.8, pp 253-256, 1994.
[7]S. Sukhsawas and K. Benkrid, “A high-level implement of a high performance pipeline FFT on Virtex-E FPGAs”, in Processdings of the IEEE Computer Society Annual Symosium on VLSI(ISVLSI’04), pp.229-231, Feb. 2004.
[8]B. Zhou, Y. Peng and D. Hwang, “Pipeline FFT architectures Optimized for FPGAs”, International Journal of Reconfigurable Computing. Volume 2009, Jube 2009.
[9]K. K. Parhi, “VLSI Digital Signal Processing Systems, Design and Implementation,” Wiley Interscience Publication, pp.505-511.
[10]E. E Ngu, K. Ramar, R. Montano and V. Vooray “Fault characterization and classification using wavelet and Fast Fourier Transform,” WSEAS transaction on signal processing, Volume 4, Issue 7, pp. 398-408, July 2008.
[11]S. He and M. Torkelson, “A new approach to pipeline FFT processor,” in Proc. 10th International Parallel Processing Symp., pp. 766-770, 1996.
[12]M. Nilsson, “FFT, Realization and Implementaion in FPGA,” Master thesis, Ericsson Microwave Sysetms AB / Griffith University, 2000-2001.
[13]Z. Sun, X. Liu, and Z. Ji, “The Design of Radix-4 FFT by FPGA,” International Symposium on Intelligent Information Techonlogy Application Workshops, pp765-768, 2008.
[14]L. R. Rabiner and B. Gold, “Theory and Application of Digital Signal Processing”, Prentice-Hall, Inc, New Jersey, 1975.
[15]E. H. Wold and A. M. Despain, “Pipeline and Parallel-Pipeline FFT processors for VLSI Implementation,” IEEE Transactions on Computers, Vol.33, NO. 5, pp.414-426 May 1984.
[16]A. M. Despain, “Fourier Transform Computer Using CORDIC iterations,” IEEE Transactions on Computers, Vol. 23, NO. 10, pp.993-1001, Oct. 1974.
[17]G. Jesus, J. A. Michell, G. Ruiz, and A. M. Buron, “FPGA realization of a Split Radix FFT processor,” Proc. of SPIE Microtechnologies for the New Millennium. vol. 6590, pp.65900P-1 to 65900P-11, 2007.
[18]S. W. Reitwiesner, “Binary arithmetic,” Advances in Computer, pp.231-308, 1996..
[19]M. Benhamid, and M. Othman, “FPGA implementation of a canonical signed digit multiplier-less based FFT processor for wireless communication applications,” IEEE international Conference on Semiconductor Electronics, ICSE2006, pp.641-645, 2006.
[20]M. B. Othman and M. Benhamid, “Hardware Implementation of a Genetic Algorithm Based Canonical Singed Digit Multiplierless Fast Fourier Transform Processor for Multiband Orthogonal Frequency Division Multiplexing Ultra Wideband Applications,” Journal of Mathematics and Statistics, Vol.5, pp.241-250, 2009.
[21]R. Prasanthi, V. Anuradha, S. K. Sahoo and C. Shekhar, “Multiplier Less FFT Processor Architecture for Signal and Image Processing,” International Conference on Intelligent Sensing and Information, pp.326-330, 2005.
[22]Y. Zhou, J. M. Noras and S. J. Shepherd, “Novel design of multiplier-less FFT processors,” Signal Processing, 87, pp. 1402-1407,2007.
[23]J. E Volder, “The CORDIC Trigonometric Computing Technique,” IRE Trans. Electon.Comput., vol. EC-8, no.3, pp. 330-334, Spet. 1959.
[24]C. S. Wu, A. Y. Wu, and C. H. Lin, “A high-performance/low-latency vector rotational CORDIC architecture2/ based on extened elementary angle set and trellis-based searching schemes,” IEEE Transactions on Circuits System. II, Analog Digit. Signal Process, vol. 50, no.9, pp. 589-601, Sep. 2003.
[25]J. C. Chih and S. G. Chen, “A fast CORDIC algorithm based on a novel angle recoding scheme,” in Proc. IEEE Int. Symp. Circuits Syst., vol 4, pp.621-624, 2000.
[26]謝昭和、郭忠明與楊乃中，訊號與系統Signals, Systems, and Transforms，第三版，2004。