正交分頻多工調變（Orthogonal Frequency Division Multiplexing，OFDM）因為具有節省傳輸頻寬和抵抗符元間干擾（InterSymbol Interference，ISI）的優點，所以被普遍使用於許多新一代的通訊標準中。快速傅立葉轉換（Fast Fourier Transform，FFT）處理器是OFDM系統中的關鍵部分。為了實現出一個能適用於各種通訊標準的可變長度FFT處理器，本篇論文以記憶體式（Memory Based）架構和Mixed Radix演算法做為處理器的設計基礎。除了引用某些文獻的方法降低處理器硬體複雜度，本篇論文也修改了原先的記憶體式架構。利用交替記憶體對週邊使用權的方式達到如同管線式（Pipline）FFT處理器般的連續資料流輸出，接著提出一種資料存取策略使得FFT處理器的輸出入都是正常次序。最後進行處理器的整體效能評估，並驗證其可行性。

Orthogonal Frequency Division Multiplexing (OFDM) has been adopted in new generation communication standards because it can save transmission bandwidth and reduce InterSymbol Interference (ISI). Fast Fourier Transform (FFT) processor is the most important part in the OFDM system. In order to satisfy various kinds of communication application standards, a variable length FFT processor should be designed, Memory Based structure and Mixed Radix algorithm as the foundations of designing processor are established. In addition to low complexity hardware design technique, this thesis also modified the old kind of Memory Based architecture. We take advantage of altering memory access right to peripheral to achieve continuous data flow output like Pipelined FFT processor, and then develop a strategy for data access to ensure the sequences of the FFT processor in/output are normal order. At last we assess the entire performance of the processor, and verify its feasibility.

目　　　錄
中文摘要　-------------------------------------- I
英文摘要　--------------------------------------II
誌　　謝　-------------------------------------III
圖表索引　------------------------------------ VII
第一章　　　　緒論------------------------------ 1
　　1.1　　　 前言和研究動機-------------------- 1
　　1.2　　　 論文大綱-------------------------- 3
第二章　　　　FFT演算法------------------------- 4
2.1　　　 簡介---------------------------------- 4
2.2　　　 分頻Radix 2演算法--------------------- 5
2.3　　　 分頻Radix 4與Split Radix 2 / 4演算法-- 9
2.3.1 分頻Radix 4演算法----------------- 9
2.3.2 分頻Split Radix 2 / 4演算法------ 12
2.4　　　 分頻Radix 4與Split Radix 2 / 8演算法- 13
2.4.1 分頻Radix 8演算法---------------- 13
2.4.2 分頻Split Radix 2 / 8演算法------ 16
2.5　　　 Mixed Radix 演算法------------------- 17
2.6　　　 總結--------------------------------- 19
第三章　　　　FFT處理器架構-------------------- 21
3.1　　　 簡介--------------------------------- 21
3.1.1 複數乘法器--------------------------- 21
　3.1.2 特殊角度乘法器----------------------- 22
3.2　　　 管線式（Pipeline）FFT處理器---------- 24
3.2.1 多路徑延遲架構------------------- 24
3.2.2 單一路徑回授延遲架構------------- 27
3.2.3 效能分析--------------------------30
3.3　　　 記憶體式（Memory Based）FFT處理器---- 33
3.4　　　 總結--------------------------------- 38
第四章　　　　可變長度FFT/IFFT處理器----------- 42
4.1 簡介---------------------------------- 42
4.2 可變長度位址產生器-------------------- 43
4.2.1 資料位址產生器------------------ 44
4.2.2 係數位址產生器------------------------ 52
4.2.3 Radix 4 位址切換器-------------------- 54
4.3 Radix 4 換向器------------------------ 56
4.4 倍儲存量之唯讀記憶體----------------- 58
4.5 Radix 4蝴蝶圖單元--------------------- 58
4.6 FFT與IFFT的硬體共用------------------- 59
第五章　　　　硬體實現------------------------- 61
　　5.1　　　 處理器的設計---------------------61
5.1.1　 演算法的選擇-------------------- 61
5.1.2 Mixed Radix蝴蝶圖單元----------- 62
5.1.3 資料長度的選擇------------------ 67
5.1.4 連續資料流輸出------------------------ 70
　　5.2 Mixed Radix可變長度位址產生器--- 73
5.2.1 可變長度IO位址產生器------------ 73
5.2.2 可變長度PE位址產生器------------ 76
　　5.3 Mixed Radix換向器---------------- 79
　　5.4 控制流程------------------------- 80
　　5.5 實現結果------------------------- 84
5.5.1 驗證結果------------------------ 84
5.5.2 模擬結果------------------------ 86
第六章　　　　結論----------------------------- 88
參考文獻　------------------------------------- 89
作者簡介　------------------------------------- 91
授權書　　------------------------------------- 92

[1]　S Salivahanan and A Vallavaraj, Digital Signal Processing, McGRAW - HILL , pp.497-501（2001）
[2]　J. W. Cooley and J. W. Tukey,’’An Algorithm for Machine Computation of Comoplex Fourier Series,’’ Math. Computation, Vol. 19, pp.297-301, April 1965
[3]　L. G. Johnson,’’Conflict Free Memory Addressing for Dedicated FFT Hardward,’’IEEE Trans. Circuits and System – II: Analog and Digital Signal Processing, Vol. 39 No.5, pp.312-316, May 1992
[4] D. Cohen,’’ Simplified Control of FFT Hardware,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. ASSP-24, pp. 577-579, 1976.
[5] C. K. Chang, “Investigation and Design of FFT core for OFDM Communication Systems,” NCTU, Master Thesis, Jun. 2002.
[6] Alan V.Oppenheim, Ronald W.Schafer, “Discrete-Time Signal Processing” Prentice Hall, 1999
[7] Hsin-Fu Lo, Ming-Der Shieh, and Chien-Ming Wu, ’’Design of an Efficient FFT Processor for DAB System,’’IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 654-657, 2001
[8]　Sau-Gee Chen, Investigation and Design of FFT Core for OFDM Communication Systems, NCTU, Master Thesis, June 2001.
[9] Yutai Ma, “An Effective Memory Addressing Scheme for FFT Processors,” IEEE Transactions on Signal Processing, Vol. 47 Issue: 3, pp. 907-911, March 1999.
[10] C. H. Chang, C. L. Wang and Y. T. Chang, “Efficient VLSI Architectures for Fast Computation of the Discrete Fourier Transform and Its Inverse,” IEEE Transactions on Signal Processing, Vol. 48 Issue: 11, pp. 3206-3216, Nov. 2000.
[11] C. L. Wang and C. H. Chang, “A New Memory-Based FFT Processor for VDSL Transceivers,” IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 670 –673, 2001.
[12] G. Bi and E. V. Jones, “A Pipelined FFT Processor for Word Sequential Data,” IEEE Trans. Acoust., Speech, Signal Processing, Vol. 37 No. 12, pp. 1982-1985, Dec. 1989.
[13] R. Radhouane, P. Liu, c. Modlin, “Minimizing the Memory Requirement for Continuous Flow FFT Implementation: Continuous Flow Mixed Mode FFT (CFMM-FFT) ” Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. Vol. 1, pp. 116-119, 2000.
[14] Baek, J.H.and Son, B.S.,’’ A continuous flow mixed-radix FFT architecture with an in-place algorithm’’,IEEE Circuits and Systems, 2003. ISCAS '03. Proceedings of the 2003 International Symposium on Volume 2, 25-28 May 2003 Page(s):II-133 - II-136 vol.2
[15] B. S. Kim and L. S. Kim, “Low Power Pipelined FFT Architecture for Synthetic Aperture Radar Signal Processing,” in Proc. IEEE Midwest Symposium on Circuits and Systems, Vol.3, pp. 1367-1370, 1996.
[16] Lihong Jia, Yonghong Gao and Hannu Tenhunen, “ A Pipelined Shared-Memory Architecture for FFT Processors,” 42nd Midwest Symposium on Circuits and Systems, Vol. 2 pp. 804 –807, 2000.
[17] L. Jia, Y. Gao, H Tenhunen,” Efficient VLSI implementation of radix-8 FFT algorithm ” IEEE Pacific Rim Conference on, pp.468 – 471,Aug. 1999.
[18] A. M. Despain, “Fourier transform computer using CORDI iteration, ” IEEE Trans. Comput., Vol. C-23, pp. 993-1001, Oct . 1974.
[19] E. E. Swartzlander, W. K. W. Young, and S. J. joseph, ”A radix-4 delay commutator for Fast Fourier Transform processor implement, ” IEEE J. Solid-State Circuit, SC-19(5):702-709, Oct. 1984.
[20] E. H. Wold and A. M. Despain, “Pipeline and parallel pipeline FFT processor for VSLI implementation ”IEEE Trans. Comput., vol.C-33, pp.414-426, May 1984.