【導讀】快速傅立葉變換作為時域和頻域轉換的基本運算，是數(shù)字譜分析的必要前提。傳統(tǒng)的FFT使用軟件或DSP實現(xiàn)，高速處理時實時性較難滿足。定運算時，速度會遠遠高于通用的DSP芯片。FFT運算結構相對比較簡單和固定，適。于用FPGA進行硬件實現(xiàn)，并且能兼顧速度及靈活性。本文介紹了一種通用的可以在。FPGA上實現(xiàn)32點FFT變換的方法。設計復數(shù)乘法器為核心設計了FFT算法中的基-2. 內部的雙口RAM為基礎組成了基-2FFT算法模塊。整個模塊采用基-2時域抽取,順序輸。比較仿真結果和Matlab中FFT函數(shù)產生的結果的程序,從而驗證了仿真結果的正確性。成設計的總體要求。Keywords：FPGA；FFT；IPcore;Base-2；Time-domainextracti

　　

【正文】 FT，這樣一來乘法次數(shù)將大大減少，能夠非常明顯地降低 DFT 的運算量。此外，旋轉因子 mWN具有明顯的周期性和對稱性。其周期性表現(xiàn)為： 22()j m lN j mm lN mNNNNW e e W??? ? ?? ? ? ? （ 32） 其對稱性表現(xiàn)為 m N mNNWW??? []N m mNNWW??? （ 33） 不斷的把長序列的 DFT 分解成幾個短序列的 DFT，并且利用 mWN的周期性和對稱性來減少 DFT的運算次數(shù)，這就是 FFT 算法的基本思想。比較常用的 FFT 算法有基 2 FFT和基 4FFT 兩種?；?2 FFT 中的基 2 指的是 N=2M ，即有限長序列的長度 N 要到等于 2的整數(shù)次冪 )。下 面就以 8 點的 FFT 為例詳細分析基 2 FFT 算法。 基 2 FFT 算法基本原理 基 2 FFT 算法基本上分為時域抽取法 FFT(DITFFT)和頻域抽取法 FFT(DIFFFT)兩大類。由于這兩種算法的基本原理是相同的，所以下面主要介紹 DITFFT 算法。本課題采用的就是 DITFFT這一算法。 設序列 x(n)的長度為 N，并且有以下的條件成立 2MN? ,M為自然數(shù) (34) 第 13 頁 共 38 頁 x1(r)和 x2(r)是 x(n)按 n 的奇偶性分解成的兩個 N/2 點的子序列，如下式所示 1( ) (2 )x r x r? ， 0,1, 12Nr? ??? ? (35) 2 ( ) (2 1)x r x r??， 0,1, 12Nr? ??? ? (36) 那么 x(n)的 DFT 為 ( ) ( ) ( )k n k nNNnnX k x n W x n W?????? / 2 1 / 2 12 ( 2 1 )00( 2 ) ( 2 1 )NNk r k rNNrrx r W x r W?? ?? ? ??? / 2 1 / 2 1 21200( ) ( )NNk k rNNrrx r W x r W?????? (37) 由于 22 2222 /2j k rNj k rk r k rNNNW e e W?? ??? ? ? (38) 所以 / 2 1 / 2 11 / 2 2 / 2 1 200( ) ( ) ( ) ( ) + W ( )NN k r k k r kN N N NrrX k x r W W x r W X k X k??? ? ??? (39) k =0,1,?,N 1 其中 X1(k)和 X2(k)分別為 x1(r)和 x2(r)的 N/2 點 DFT，即 / 2 11 1 / 2 10( ) ( ) [ ( ) ]N krNrX k x r W D F T x r????? (310) / 2 12 2 / 2 20( ) ( ) [ ( ) ]N krNrX k x r W D F T x r????? (311) 又由于 X1(k)和 X2(k)都是以 N/2 為周期，且 2Nk kNNWW? ?? (312) 所以 X(k)又可以表示為如下所示的表達式 12( ) ( ) ( )kNX k X k W X k?? 0,1 12Nk ? ??? ? (313) 12( ) ( ) ( )2 kNNX k X k W X k? ? ? 0,1 12Nk ? ??? ? (314) 這樣一個 N點的 DFT就被拆分成為了兩個 N/2 點的 DFT。式 (37)和式 (38)說明了原 N點的 DFT 和這兩個 N/2 點的 DFT 之間的關系 。通常為了后續(xù)說明的方便，和其它許多文獻一樣，在本文中也將式 (313)和式 (314)的運算用圖 所示的一個流圖符號表 第 14 頁 共 38 頁 示。因為這個流圖符號形狀酷似一只蝴蝶，所以稱其為蝶形運算符號。 圖 采用蝶形運算符號的這種圖示方 法，可以用圖 來表示前面所講到的運算。在圖 中， N= 32 =8，式 (313)給出了 X(0)～ X(3)的計算方法，而式 (214)給出了 X(4)～X(7)的計算方法。 圖 N點 DFT的一次時域抽取分解圖 (N=8) 由圖 ，要完成一個蝶形運算，需要一次復數(shù)乘法和兩次復數(shù)加法運算。由圖 ，經過一次分解后，計算一個 N 點 DFT 共需要計算兩個 N/2 點 DFT 和N/2 個蝶形運算。由前面的說明可以知道，計算一個 N/2 點 DFT 需要 2( /2)N 次復數(shù)乘法和 N/2(N/21)次復數(shù)加法。那么按圖 計算 N 點 DFT 共需要 22( /2)N +N/2=N(N+1)/2≈ 2N /2(N1)次復數(shù)乘法和 N(N/21)+2N/2= 2N /2 次復數(shù)加法運算。通過對比可以看出，只進行過這樣的一次分解就使得運算量減少了近一半，充分說明了這樣分解對減少DFT 的運算量是十分有效的。由于這里 N=2M ， N/2 仍然是偶數(shù)，為了使得計算量能夠得到進一步的減少，可以仿效前面的做法對 N/2 點 DFT 再做進一步分解。 與第一次分解相同， x3(l)和 x4(l)為 x1(r)按奇偶 分解成的兩個長為 N/4的子序列，即 3241( ) ( 2 ) , 0 , 1 , , 1( ) ( 2 1 ) 4x l x l Nlx l x l? ? ? ??? ????? （ 315） 那么， X1(k)又可表示為 )12( 2/14/0 12 2/14/0 11 )12()2()(????? ??? ??lkNNiklNNi WlxWlxkX 第 15 頁 共 38 頁 = klNNikNklNNi WlxWWlx 4/14/0 42/4/14/0 3 )()( ?????? ? = 12/,1,0),()( 42/3 ??? NkkXWkx kN ? (316) 其中 )]([)()(34/14/0 33 lxD F TWlxkxklNNi ?? ??? (317) )]([)()(44/14/0 44 lxD F TWlxkxklNNi ?? ??? (317) 同理，由 X3(k)和 X4(k)的周期性和 2NWm 的對稱性 /4/2 /2k N kNNWW? ?? 最后得到： 14/,1,0,)()()4/( )()()(42/3142/31 ???????? ?? NkkXWkXNkX kXWkXkX kNkN ? (319) 同理可得 14/,1,0,)()()4/( )()()(62/5262/52 ???????? ?? NkkXWkXNkX kXWkXkX kNkN ? (320) 其中有 )]([)()( 54/14/ 0 55 lxD F TWlxkX klNN i ?? ? ?? (321) )]([)()( 64/14/ 0 66 lxD F TWlxkX klNN i ?? ? ?? (322) 14/1,0,)12()( )2()(2625 ??????? ? Nllxlx lxlx ? (323) 這樣，如圖 ，經過第二次的分解，一個 N/2 點的 DFT 就被拆分成為了兩個N/4 點的 DFT 了。式 (310)和式 (311)說明了原 N/2 點的 DFT 和這兩個 N/4 點 的 DFT 之間的關系。依次類推，經過 M1 次分解，最后將 N 點 DFT 分解成 N/2 個 2 點 DFT。將前面兩次分解的過程綜合起來，就得到了一個完整的 8點 DITFFT 運算流圖，如圖 示。圖中用到關系式 /k mkN m NWW? 。圖中的輸入序列不是順序的，但是后面會看到，其排列是有規(guī)律的。 第 16 頁 共 38 頁 圖 N點 DFT的第二次時域抽取分解圖（ N=8） 圖 N點 DITFFT運算流圖（ N=8） (3)DITFFT算法與直接計算 DFT運算量的比較由 DITFFT算法的 分解過程及圖 可見， N=2M 時，其運算流圖應該有 M 級蝶形，每一級都由 N/2 蝶形運算構成。每一級運算都需要 N/2次復數(shù)乘和 N次復數(shù)加 (每個蝶形需要兩次復數(shù)加法 )。所以， M級運算總共需要的復數(shù)乘次數(shù)為 NNMNC M 2log22)2( ??? (324) 復數(shù)加次數(shù)為 NNMNC A 2lo g)2( ??? (325) 而由前面的介紹，直接計算 N點的 DFT 需要 2N 次復數(shù)乘法以及 N(N1)次復數(shù)加法運算。當 N1 時， N(N1)是約等于 2N 的。當 N=102 =1024 時，可以求得直接計算 N 點的 DFT和使用基 2 DITFFT 算法的所需乘法次數(shù)的比值為 og)2/( 22 ??NN N (326) 這樣，運算效 率就提高了 200 多倍。圖 FFT 算法與直接計算 DFT 所需乘法次數(shù)的比較曲線。由此圖更加直觀地看出 FFT 算法的優(yōu)越性，從圖 35 可以明顯的看出， 第 17 頁 共 38 頁 N越大時，優(yōu)越性就越明顯。 圖 FFT算法與直接計算 DFT所需乘法次數(shù)的比較曲線 (4)DITFFT 的一些運算規(guī)律 DITFFT 運算中是存在一些規(guī)律的，下面簡單的介紹一下這些規(guī)律。 原址計算 由圖 可以看出， DITFFT 的運算過程是很有規(guī)律的。 N=2M 點的 FFT 共需要進行進行 M級運算，每級由 N/2 個蝶形運算組成。在同一級運算中，每一個蝶形運算是有兩個輸入和兩個輸出的。這兩個輸入、輸出數(shù)據(jù)節(jié)點在同一水平線上，并且它們只對本蝶形運算有效，對其它的蝶形運算是無效的。因為這樣，當計算完一個蝶形以后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲單元。以此 類推，當 M級運算都計算完畢以后，原來存放輸入序列數(shù)據(jù)的 N 個存儲單元中便依次存放了 X(k)的 N 個值。這種利用同一存儲單元存儲蝶形運算計算輸入、輸出數(shù)據(jù)的方法就稱為原址計算。很明顯原址計算可以節(jié)省存儲資源，從而降低硬件的成本。 旋轉因子的變化規(guī)律 由 8點 DITFFT的運算流圖可以推得在 N 點 DITFFT 運算流圖中，每級都有 N/2 個蝶形。每個蝶形都要乘以因子 PNW 。 PNW 被稱為旋轉因子，其中 p為旋轉因子的指數(shù)。 通過 觀察圖 34可以推得，第 L 級共有 12L? 個不同的旋轉因子。 N=32 =8時的各級旋轉因子表示如下： 0,1 24/ ???? JWWWL JJNPN L時， (327) 1,0,2 22/ ???? JWWWL JJNPN L時， (328) 3,2,1,0,3 2 ???? JWWWL JJNPN L時， (329) 對 2MN? 的一般情況，第 L級的旋轉因子為 第 18 頁 共 38 頁 12,2,1,0, 12 ??? ?LJpN JLWW ? (330) MLMLML N ?? ???? 2222 (331) 12,2,1,0, 122 ???? ??? ?? LJNJNPN JWWW LMML ? (332) LMJP ??? 2 (333) 蝶形運算規(guī)律 設序列 x(n)經時域抽選 (倒序 )后，存入數(shù)組 X 中。如果蝶形運算的兩個輸入數(shù)據(jù)相距 B個點，應用原位計算，則蝶形運算可表示成如下形式： PNLL WBJXJXJX )()()( 11 ??? ?? (334) PNLL WBJXJXBJX )()()( 11 ???? ?? (335) 其中 MLJJp LLM ,2,1。12,1,0。2 1 ?? ????? ?? (336) 下標 L表示第 L級運算， LX (J)則表示第 L 級運算后數(shù)組元素 X(J)的 值。 序列的倒序 仔細分析可以發(fā)現(xiàn)看似毫無規(guī)律可循的 DITFFT算法的輸入序列的排序其實是很有規(guī)律的。由于 N=2M ，所以順序數(shù)可用 M 位二進制數(shù) ( 1 2 1 0...MMn n n n?? )表示。 當 N=8時，這種規(guī)律就可以用圖 和表 來表示。 圖 形成倒序的樹狀圖（ N= 32 ） 表 順序和倒序二進制數(shù)對照表 順序 倒序 十進制數(shù) I 二進制數(shù) 二進制數(shù) 十進制數(shù) J 0 000 000 1 1 001 100 4 2 010 010 2 3 011 110 6 第 19 頁 共 38 頁 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 DITFFT 的輸入順序輸出倒序的信號流圖 DITFFT 的信號流 圖的形式不是唯一的，它還有多種表現(xiàn)形式。圖 是 DITFFT的一種變形的運算流圖，其中蝶形運算的旋轉因子、運算量與圖 相同。從圖中很容易看出它是一種順序輸入，倒序輸出的方式。這種結構的信號流圖有一個非常特別的優(yōu)點就是前一級的旋轉因子剛好是后一級上一半蝶形運算的旋轉因子，且順序不變，如果旋轉因子的計算采用查表法，只要構造出一個 N/2 點的 NPW ，就可以用它來計算 N、 N/N/?長度的 FFT。因此在大型數(shù)據(jù)處理系統(tǒng)的 FFT 算法中，較多采用的是圖 所 示的流圖算法。本課題也是采用的圖 。 圖 DIT― FFT的順序輸入倒序輸出形式 4 FFT 處理器的 FPGA 的實現(xiàn) 整體設計 基 2FFT IP 核設計主要由 4 個部分組成：旋轉因子單元存儲單元、 邏輯控制單元 、雙引擎蝶 形運算單元 ，如圖 所示。 第 20 頁 共 38 頁 圖 FFT 處理器的工作過程 （ 1）當收到控制模塊發(fā)出的啟動命令后，進入正常工作狀態(tài)。這時首先啟動輸入數(shù)據(jù)單元，將原始數(shù)據(jù)存儲到雙口 RAM 中。數(shù)據(jù)存儲完畢后，進入 FFT 工作模式，對數(shù)據(jù)進行處理； （ 2）進入 FFT 工作狀態(tài)后，首先啟動控制模塊，讀取雙口 RAM 中的原始數(shù)據(jù)； （ 3） RAM 采用乒乓結構對數(shù)據(jù)進行存儲和讀取； （ 4）在進行本級蝶形運算之前，控制模塊讀取旋轉因子的實部與虛部之和、實部與虛部之差和實部。 三路數(shù)據(jù)一起輸出至蝶形運算模塊； （ 5）啟動 FFT 蝶形運算模塊，蝶形運算結果輸出； （ 6）將運算結果寫入雙口 RAM，作為下一級運算的輸入； （ 7）控制模塊產生新的地址進行第二次蝶形運算； （ 8）當最后一次蝶形運算結束后，控制模塊從 RAM 中讀出計算結果； （ 9）當一組數(shù)據(jù)處理完成之后，等待來自控制模塊發(fā)出啟動命令來進行下一組數(shù)據(jù)的處理。 由上述可以將 FFT 處理器工作的全過程分為 3 種模式：輸入模式、 FFT 模式和輸出模式。輸入模式對原始數(shù)據(jù)進行存儲， FFT 模式對數(shù)據(jù)進行 FFT 運算和緩存，輸出模式對結果進行輸出。 引腳說明 FFT 運算 RAM1 邏輯控制單元 雙引擎蝶形運算單元 旋轉因子 RAM FFT 運算 RAM2 第 21 頁 共 38 頁 圖 FFT處理 器符號圖 如圖 所示： CLK：工作時鐘輸入引腳，最高工作頻率為 153MHz，推薦工作在 150MHz。 RST: 復位引腳，低電平有效，恢復初始狀態(tài)。 Start: 啟動信號，高電平有效，至少維持 2個時鐘。第 2個時鐘開始的同時第一個有效輸入數(shù)據(jù)必須出現(xiàn)在輸入端。 In_im[15..0]：復數(shù)的虛部，位寬 16 位，但有效位不得超過 14 位。 Start 拉高的同時，必須出現(xiàn)第一個有效的虛部數(shù)據(jù)。 In_re[15..0]：復數(shù)的實部，位寬 16 位，但有效位不得超過 14 位。 Start 拉高的同時，必須出現(xiàn)第一個有效的實部數(shù)據(jù)。 Busy: 在 Start 生效之后， FFT 運算器將其拉高。表明開始一幀數(shù)據(jù)的輸入，運算與輸出。此時不能將 Start 再次拉高，只有 Busy 恢復低電平時，才能將 Start 拉高進行下一幀。 Data