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