【文章內(nèi)容簡介】 Ni ?? ??? (218) 同理，由 X3(k)和 X4(k)的周期性和 2NWm 的對(duì)稱性 /4/2 /2k N kNNWW? ?? 最后得到： 基于 FPGA的 FFT算法實(shí)現(xiàn) 第 6 頁 共 41 頁 14/,1,0,)()()4/( )()()(42/3142/31 ???????? ?? NkkXWkXNkX kXWkXkX kNkN ? (219) 同理可得 14/,1,0,)()()4/( )()()(62/5262/52 ???????? ?? NkkXWkXNkX kXWkXkX kNkN ? (220) 其中有 )]([)()( 54/14/ 0 55 lxD F TWlxkX klNN i ?? ? ?? (221) )]([)()( 64/14/ 0 66 lxD F TWlxkX klNN i ?? ? ?? (222) 14/1,0,)12()( )2()( 26 25 ??????? ? Nllxlx lxlx ? (223) 這樣，如圖 ，經(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? 。圖中的輸入序列不是順序的，但是后面會(huì)看到，其排列是有規(guī)律的。 圖 N 點(diǎn) DFT 的第二次時(shí)域抽取分解圖（ N=8） 基于 FPGA的 FFT算法實(shí)現(xiàn) 第 7 頁 共 41 頁 圖 N點(diǎn) DITFFT運(yùn)算流圖（ N=8） (3)DITFFT算法與直接計(jì)算 DFT運(yùn)算量的比較由 DITFFT算法的分解過程及圖 ， N=2M時(shí)，其運(yùn)算流圖應(yīng)該有 M級(jí)蝶形，每一級(jí)都由 N/2 蝶形運(yùn)算構(gòu)成。每一級(jí)運(yùn)算都需要 N/2次復(fù)數(shù)乘和 N次復(fù)數(shù)加 (每個(gè)蝶形需要兩次復(fù)數(shù)加法 )。所以， M級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為 NNMNC M 2lo g22)2( ??? (224) 復(fù)數(shù)加次數(shù)為 NNMNC A 2lo g)2( ??? (225) 而由前面的介紹，直接計(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ù)的比值為 2020 4857 6log)2/( 22 ??NN N (226) 這樣，運(yùn)算效率就提高了 200 多倍。圖 FFT 算法與直接計(jì)算 DFT所需乘法次數(shù)的比較曲線。由此圖更加直觀地看出 FFT 算法的優(yōu)越性，從圖 35 可以明顯的看出， N 越大時(shí)，優(yōu)越性就越明顯。 圖 FFT 算法與 直接計(jì)算 DFT 所需乘法次數(shù)的比較曲線 基于 FPGA的 FFT算法實(shí)現(xiàn) 第 8 頁 共 41 頁 基 4FFT算法原理 在 FFT各類算法中，基 2FFT算法是最簡單的一種，但其運(yùn)算量與基 4FFT算法相比則大得多，分裂基算法綜合了基 4和 基 2算法的特點(diǎn)，雖然具有最少的復(fù)乘運(yùn)算量，但其 L蝶形運(yùn)算控制的復(fù)雜性也限制了其在硬件上的實(shí)現(xiàn)，因此，本設(shè)計(jì)采用了基 4FFT算法結(jié)構(gòu)。 基 4FFT算法的基本運(yùn)算是 4點(diǎn) DFT。一個(gè) 4點(diǎn)的 DFT運(yùn)算的表達(dá)式為： ???????????????????????????????????????????????030200)3()2()1()0(111111111111)3(39。)1(39。)2(39。)0(39。KNkNKNNWXWXWXWXjjjjXXXX 式 (1)對(duì)于輸出變量進(jìn)行了二進(jìn)制倒序，便于在運(yùn)算過程中進(jìn)行同址運(yùn)算，節(jié)省了運(yùn)算過程中所需存儲(chǔ)器單元的數(shù)量。 按 DIT(時(shí)間抽取 )的 1 024 點(diǎn)的基 4FFT共需 5 級(jí)蝶形運(yùn)算，每級(jí)從 RAM 中讀取的數(shù)據(jù)經(jīng)過蝶形運(yùn)算后原址存入存儲(chǔ)單元準(zhǔn)備下一級(jí)運(yùn)算。算法的第 1 級(jí)為一組 N=1024 點(diǎn)的基 4 蝶形運(yùn)算，共256個(gè)蝶形，每個(gè)蝶形的距離為 256點(diǎn)；第 2級(jí)為 4組 N=256點(diǎn)的基 4蝶形運(yùn)算，每組 64個(gè)蝶形，每個(gè)蝶形的距離為 64點(diǎn)。后 3級(jí)類推。這種算法每一級(jí) 的運(yùn)算具有相對(duì)獨(dú)立性，每級(jí)運(yùn)算都采用同址運(yùn)算，因此，本設(shè)計(jì)只使用了 2個(gè) 1 k 16 bits的 RAM單元。運(yùn)算過程中所需的旋轉(zhuǎn)因子的值經(jīng)過查詢預(yù)設(shè)的正弦與余弦 ROM表得到。 IP 核實(shí)現(xiàn)原理 1) FFT兆核函數(shù)功能描述 長度為 N 的離散傅里葉變換 (DFT)是計(jì)算單位圓上 N 點(diǎn)均勻分布的離散時(shí)間序列（ w=2πk=0， ...NI）的采樣傅里葉變換。 序列 r(n)的 N點(diǎn) DFT如下所示： 1. . . .1,0)()( /)22(10 ??? ??? NkenxakX NpnkjNn (227) N點(diǎn) IDFT如下所示： 1. . . . . . ,1,0][1)( /210 ??? ?? NnekXaNnx NpnkjNk (228) DFT 直接計(jì)算的復(fù)雜性可以通過快速傅里葉變換 (FFT)算法大大降低。 FFT 算法可基于式 ( 51)和式 (52)中求和運(yùn)算的嵌套分解以及復(fù)數(shù)乘法的對(duì)稱性來實(shí)現(xiàn)。其中一類 FFT 算法為庫利 圖基( CooleyTukey)基 r 按頻率抽選（ Decimationin Frequency，縮寫 DIF）法將輸入序列循環(huán)分解為 N/r個(gè)長度為 r的序列，并需要 Nlogr級(jí)運(yùn)算。 每一級(jí)分解由同一個(gè)硬件單元完成，包括數(shù)據(jù)從 存儲(chǔ)器中抽取、通過 FFT 處理器以及入存儲(chǔ)器的過程。每次通過 FFT 處理器都要完成 Nlogr次運(yùn)算。通常基數(shù) r 選擇 4 和 16， ,增加分解基數(shù)r，可以通過犧牲硬件的資源來減少 FFT 處理器的運(yùn)算次數(shù)。 基于 FPGA的 FFT算法實(shí)現(xiàn) 第 9 頁 共 41 頁 將輸入序列循環(huán)分解為 4點(diǎn)序列的基 4分解，使用 4點(diǎn) FFT在乘法運(yùn)算上具有更大優(yōu)勢(shì)， Altera公司的 FFT兆核選用的就是基 4運(yùn)算，在 N是 2的奇數(shù)冪的情況下， FFT IP核，自動(dòng)在完成轉(zhuǎn)換的最后使用基 2運(yùn)算。 為了在整個(gè)轉(zhuǎn)換計(jì)算過程中保持高信噪比 (SNR)， FFT 兆核函 數(shù)采用塊浮點(diǎn) (Block floatingpoint)結(jié)構(gòu)，這種結(jié)構(gòu)是定點(diǎn) (Fixedpoint)與全浮點(diǎn) (Fullfloatingpoint)結(jié)構(gòu)之 M平衡 在塊浮點(diǎn)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)模塊中所有的數(shù)值都有一個(gè)獨(dú)立的尾數(shù)，但共享一個(gè)公共的指數(shù)，輸入到 FFT函數(shù)的數(shù)據(jù)作為定點(diǎn)復(fù)數(shù)。 塊浮點(diǎn)結(jié)構(gòu)保證了在 FFT 函數(shù)和整個(gè)轉(zhuǎn)換過程中數(shù)據(jù)位數(shù)的完整使用。每次通過基 4FFT 運(yùn)算以后，數(shù)據(jù)位數(shù)最大可能增加縮位，根據(jù)前面輸出數(shù)據(jù)模塊動(dòng)態(tài)范圍的測(cè)量按比例進(jìn)行運(yùn)算，換算過程中累計(jì)的移位次數(shù)被作為整個(gè)模塊的指數(shù)輸出。這種移 位方法保證最低位 (LSB)的最小值在乘法運(yùn)算后的輸出進(jìn)行舍入操作之前就被丟棄。實(shí)際上，塊浮點(diǎn)表示法起到了數(shù)字自動(dòng)增益控制的作用。為了在連續(xù)輸出模塊中產(chǎn)生統(tǒng)一的比例，必須用最終的指數(shù)對(duì) FFT函數(shù)輸出進(jìn)行比例換算。 2) FFT處理器引擎結(jié)構(gòu) FFT 兆核函數(shù)可以通過定制參數(shù)來使用兩種不同的引擎結(jié)構(gòu)：四輸出 (Quadoutput)或單輸出( Quadoutput)引擎結(jié)構(gòu)。為了增加 FFT兆核函數(shù)的總吞吐量，也可以在一個(gè) FFT 兆核函數(shù)變量中使用多個(gè)并行引擎。 (1)四輸出 FFT 引擎結(jié)構(gòu) 對(duì)于需要最少轉(zhuǎn)換時(shí) 間的應(yīng)用，四輸出 FFT 引擎結(jié)構(gòu)是最佳選擇。四輸出 (Quadoutput)指的是內(nèi)部 FFT 蝶形處理器的吞吐量，這種引擎實(shí)現(xiàn)結(jié)構(gòu)可以在一個(gè)單時(shí)鐘周期內(nèi)計(jì)算所有四個(gè)基 4 蝶形復(fù)數(shù)輸出。四輸出引擎結(jié)構(gòu)的構(gòu)圖如圖 。 復(fù)數(shù)采樣數(shù)據(jù) x[k， m]從內(nèi)部存儲(chǔ)器并行讀出，并由變換開關(guān) (SW)重新排序’排序后的取樣 數(shù)據(jù)由基 4處理器處理并得到復(fù)數(shù)輸出 G[k， m]，由于基 4按頻率抽選 (DIF)分解方法固有的數(shù)字特點(diǎn)，在蝶形處理器輸出上僅需要 3 個(gè)復(fù)數(shù)乘法器完成 3 次乘旋轉(zhuǎn)因子（有一個(gè)旋轉(zhuǎn)因予為 1，不需要乘）計(jì)算。為了辨別采 樣數(shù)據(jù)的最大動(dòng)態(tài)范圍， 4 個(gè)輸出由塊浮點(diǎn)單元 (BFPU)并行估計(jì)，丟棄適當(dāng)?shù)淖畹臀?(LSB)，在寫入內(nèi)部存儲(chǔ)器之前對(duì)復(fù)數(shù)值進(jìn)行四舍五人并重新排序。 圖 四輸出 F 訂引擎結(jié)構(gòu) (2)單輸出 FFT引擎結(jié)構(gòu) 在需要最小尺寸 FFT 函數(shù)的應(yīng)用中，單輸出引擎最適合。單輸出也指的是內(nèi)部 FFT 蝶形處理器的吞吐量。在這種引擎結(jié)構(gòu)中，每個(gè)時(shí)鐘周期計(jì)算一個(gè)單蝶形輸出，需要一個(gè)單獨(dú)的復(fù)數(shù)乘法器，其引擎結(jié)構(gòu)如圖 。 基于 FPGA的 FFT算法實(shí)現(xiàn) 第 10 頁 共 41 頁 R A MR A MB F P UX [ k , 0 ]X [ k , 1 ]X [ k , 2 ]X [ k , 3 ]G [ k , 0 ]G [ k , 1 ]G [ k , 2 ]G [ k , 3 ]R O MH [ k , m ]F F T E n g i n e 圖 單輸出 FFT 引擎結(jié)構(gòu) (3) FFT兆核 I/O數(shù)據(jù)流結(jié)構(gòu) FFT 兆核函數(shù)支持的 I/O 數(shù)據(jù)流包括：流 (Streaming)、緩沖突發(fā) (Buffered Burst)和突發(fā)(Burst)。 1)流 (Streaming)I/0數(shù)據(jù)流結(jié)構(gòu) 流 I/O數(shù)據(jù)流結(jié)構(gòu)允許輸入數(shù)據(jù)連續(xù)處理，并輸出連續(xù)的復(fù)數(shù)據(jù)流，這個(gè)過程中不需要停止 FFT數(shù)據(jù)流進(jìn)出。這種數(shù)據(jù)流結(jié)構(gòu)的仿真結(jié)果如圖 。 FFT兆核函數(shù)采用 Altera Atlantic接口I/O協(xié)議，輸入接口為主設(shè)備匯端 (MasterSink)．而輸出接口為主設(shè)備源端 (Master Source)。 圖 FFT streaming 數(shù)據(jù)流仿真結(jié)果 在系統(tǒng)復(fù)位信號(hào) ( Reset)變?yōu)榈碗娖胶螅瑪?shù)據(jù)源將 master— sink— dav 信號(hào)置為高電平，對(duì)于FFT函數(shù)束說這表明在輸入端至少有 N個(gè)復(fù)數(shù)據(jù)樣點(diǎn)可以輸入。作為回應(yīng)， FFT函數(shù)將 Masterink_ena信號(hào)置為高電平，表明有能力接收這些輸人信哆。數(shù)據(jù)源加載第一個(gè)復(fù)數(shù)據(jù)樣點(diǎn)到 FFT 函數(shù)中，同時(shí)將 master_sink_sop信號(hào)置為高電平，表示輸入模塊的開始。在下一時(shí)鐘周期， master_sink_sop信號(hào)被復(fù)位，并以 自然順序加載數(shù)據(jù)樣點(diǎn)。如圖 ，圖中z，（ n）表示輸入復(fù)數(shù)據(jù)實(shí)部， z．（ n）表示輸入復(fù)數(shù)據(jù)虛部。 基于 FPGA的 FFT算法實(shí)現(xiàn) 第 11 頁 共 41 頁 圖 FFT Streaming 數(shù)據(jù)流結(jié)構(gòu)輸入流程控制時(shí)序 在 streaming數(shù)據(jù)流結(jié)構(gòu)中， FFT函數(shù)希望輸入端的輸人數(shù)據(jù)連續(xù)可用，因此， mastersink_ena會(huì)一直保持高電平，除非系統(tǒng)復(fù)位，或 master_sink_dav 信號(hào)復(fù)位顯示輸人數(shù)據(jù)模塊完整，或由于master _sink_sop信號(hào)置高電平失敗， master_sink_ena信號(hào)才復(fù)位。 如果要在一個(gè)輸入模塊的邊界上停止模塊數(shù)據(jù)流， master_sink_sop信號(hào)將在前一模塊后數(shù)據(jù)樣點(diǎn)輸入以后保持低電平。 FFT函數(shù)復(fù)位 master_sink_ena信號(hào)，并繼續(xù)處理已入的數(shù)據(jù)模塊。 FFT函數(shù)中的流水線已經(jīng)清除以后， master_sink_ena 重新置為高電平，在下一個(gè)輸入模塊流的第一個(gè)輸入數(shù)據(jù)樣點(diǎn)上置位 master_sink_sop信號(hào)來對(duì)下一個(gè)輸塊的讀取進(jìn)行初始化。 當(dāng) FFT 已經(jīng)完成了輸入模塊的變換，并且從設(shè)備匯端 (Slave Sink)將 master_source— dav 號(hào)置高 電平（表示數(shù)據(jù)從設(shè)備接收器可以接收輸出數(shù)據(jù)模塊）時(shí)， FFT 將 master— source— ena 號(hào)置高電平，并且以自然順序輸出復(fù)數(shù)變換域數(shù)據(jù)模塊。 FFT 函數(shù)在 master— source— sop 號(hào)上輸出一個(gè)高電平詠沖表示第一個(gè)輸出樣點(diǎn)，如圖 ，圖中詳細(xì)表明了輸出流程制時(shí)序。在 N 個(gè)時(shí)鐘周期之后， master_source_eop信號(hào)被置為高電平，表示轉(zhuǎn)換輸出數(shù)據(jù)塊結(jié)束如圖 。