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

　　

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