【正文】 比。如果 N 取 32，那么 將達(dá)到 1024。所以要想使得 DFT 在各種科學(xué)和工程計(jì)算中得到廣泛的應(yīng)用就必須想辦法減少其運(yùn)算量。其實(shí)一個(gè) N 點(diǎn) DFT 可以看做是由幾個(gè)較短的2DFT 組成的。此外，旋轉(zhuǎn)因子 具有明顯的周期性和對(duì)稱性。比較常用的 FFT 算法有基2 FFT 和基 4FFT 兩種。下面就以 8 點(diǎn)的MFFT 為例詳細(xì)分析基2 FFT 算法。由于這兩種算法的基本原理是相同的，所以下面主要介紹 DITFFT 算法。設(shè)序列 x(n)的長(zhǎng)度為 N，并且有以下的條件成立,M 為自然數(shù) (24)2M?x1(r)和 x2(r)是 x(n)按 n 的奇偶性分解成的兩個(gè) N/2 點(diǎn)的子序列，如下式所示， (25)1()xr0,12Nr???， (26)2)??,?基于 FPGA 的 FFT 算法 實(shí)現(xiàn)第 4 頁(yè) 共 41 頁(yè)那么 x(n)的 DFT 為 ()()()knknNNnXkxWx????? /21/21(21)00(krkrNr W??? (27)/21/21200()()NNkkrrrxx????由于 (28)222 2/jkrNjkrkr krNWeW??????所以 (29)/21/21/2/21200()()()()+()Nkr krkNNNr rXkxxX?????=0,1,…,N1 其中 X1(k)和 X2(k)分別為 x1(r)和 x2(r)的 N/2 點(diǎn) DFT，即 (210) /211/210()()[()]NkrNrXkxWDFTxr??? (211)/212/220()()[()]krr?又由于 X1(k)和 X2(k)都是以 N/2 為周期，且 (212)2Nkk???所以 X(k)又可以表示為如下所示的表達(dá)式 (213)12()()kNXkWX??0,1? (214)2?2k??這樣一個(gè) N 點(diǎn)的 DFT 就被拆分成為了兩個(gè) N/2 點(diǎn)的 DFT。通常為了后續(xù)說(shuō)明的方便，和其它許多文獻(xiàn)一樣，在本文中也將式(313)和式(314)的運(yùn)算用圖 所示的一個(gè)流圖符號(hào)表示。ABCA + B CA B C基于 FPGA 的 FFT 算法 實(shí)現(xiàn)第 5 頁(yè) 共 41 頁(yè)圖 蝶形運(yùn)算符號(hào)采用蝶形運(yùn)算符號(hào)的這種圖示方法，可以用圖 來(lái)表示前面所講到的運(yùn)算。32圖 點(diǎn) DFT 的一次時(shí)域抽取分解圖(N=8)由圖 可以看出，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運(yùn)算。由前面的說(shuō)明可以知道，計(jì)算一個(gè) N/2 點(diǎn) DFT 需要 次復(fù)數(shù)乘法和 N/2(N/21)次復(fù)數(shù)加法。通過(guò)對(duì)比可以看出，只進(jìn)行過(guò)這樣的一次分解就使得運(yùn)算量減少了2近一半，充分說(shuō)明了這樣分解對(duì)減少 DFT 的運(yùn)算量是十分有效的。與第一次分解相同，x3(l)和 x4(l)為 x1(r)按奇偶分解成的兩個(gè)長(zhǎng)為 N/4 的子序列，即 （215）3241(),01,)4xll???????那么，X1(k)又可表示為 )12(/14/02/14/01 ()()( ??????lkNNiklNi WlxxkX = klikNkli 4/14/024/14/03 )()(????? = (216)12/,42/3Xxk?其中 (217))]([)()( 34/14/033 lxDFTWlxkklNNi ???? 　 (218))]([)()( 44/1/04 llkli??基于 FPGA 的 FFT 算法 實(shí)現(xiàn)第 6 頁(yè) 共 41 頁(yè)同理，由 X3(k)和 X4(k)的周期性和 的對(duì)稱性 最后得到：2NWm/42/2kNkW??? (219)1,0,)()(/()42/31 ??????XkkkN?同理可得 (220)4/,)()(4/()62/52 ??NkWkNkXkN?其中有 (221))]([)()( 54/14/055 lxDFTlxklNi ???? (222))]([)()( 64/14/066 llkXklNi?? (223)1/,)12()65 ?????Nlxl?這樣，如圖 所示，經(jīng)過(guò)第二次的分解，一個(gè) N/2 點(diǎn)的 DFT 就被拆分成為了兩個(gè) N/4 點(diǎn)的DFT 了。依次類(lèi)推，經(jīng)過(guò) M1 次分解，最后將 N 點(diǎn) DFT 分解成 N/2 個(gè) 2 點(diǎn) DFT。圖中用到關(guān)系式 。圖 N 點(diǎn) DFT 的第二次時(shí)域抽取分解圖（N=8）基于 FPGA 的 FFT 算法 實(shí)現(xiàn)第 7 頁(yè) 共 41 頁(yè)圖 N 點(diǎn) DITFFT 運(yùn)算流圖（N=8）(3)DITFFT 算法與直接計(jì)算 DFT 運(yùn)算量的比較由 DITFFT 算法的分解過(guò)程及圖 可見(jiàn)，N=時(shí)，其運(yùn)算流圖應(yīng)該有 M 級(jí)蝶形，每一級(jí)都由 N/2 蝶形運(yùn)算構(gòu)成。所以，M 級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為 (224)C2log2)(??復(fù)數(shù)加次數(shù)為 (225)NA2l)(?而由前面的介紹，直接計(jì)算 N 點(diǎn)的 DFT 需要 次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。當(dāng) N= =1024 時(shí)，可以求得直接計(jì)算 N 點(diǎn)的 DFT 和使用基2 210DITFFT 算法的所需乘法次數(shù)的比值為 (226))/(2?這樣，運(yùn)算效率就提高了 200 多倍。由此圖更加直觀地看出 FFT 算法的優(yōu)越性，從圖 35 可以明顯的看出，N 越大時(shí)，優(yōu)越性就越明顯。　　基 4FFT 算法的基本運(yùn)算是 4 點(diǎn) DFT。239。按 DIT(時(shí)間抽取)的 1 024 點(diǎn)的基 4FFT 共需 5 級(jí)蝶形運(yùn)算，每級(jí)從 RAM 中讀取的數(shù)據(jù)經(jīng)過(guò)蝶形運(yùn)算后原址存入存儲(chǔ)單元準(zhǔn)備下一級(jí)運(yùn)算。后 3 級(jí)類(lèi)推。運(yùn)算過(guò)程中所需的旋轉(zhuǎn)因子的值經(jīng)過(guò)查詢預(yù)設(shè)的正弦與余弦 ROM 表得到。序列 r(n)的 N 點(diǎn) DFT 如下所示： (227) 1.,0)()(/)210 ????kenxakXNpnkjN N 點(diǎn) IDFT 如下所示： 1.,0][1)(/20??nekaNnxNpj (228) DFT 直接計(jì)算的復(fù)雜性可以通過(guò)快速傅里葉變換(FFT)算法大大降低。其中一類(lèi) FFT 算法為庫(kù)利圖基( CooleyTukey)基 r 按頻率抽選（Decimationin Frequency，縮寫(xiě) DIF）法將輸入序列循環(huán)分解為N/r 個(gè)長(zhǎng)度為 r 的序列，并需要 級(jí)運(yùn)算。每次通過(guò) FFT 處理器都要完成 次運(yùn)算?；?FPGA 的 FFT 算法 實(shí)現(xiàn)第 9 頁(yè) 共 41 頁(yè) 將輸入序列循環(huán)分解為 4 點(diǎn)序列的基 4 分解，使用 4 點(diǎn) FFT 在乘法運(yùn)算上具有更大優(yōu)勢(shì)，Altera 公司的 FFT 兆核選用的就是基 4 運(yùn)算，在 N 是 2 的奇數(shù)冪的情況下，F(xiàn)FT IP 核，自動(dòng)在完成轉(zhuǎn)換的最后使用基 2 運(yùn)算。 塊浮點(diǎn)結(jié)構(gòu)保證了在 FFT 函數(shù)和整個(gè)轉(zhuǎn)換過(guò)程中數(shù)據(jù)位數(shù)的完整使用。這種移位方法保證最低位(LSB)的最小值在乘法運(yùn)算后的輸出進(jìn)行舍入操作之前就被丟棄。為了在連續(xù)輸出模塊中產(chǎn)生統(tǒng)一的比例，必須用最終的指數(shù)對(duì) FFT 函數(shù)輸出進(jìn)行比例換算。為了增加 FFT 兆核函數(shù)的總吞吐量，也可以在一個(gè) FFT 兆核函數(shù)變量中使用多個(gè)并行引擎。四輸出(Quadoutput)指的是內(nèi)部 FFT 蝶形處理器的吞吐量，這種引擎實(shí)現(xiàn)結(jié)構(gòu)可以在一個(gè)單時(shí)鐘周期內(nèi)計(jì)算所有四個(gè)基 4 蝶形復(fù)數(shù)輸出。復(fù)數(shù)采樣數(shù)據(jù) x[k，m]從內(nèi)部存儲(chǔ)器并行讀出，并由變換開(kāi)關(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ì)算。 圖 四輸出 F 訂引擎結(jié)構(gòu)(2)單輸出 FFT 引擎結(jié)構(gòu)在需要最小尺寸 FFT 函數(shù)的應(yīng)用中，單輸出引擎最適合。在這種引擎結(jié)構(gòu)中，每個(gè)時(shí)鐘周期計(jì)算一個(gè)單蝶形輸出，需要一個(gè)單獨(dú)的復(fù)數(shù)乘法器，其引擎結(jié)構(gòu)如圖 所示。1)流(Streaming)I/0 數(shù)據(jù)流結(jié)構(gòu)流 I/O 數(shù)據(jù)流結(jié)構(gòu)允許輸入數(shù)據(jù)連續(xù)處理，并輸出連續(xù)的復(fù)數(shù)據(jù)流，這個(gè)過(guò)程中不需要停止FFT 數(shù)據(jù)流進(jìn)出。FFT 兆核函數(shù)采用 Altera Atlantic接口 I/O 協(xié)議，輸入接口為主設(shè)備匯端(MasterSink)．而輸出接口為主設(shè)備源端(Master Source)。作為回應(yīng)，F(xiàn)FT 函數(shù)將 Masterink_ena 信號(hào)置為高電平，表明有能力接收這些輸人信哆。在下一時(shí)鐘周期，master_sink_sop 信號(hào)被復(fù)位，并以自然順序加載數(shù)據(jù)樣點(diǎn)。圖 FFT Streaming 數(shù)據(jù)流結(jié)構(gòu)輸入流程控制時(shí)序在 streaming 數(shù)據(jù)流結(jié)構(gòu)中，F(xiàn)FT 函數(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ù)位。FFT 函數(shù)復(fù)位 master_sink_ena 信號(hào)，并繼續(xù)處理已入的數(shù)據(jù)模塊。 當(dāng) FFT 已經(jīng)完成了輸入模塊的變換，并且從設(shè)備匯端(Slave Sink)將 master_source—dav 號(hào)置高電平（表示數(shù)據(jù)從設(shè)備接收器可以接收輸出數(shù)據(jù)模塊）時(shí)，F(xiàn)FT 將 master—source—ena 號(hào)置高電平，并且以自然順序輸出復(fù)數(shù)變換域數(shù)據(jù)模塊。在 N 個(gè)時(shí)鐘周期之后，master_source_eop 信號(hào)被置為高電平，表示轉(zhuǎn)換輸出數(shù)據(jù)塊結(jié)束如圖 所示。這種數(shù)據(jù)流結(jié)構(gòu)的仿真結(jié)果如圖 所示。作為回應(yīng)，F(xiàn)FT 函數(shù)將 master—sink—ena 信號(hào)置高電平，表明有能力接收這些輸入信號(hào)。在下一個(gè)時(shí)鐘周期，master—sink_sop 信號(hào)被復(fù)位，并以自然順序加載后面的 N1 個(gè)復(fù)輸數(shù)據(jù)樣點(diǎn)。如圖 所示為輸入信號(hào)流程控制時(shí)序。下一個(gè)輸入模塊的起點(diǎn)由 mastersinksop 脈沖確定。 3)突發(fā)(Burst)I/O 數(shù)據(jù)流結(jié)構(gòu) 突發(fā) I/O 數(shù)據(jù)流結(jié)構(gòu)的執(zhí)行過(guò)程和緩沖突發(fā)結(jié)構(gòu)相同，不同的是，對(duì)于給定參數(shù)設(shè)置突發(fā)結(jié)構(gòu)在降低平均吞吐量的前提下需要更少的存儲(chǔ)資源?；?FPGA 的 FFT 算法 實(shí)現(xiàn)第 13 頁(yè) 共 41 頁(yè)3 FFT 設(shè)計(jì)實(shí)現(xiàn) 總體結(jié)構(gòu)設(shè)計(jì)設(shè)計(jì)的總體方框結(jié)構(gòu)圖如圖 所示。DDS 模塊是為了方便測(cè)試（產(chǎn)生正弦信號(hào)）而增設(shè)的。信號(hào)采樣部分會(huì)定時(shí)采樣數(shù)據(jù)并進(jìn)行存儲(chǔ)；FFT 運(yùn)算部分負(fù)責(zé)對(duì)采樣數(shù)據(jù)進(jìn)行換算，并將換算后的數(shù)據(jù)存人雙口 RAM。 a / d 采樣控制模塊F F TI P 核雙端口 R A M 1數(shù)據(jù)加載模塊 1雙端口 R A M 2數(shù)據(jù)加載模塊 2縮放運(yùn)算求模運(yùn)算波形顯示控制模塊V G A 顯示控制模塊D D S 信號(hào)發(fā)生器S i n k e n aS o u r c e s o p至 V G A顯示器Sinksop圖 方框結(jié)構(gòu)圖各模塊簡(jiǎn)介各模塊功能簡(jiǎn)介如表 所列基于 FPGA 的 FFT 算法 實(shí)現(xiàn)第 14 頁(yè) 共 41 頁(yè)表 各模塊功能 FFT IPCore 的建立 ①安裝 MegaCore。MegaCore 不附帶在 Quartus II 軟件中，需要單獨(dú)向Altera 公司購(gòu)買(mǎi)或申請(qǐng)?jiān)囉冒?。?Quartus II 主界面中選擇 ToolMegaWizard PlugIn Managc 打開(kāi)添加宏單元的向?qū)Вx擇 Create a new custom megafunction variation 新建宏單元模塊然后在新建宏單元模塊窗口中選擇 DSP TransformsFFT 3 并命名為 fft。在 Quartus II 主界面中，在 FFT 兆核函數(shù)向?qū)е袉螕簟癝tep 1：Parameterize”打開(kāi) FFT 參數(shù)設(shè)置對(duì)話框，具體參數(shù)設(shè)置如下： (a)在 Parameters 選項(xiàng)卡設(shè)置 FFT 變換長(zhǎng)度(Transform Length)為 512，數(shù)據(jù)精度(Data Precision)和旋轉(zhuǎn)因子精度(Twiddle