臺灣博碩士論文加值系統

本篇論文設計符合手持數位電視系統規格的快速傅立葉轉換器，此電路採用單一路徑延遲迴授(single-path delay feedback)的管線架構。我們提出交錯時間排程的方式，並藉由改善Radix - 2演算法的實現方式，使相鄰兩階的運算得以共用同一個複數乘法器，利用率可達100%。另外我們透過系統模擬來決定表示資料所需的位元數，以達到系統的需求。而在記憶體的規畫上，採用記憶體表排序刪減法，其中主要是利用迴旋因子的週期性，刪減重覆的迴旋因子表格，使得記憶體中所需儲存的迴旋因子減為一半。
在使用CMOS 0.18μm 1P6M 製程的情況下，此快速傅立葉轉換器其核心面積為2.08 x 2.076 mm2，經過模擬驗證輸出的資料速率至少可達到50 MHz，可以符合手持數位電視系統之規格需求。

A circuit design of Fast Fourier Transform for DVB-H system is presented in this thesis. This circuit is based on SDF (single path delay feedback) pipeline architecture with radix-2 computation element. We propose a novel method of timing scheduling that can share one complex multiplier for couple of stage and promote the utilization of complex multiplier to 100%, so we can improve the implementation with radix-2 computation. The number of bits is carefully selected by system simulation to meetthe requirements of DVB-H system. In addition, a memory table permutation deletion method for memory scheduling, which can reduce the size of memory storing twiddle factors tables.
The circuit is carried out by CMOS 0.18μm 1P6M process with core area 2.08 x 2.076 mm2. In the gate level simulation, the output data rate of this circuit is above 50MHz, so the circuit can meet the requirement of DVB-H system.

目錄
誌謝 i
摘要 ii
Abstract iii
目錄 iv
圖索引 vi
表索引 viii
第一章　簡介與研究動機 1
第二章　快速傅立葉轉換演算法 3
2.1　分時、分頻快速傅立葉轉換 3
2.1.1　Radix - 2 分時快速傅立葉轉換演算法[ 1] 3
2.1.2　Radix - 2 分頻快速傅立葉轉換演算法[ 1] 5
2.2　Radix - 4 快速傅立葉轉換演算法[ 6] 8
第三章　硬體架構 11
3.1　記憶體式快速傅立葉轉換架構 11
3.2　管線式 ( pipeline ) 架構 12
3.2.1　Radix - 2 多路徑換向式架構 12
3.2.2　Radix - 2 單一路徑延遲迴授式架構 15
第四章　快速傅立葉轉換電路設計 19
4.1　迴旋因子 19
4.1.1　記憶體表排序刪減法 19
4.1.2　記憶體表排序刪減法之控制電路 21
4.1.3　三角函數特性 22
4.1.4　三角函數特性之控制電路 23
4.1.5 迴旋因子修正探討 24
4.2　時間排程設計 25
4.2.1　交錯時間排程 25
4.2.2　交錯時間排程之架構圖 31
4.2.3　交錯時間排程之修正探討 34
第五章　系統模擬與晶片設計 35
5.1　硬體需求 35
5.2　各階位元數 38
5.2.1　各階位元數探討 38
5.2.2　各階位元數模擬結果 41
5.3 晶片設計流程 47
5.3.1　Modelsim Simulation 48
5.3.2　佈局與繞線 52
5.3.3　DRC驗證 53
5.3.4　LVS驗證 54
第六章 結論 55
參考文獻 57

圖索引
圖2.1　N = 8時，DFT拆解成兩個四點的分時DFT訊號流程圖 5
圖2.2　N = 8時，分時快速傅立葉轉換訊號流程圖 5
圖2.3　RADIX - 2 分時快速傅立葉轉換蝴蝶圖 6
圖2.4　N = 8時，分時快速傅立葉轉換訊號流程圖 (化簡) 6
圖2.5　RADIX - 2 分頻快速傅立葉轉換蝴蝶圖 8
圖2.6　N = 8時，DFT拆解成兩個四點的分頻DFT訊號流程圖 8
圖2.7　N = 8時，分時快速傅立葉轉換訊號流程圖 9
圖2.8　RADIX - 4 基本蝴蝶圖 10
圖2.9　RADIX - 4 基本蝴蝶圖 (化簡) 10
圖2.10　 N = 16時，RADIX - 4快速傅立葉轉換訊號流程圖 11
圖3.1　記憶體式快速傅立葉轉換架構 12
圖3.2　RADIX - 2 MDC分頻快速傅立葉轉換架構圖 13
圖3.3　蝴蝶圖運算處理元件 13
圖3.4　四點快速傅立葉轉換蝴蝶圖 15
圖3.5　RADIX - 2 MDC分頻快速傅立葉轉換流程圖 16
圖3.6　RADIX - 2 SDF分頻快速傅立葉轉換架構圖 16
圖3.7　蝴蝶圖運算處理元件動作圖 17
圖3.8　四點快速傅立葉轉換蝴蝶圖 18
圖3.9　RADIX - 2 SDF分頻快速傅立葉轉換流程圖 19
圖4.1　記憶體位置選取圖 23
圖4.2　三角函數對應關係圖 24
圖4.3　交錯時間排程流程示意圖 (A) 28
圖4.4 交錯時間排程流程示意圖 (B) 28
圖4.5 交錯時間排程流程示意圖 (C) 28
圖4.6 交錯時間排程流程示意圖 (D) 28
圖4.7 交錯時間排程流程示意圖 (E) 28
圖4.8 交錯時間排程流程示意圖 (F) 29
圖4.9 交錯時間排程流程示意圖 (G) 29
圖4.10　SDF架構簡圖 29
圖4.11　交錯時間排程之架構圖 (前級) 32
圖4.12　交錯時間排程之架構圖 (後級) 33
圖5.1　N點快速傅立葉轉換輸入資料位元數模擬方塊圖 37
圖5.2　8192點快速傅立葉轉換，輸入定點數與SQNR對照圖 37
圖5.3　8192點快速傅立葉轉換，迴旋因子定點數與SQNR對照圖 38
圖5.4　8192點快速傅立葉轉換，迴旋因子與輸入定點數與SQNR對照圖 38
圖5.5　共用乘法器之快速傅立葉轉換方塊圖 40
圖5. 6　晶片設計流程圖 49
圖5. 7 MODELSIM SIMULATION 模擬方塊圖 50
圖5. 8 PRE-SIMULATION RESULT OF 8192 FFT 50
圖5. 9 PRE-SIMULATION RESULT OF 4096 FFT 51
圖5. 10 PRE-SIMULATION RESULT OF 2048 FFT 51
圖5. 11 GATE LEVEL SIMULATION RESULT OF 8192 FFT 51
圖5. 12 GATE LEVEL SIMULATION RESULT OF 4096 FFT 52
圖5. 13 GATE LEVEL SIMULATION RESULT OF 2048 FFT 52
圖5. 14　佈局平面圖 53
圖5. 15　LVS驗證結果 55

表索引
表1.1　各種通訊系統所需的快速傅立葉轉換點數 2
表4.1　各階旋轉因子範圍 21
表4.2　三角函數對應關係表 24
表4.3 記憶體表排序刪減法採用與否之GATE COUNT比較表 25
表4.4　交錯時間排程資料傳遞流程 (A) 29
表4.5　交錯時間排程資料傳遞流程 (B) 30
表4.6　交錯時間排程資料傳遞流程 (C) 30
表4.7　交錯時間排程資料傳遞流程 (D) 30
表4.8　交錯時間排程資料傳遞流程 (E) 31
表4.9　交錯時間排程控制訊號 34
表4.10 交錯時間排程採用與否之GATE COUNT比較表 35
表5.1　模擬結果參數說明 50
表5.2　DRC錯誤列表 54
表6.1 電路規格表 56
表6.2　快速傅立葉處理器比較表 57

[ 1 ] A. V. Oppenheim R.W. Schafer, Discrete-Time Signal Processing, Prentice- Hall, Second Edition 1999.
[ 2 ] Swartzlander, Young, Joseph, “A Radix 4 DelayCommutator for Fast Fourier Transform Processor Implementation,” IEEE J.Solid-State Circuits, Vol.SC-19, pp.702-709, Oct. 1984.
[ 3 ] T. Widhe, J. Melander, L. Wanhammar, “Design of Efficient Radix-8 Butterfly PEs for VLSI,” IEEE International Symposium on Circuits and Systems, Vol.3, pp.2084-2087, June 1997.
[ 4 ] H. Jiang, H. Luo, J. Tian, and W. Song “Design of an Efficient FFT Processor for OFDM Systems” IEEE Trans. on Consumer Electronics, pp. 1099-1103, Nov. 2005.
[ 5 ] S. He and M. Torkelson, “A new approach to pipeline FFT processor,” IEEE Int. Symp. Circuits and Systems, pp. 766-776, 1996.
[ 6 ] G.. Bi, and E. V. Jones. “A Pipelined FFT Processor for Word-Sequential Data,” IEEE Tra., Acoust, Speech, Signal Processing, pp.1982-1985, December 1989.
[ 7 ]　Y. T. Lin, P. Y. Tsai, and T. D. Chiueh, “Low-power variable-length fast Fourier transform processor”, IEE Computers and Digital Techniques, Vol.152, pp. 499-506, 2005.
[ 8 ] A. Cortes, I. Velez, J. F. Sevillano, and A. An Irizar, “Approach to simplify the design of IFFT/FFT cores for OFDM systems”, IEEE Trans. on Consumer Electronics, pp. 26-32, 2006.
[ 9 ] C. C. Wang, J. M. Huang, and H. C. Cheng, “A 2K/8K mode small-area FFT processor for OFDM demodulation of DVB-T receivers”, IEEE Trans. on Consumer Electronics, pp. 28-32, 2005.
[ 10 ] Y. Zhao, A.T. Erdogan, and T. Arslan, “A low-power and domain-specific reconfigurable FFT fabric for system-on-chip applications”, IEEE Digital Object Identifier, pp. 4-8, 2005.
[ 11 ] C.-K Chang, C.-P. Hung, and S.-G. Chen, “An efficient memory-based FFT architecture,” IEEE Int. Symp. Circuit and System, vol. 2, May 2003.
[ 12 ] S. Lee, H. Kim, and S.-C. Park, “Design of power-efficient memory-based FFT processor with new memory addressing scheme,” IEEE Conf. Commun., pp.1-5, Aug. 2006.
[ 13 ] L.R. Rabiner, B.Gold, Theory and Application of Digital Signal Processing, Prentice-Hall, 1975.
[ 14 ] L. Jia, Y. Gao, J. Isoaho, H. Tenhunen, “Efficient VLSI Implementation of Radix-8 FFT Algorithm,” Communications, Computers and Signal Processing, IEEE Pacific Rim Conference, pp.468-471, 1999.
[ 15 ] N.-H. Chang, Cell-based IC physical design and verification with SOC Encounter, National Chip Implementation Center, R.O.C., July 2005.