【正文】 此時不能將 Start 再次拉高，只有 Busy 恢復(fù)低電平時，才能將 Start 拉高進(jìn)行下一幀。 Busy: 在 Start 生效之后， FFT 運算器將其拉高。 In_re[15..0]：復(fù)數(shù)的實部，位寬 16 位，但有效位不得超過 14 位。 In_im[15..0]：復(fù)數(shù)的虛部，位寬 16 位，但有效位不得超過 14 位。 Start: 啟動信號，高電平有效，至少維持 2個時鐘。 引腳說明 FFT 運算 RAM1 邏輯控制單元 雙引擎蝶形運算單元 旋轉(zhuǎn)因子 RAM FFT 運算 RAM2 第 21 頁 共 38 頁 圖 FFT處理 器符號圖 如圖 所示： CLK：工作時鐘輸入引腳，最高工作頻率為 153MHz，推薦工作在 150MHz。 由上述可以將 FFT 處理器工作的全過程分為 3 種模式：輸入模式、 FFT 模式和輸出模式。數(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)行本級蝶形運算之前，控制模塊讀取旋轉(zhuǎn)因子的實部與虛部之和、實部與虛部之差和實部。 第 20 頁 共 38 頁 圖 FFT 處理器的工作過程 （ 1）當(dāng)收到控制模塊發(fā)出的啟動命令后，進(jìn)入正常工作狀態(tài)。本課題也是采用的圖 。這種結(jié)構(gòu)的信號流圖有一個非常特別的優(yōu)點就是前一級的旋轉(zhuǎn)因子剛好是后一級上一半蝶形運算的旋轉(zhuǎn)因子，且順序不變，如果旋轉(zhuǎn)因子的計算采用查表法，只要構(gòu)造出一個 N/2 點的 NPW ，就可以用它來計算 N、 N/N/?長度的 FFT。圖 是 DITFFT的一種變形的運算流圖，其中蝶形運算的旋轉(zhuǎn)因子、運算量與圖 相同。 當(dāng) N=8時，這種規(guī)律就可以用圖 和表 來表示。 序列的倒序 仔細(xì)分析可以發(fā)現(xiàn)看似毫無規(guī)律可循的 DITFFT算法的輸入序列的排序其實是很有規(guī)律的。12,1,0。 N=32 =8時的各級旋轉(zhuǎn)因子表示如下： 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級的旋轉(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) 蝶形運算規(guī)律 設(shè)序列 x(n)經(jīng)時域抽選 (倒序 )后，存入數(shù)組 X 中。 PNW 被稱為旋轉(zhuǎn)因子，其中 p為旋轉(zhuǎn)因子的指數(shù)。 旋轉(zhuǎn)因子的變化規(guī)律 由 8點 DITFFT的運算流圖可以推得在 N 點 DITFFT 運算流圖中，每級都有 N/2 個蝶形。這種利用同一存儲單元存儲蝶形運算計算輸入、輸出數(shù)據(jù)的方法就稱為原址計算。因為這樣，當(dāng)計算完一個蝶形以后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲單元。在同一級運算中，每一個蝶形運算是有兩個輸入和兩個輸出的。 原址計算 由圖 可以看出， DITFFT 的運算過程是很有規(guī)律的。由此圖更加直觀地看出 FFT 算法的優(yōu)越性，從圖 35 可以明顯的看出， 第 17 頁 共 38 頁 N越大時，優(yōu)越性就越明顯。當(dāng) N=102 =1024 時，可以求得直接計算 N 點的 DFT和使用基 2 DITFFT 算法的所需乘法次數(shù)的比值為 og)2/( 22 ??NN N (326) 這樣，運算效 率就提高了 200 多倍。所以， M級運算總共需要的復(fù)數(shù)乘次數(shù)為 NNMNC M 2log22)2( ??? (324) 復(fù)數(shù)加次數(shù)為 NNMNC A 2lo g)2( ??? (325) 而由前面的介紹，直接計算 N點的 DFT 需要 2N 次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運算。 第 16 頁 共 38 頁 圖 N點 DFT的第二次時域抽取分解圖（ N=8） 圖 N點 DITFFT運算流圖（ N=8） (3)DITFFT算法與直接計算 DFT運算量的比較由 DITFFT算法的 分解過程及圖 可見， N=2M 時，其運算流圖應(yīng)該有 M 級蝶形，每一級都由 N/2 蝶形運算構(gòu)成。圖中用到關(guān)系式 /k mkN m NWW? 。依次類推，經(jīng)過 M1 次分解，最后將 N 點 DFT 分解成 N/2 個 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) 這樣，如圖 ，經(jīng)過第二次的分解，一個 N/2 點的 DFT 就被拆分成為了兩個N/4 點的 DFT 了。通過對比可以看出，只進(jìn)行過這樣的一次分解就使得運算量減少了近一半，充分說明了這樣分解對減少DFT 的運算量是十分有效的。由前面的說明可以知道，計算一個 N/2 點 DFT 需要 2( /2)N 次復(fù)數(shù)乘法和 N/2(N/21)次復(fù)數(shù)加法。 圖 N點 DFT的一次時域抽取分解圖 (N=8) 由圖 ，要完成一個蝶形運算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運算。 圖 采用蝶形運算符號的這種圖示方 法，可以用圖 來表示前面所講到的運算。通常為了后續(xù)說明的方便，和其它許多文獻(xiàn)一樣，在本文中也將式 (313)和式 (314)的運算用圖 所示的一個流圖符號表 第 14 頁 共 38 頁 示。 設(shè)序列 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)