【文章內(nèi)容簡介】 TFFT運(yùn)算流圖，如圖 。圖中用到關(guān)系式。圖中的輸入序列不是順序的，但是后面會(huì)看到，其排列是有規(guī)律的。 圖 N 點(diǎn) DFT 的第二次時(shí)域抽取分解圖（ N=8） 圖 N點(diǎn) DITFFT運(yùn)算流圖（ N=8） (3)DITFFT 算法與直接計(jì)算 DFT 運(yùn)算量的比較由 DITFFT 算法的分解過程及圖 可見， N=時(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ù)為 (224) 復(fù)數(shù)加次數(shù)為 (225) 而由前面的介紹，直接計(jì)算 N 點(diǎn)的 DFT 需要次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。當(dāng) N1時(shí)， N(N1)是約等于的。當(dāng) N==1024時(shí)，可以求得直接計(jì)算 N點(diǎn)的 DFT和使用基 2 DITFFT算法的所需乘法次數(shù)的比值為 og)2/( 22 ??NN N (226) 這樣，運(yùn)算效率就提高了 200多倍。圖 FFT算法與直接計(jì)算 DFT所需乘法次數(shù)的比較曲線。由此圖更加直觀地看出 FFT算法的優(yōu)越性，從圖 35 可以明顯的看出， N 越大時(shí)，優(yōu)越性就越明顯。 圖 FFT 算法與直接計(jì)算 DFT 所需乘法次數(shù)的比較曲線 基 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)對于輸出變量進(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)算具有相對獨(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ù)乘法的對稱性來實(shí)現(xiàn)。其中一類 FFT 算法為庫利 圖基( CooleyTukey)基 r 按頻率抽選（ Decimationin Frequency，縮寫 DIF） 法將輸入序列循環(huán)分解為 N/r個(gè)長度為 r的序列，并需要級(jí)運(yùn)算。 每一級(jí)分解由同一個(gè)硬件單元完成，包括數(shù)據(jù)從存儲(chǔ)器中抽取、通過 FFT 處理器以及入存儲(chǔ)器的過程。每次通過 FFT 處理器都要完成次運(yùn)算。通常基數(shù) r選擇 4和 16， ,增加分解基數(shù) r，可以通過犧牲硬件的資源來減少 FFT 處理器的運(yùn)算次數(shù)。 將輸入序列循環(huán)分解為 4點(diǎn)序列的基 4分解，使用 4點(diǎn) FFT在乘法運(yùn)算上具有更大優(yōu)勢， 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)范圍的測量按比例進(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ù)對 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) 對于需要最少轉(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ǔ)器之前對復(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)如圖 。 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)置為高電平，對于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)。如圖 程控制時(shí)序，圖中 z，（ n）表示輸入復(fù)數(shù)據(jù)實(shí)部， z．（ n）表示輸入復(fù)數(shù)據(jù)虛部。 圖 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)來對下一個(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é)束如圖 。 2)緩沖突發(fā) (Burst)I/O數(shù)據(jù)流結(jié)構(gòu) 緩沖突發(fā) I/O數(shù) 據(jù)流結(jié)構(gòu)的 FFT需要的存儲(chǔ)器資源比流動(dòng) 1/0數(shù)據(jù)流結(jié)構(gòu)少，但平均模塊吞吐量減少。這種數(shù)據(jù)流結(jié)構(gòu)的仿真結(jié)果如圖 。在系統(tǒng)復(fù)位信號(hào) ( reset)變?yōu)榈碗娖胶?，?shù)據(jù)源將 master_ sink_ dav信號(hào)置為高電平，對于 FFT函數(shù)來說這表明在輸入端至少有 N個(gè)復(fù)數(shù)數(shù)據(jù)樣點(diǎn)可以輸入。作為回應(yīng)， FFT 函數(shù)將 master— sink— ena 信號(hào)置高電平，表明有能力接收這些輸入信號(hào)。數(shù)據(jù)源加載第一個(gè)數(shù)數(shù)據(jù)樣點(diǎn)到 FFT函數(shù)中，同時(shí)將 master_ sink_ sop信號(hào)置高電平，表示輸入模塊的開始。在下一個(gè)時(shí)鐘周期 ， master— sink_sop信號(hào)被復(fù)位，并以自然順序加載后面的 N1個(gè)復(fù)輸數(shù)據(jù)樣點(diǎn)。 當(dāng)完全載入輸入模塊時(shí)． FFT 函數(shù)復(fù)位 master— sink_ena 信號(hào)，表示 FFT 不再接收其他輸入數(shù)據(jù)并開始計(jì)算輸入數(shù)據(jù)模塊的變換結(jié)果。如圖 。在 FFT處理器內(nèi)部輸入緩沖區(qū)讀取輸入樣點(diǎn)之后， FFT將 master sink— ena信號(hào)重新置為高電平，并準(zhǔn)備讀取下一個(gè)輸入模塊。下一個(gè)輸入模塊的起點(diǎn)由 mastersinksop脈沖確定。 圖 FFT 緩沖突發(fā)數(shù)據(jù)流結(jié)構(gòu)輸出信號(hào) 流程控制時(shí)序 信號(hào) master_source_sop 和 master _source_eop 分別表示輸出模塊數(shù)據(jù)包的起點(diǎn)和終點(diǎn)如圖。 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)在降低平均吞吐量的前提下需要更少的存儲(chǔ)資源。其仿真結(jié)構(gòu)圖如圖 圖 FFT 緩沖突發(fā)數(shù)據(jù)流結(jié)構(gòu)輸出信號(hào)流程控制時(shí)序的仿真結(jié)構(gòu)圈 在突發(fā) I/O 數(shù)據(jù)流結(jié)構(gòu)中，載人一個(gè)有效輸入模塊以后， master _sink_ena 信號(hào)被復(fù)位，直到 FFT 函數(shù)完成轉(zhuǎn)換并且輸出數(shù)據(jù)模塊被完全讀出為止， master_sink_ena 信號(hào)才被重新置位，準(zhǔn)備下一個(gè)輸入模塊的載入。 3 FFT 設(shè)計(jì)實(shí)現(xiàn) 設(shè)計(jì)的總體方框結(jié)構(gòu)圖如圖 所示。主要包括 A/D 采樣控制模塊 (sample)、 FFT 運(yùn)算前數(shù)據(jù)存儲(chǔ)模塊 (sample_dpram)、 FFT IP 核 (fft)、縮放求模運(yùn)算模塊