【正文】 on inproving remarkably. At the same time the design methods and ideas based on FPGA to realiz FFT is put forward. The purpose of this goal is design of FFT Processor based on FPGA. The main research of this paper is to study how to use the FPGA to realiz FFT algorithm. The design has adopted the time extracting the base2 algorithm,and used Sequence structurestructure to design a wing operation unit, and at the same time selected the double port RAM storage structure, in this way the design method can keep a fortable processing speed advantage. As a consequence ,plete an input signal called 64 point card and 12 plural of FFT need just us, basically content the requirement of realtime. In the simulation test stages , with the help of Quartus Ⅱof Altera pany ,which provide a multiple platform design development environment, finished the simulation , then used the results pared with Matlab calculation results, verified the correctness of the design. Key words : Fast Fourier transform (FFT) Field programmable gates array (FPGA) Quartus Ⅱ . 1 第一章 緒論 在 數(shù)字信號處理技術(shù)中，離散傅立葉變換 DFT和卷積是 信號處理中兩個最基本也是最常用的運算，它們涉及到信號與系統(tǒng)的分析與綜合 這一廣泛的信號處理領(lǐng)域 。相應(yīng)的，在這些領(lǐng)域 中普遍的 都要求 FFT處理器具 有高速度、高精度、大容量和實時處理的性能 。從 FFT算法理論的發(fā)展上看，主要有兩個方向 ： (1)組合數(shù) FFT算法，針對 FFT變換點數(shù) N等于 2的整數(shù)次冪，如基 2算 法、基 4算法、基 8算法、實因子算法、分裂基算法及任意組合因子算法，利用系數(shù)的周期性和對稱性，使長序列的 DFT分解成更小點數(shù)的 DFT，從而大大 減少運算工作量?？刂坪唵?、實現(xiàn)規(guī)整的算法在硬件系統(tǒng)實現(xiàn)中要優(yōu)于僅僅是在運算量上占優(yōu)的算法。這種實現(xiàn)方法具有軟件設(shè)計多用性的優(yōu) 點，能夠適用 各種需要 FFT運算進行信號處理的應(yīng)用場合，靈活方便。在產(chǎn)品發(fā)展過程中，它的功能無法任意修改或改進。新近推出的 FPGA產(chǎn)品都采用多層布線結(jié)構(gòu)，內(nèi)含豐富的 I/O管腳， 且具有 大容量的邏輯單元，內(nèi)置嵌入式 RAM資源，內(nèi)部集成多個數(shù)字鎖相環(huán)，嵌入多個硬件乘法器，所有這一切都使得 FPGA在數(shù)字信號處理領(lǐng)域顯示出自己特有 的優(yōu)勢 。 FPGA實現(xiàn) FFT的 優(yōu)越性 由于成本、系統(tǒng)功耗和面市時間等原因，許多通訊、視頻和圖像系統(tǒng)已無法 簡單地利用DSP處理器來實現(xiàn)，基于 FPGA的信號處理器已廣泛應(yīng)用于各種信號處理領(lǐng)域。 (2)FPGA的存儲量大。 DSP往往需要外部的接口和控制芯片配合工作，F(xiàn)PGA則不需要，這樣使得硬件更簡單和小型化 。 本文研究的主要內(nèi)容 如今學(xué)界對 FFT運算軟、硬件實現(xiàn)的研究正在積極的進行，并取得了眾多突出的成果。 目前不少大學(xué)及研究所都使用 FPGA芯片設(shè)計開發(fā)具有自主知識產(chǎn)權(quán)的 FFT。同時，處理器是在不使用 IP核的前提下開發(fā)的，從而大大降低了實現(xiàn)成本。 4 第 二 章 FFT算法原理 簡介 離散傅立葉變換 及其實現(xiàn)的局限性 離散傅立葉變換 (DFT)開辟了頻域離散化的道路，使數(shù)字信號處理也可以在頻域上采用數(shù)字運算方法進行，它可以作為一種數(shù)學(xué)工具來描述離散信號的時域與頻域表示的關(guān)系，大大增加了數(shù)字信號處理的靈活性，特別是它的多種快速算法，使信號的實時處理和設(shè)備的簡化得以實現(xiàn)，所以離散傅立葉變換不僅在理論上有重要意義，而且在各種數(shù)字信號處理中起著核心的作用。這一變換主要用來分析濾波器形狀和信號頻譜。因此對于 N個 k值，共需要 次復(fù)數(shù)乘法和 N(N1)復(fù)數(shù)加法。 快速傅里葉變換 FFT的原理 如 所述， DFT計算時間長，實現(xiàn)困難，直接使用譜分析和信號的實時處理是不切實際的。 FFT 算法正是基于上述的基本思路而發(fā)展起來的 ， 快速傅里葉變換 (FFT)的提出 ,從根本上改變了傅里葉變換的地位。 基 2時域抽取 FFT 算法 基 2時間抽取法 FFT的基本原理是將一個 N點的計算分解為兩個 N/2點的 DFT計算，每 N/2點的計算再進一步分解為 N/4點計算，依次類推。那么由式 (26)可得： X(k)= G(k)+ WnkNH(k) k=0,1,?? N/21 (28) X(k+N/2)= G(k)WnkNH(k) k=0,1,?? N/21 (29) 一個簡單的碟形運算單元如圖 21所示： ABPBWA ?PBWA ?PW 圖 21 基 2時間抽取法 碟形運算單元 基本結(jié)構(gòu) 式 (28)和式 (29)結(jié)合在一起，將 N點的 DFT分解成了兩個 N/2點的 DFT。以此類推，對于 N=2L (L 為整數(shù) )點的 FFT，要經(jīng)過 log2N 級運算，每一級有 2N 個蝶形單元，總共有 2N log2N 個運算單元，經(jīng)過 2N log2N 次復(fù)數(shù)乘法和 2N log2N 次復(fù)數(shù)加法實現(xiàn) DFT 運算。 ③原位運算：當(dāng)數(shù)據(jù)輸入到存儲器以后，每一組蝶形運算后，結(jié)果仍然存放在這同一組存儲器中的同一位置，不需要另辟存儲單元，直到最后輸出。 表 21 碼位的倒位序（ N=8） 自然順序碼 二進制碼 倒位序二進制碼 到位序數(shù) 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 實際運算中，總是先按自然順序?qū)⑤斎胄蛄写嫒氪鎯卧?，要實現(xiàn) FFT算法，首先將按自然順序存放的序列經(jīng)變址運算變換得到倒位序的排列。最后一次迭代的蝶形類型最多，參加蝶形運算的兩個數(shù)據(jù)點的間隔也最大，為2N。 同樣點數(shù)的 DFT，基 4算法運算量為基 2算法的 75％。 10 第 三 章 FFT處理器基于 FPGA的設(shè)計 FPGA因其在 EDA領(lǐng)域的眾多優(yōu)勢，正在漸漸替代 DSP處理器而成為數(shù)字信號處理硬件實現(xiàn)的新方法。 (1)順序處理 順序處理是 FFT專用處理器的基本形式，蝶形運算單元在控制器的控制下，根據(jù)標(biāo)準(zhǔn)的 FFT信號流圖，按時間順序依次進行運算。對一個 N點的 FFT變換，每一級的 N/2次蝶形運算安排一個獨立的蝶形處理器按順序完成，總共采用 log2N個蝶形運算單元同時進行工作，這種形式稱為流水線處理或者級聯(lián)處理。 (4)陣列處理 把流水線處理和并行迭代處理結(jié)合起來，采用2N log2N個蝶形運算單元實現(xiàn)全并行工作，稱為陣列處理。 FFT處理器的總體設(shè)計方案 該設(shè)計采用 順序 結(jié)構(gòu)設(shè)計蝶形運算單元 ， 同時采用雙端口 RAM存儲結(jié)構(gòu) 。每個蝶形運算的輸入、輸出數(shù)據(jù)均要經(jīng)過 RAM的讀寫操作，因此， RAM的頻繁讀寫操作對 FFT的處理速度影響較大。將旋轉(zhuǎn)因子記做 WrN ，除去 r=0的因子，其余的 511個旋轉(zhuǎn)因子偶對稱。旋轉(zhuǎn)因子實部和虛部的符號根據(jù) r的值確定，當(dāng) 0≤ r≤ 255時，旋轉(zhuǎn)因子實部符號為 0，即實部為正值，當(dāng) r255時，旋轉(zhuǎn)因子實部符號為 1，即實部為負值，旋轉(zhuǎn)因子的虛部符號恒為 l，即虛部恒為負值。 (3)FFT運算單元 此模塊是處理器設(shè)計的重點單元。 可以看出，蝶形處理器是 FFT 運算單元的核心 。 基于此， 首先對 復(fù)數(shù)乘法器 給出具體 的設(shè)計 方案。 Start信號啟動 FFT運算，若 Busy信號為低電平，則可進行下一個 FFT運算，當(dāng) FFT完成后，產(chǎn)生 Outen信號通知外部讀取處理后的數(shù)據(jù)。 h 0 0 1 Eq u a l 81 39。 h 0 0 0 Eq u a l 11 0 39。 h 0 5 39。 h 0 5 39。 h 0 F s t a t e ~[ 7 . . 4 ]Eq u a l 31 39。 h 1 co u n t e r~[ 9 . . 0 ] 圖 33 地址生成模塊結(jié)構(gòu)圖 15 (5)倒序模塊 由 FFT算法可知，順序輸入的數(shù)據(jù) FFT結(jié)果按位倒序輸出，為了能在輸出端得到順序的 1024點頻域數(shù)據(jù)，因此在運算完成后，進入位倒序模塊，使得輸出結(jié)果順序輸出。 (3)ICR包括各種長度的連線線段和一些可編程連接開關(guān)，它們將各個 CLB或 IOB連接起來，構(gòu)成特定功能的電路。 (2)FPGA內(nèi)部的 DCM模塊提供倍頻功能，蝶形運算采用流水線工作方式，使每一個蝶形運算在一個時鐘周期內(nèi)完成，提高了處理速度。 兵乓結(jié)構(gòu)如圖 35所示： 輸 入 數(shù)據(jù) 選 擇單 元輸 入 數(shù)據(jù) 選 擇單 元數(shù) 據(jù) 緩 沖模 塊 2數(shù) 據(jù) 緩 沖模 塊 2數(shù) 據(jù) 緩 沖模 塊 1數(shù) 據(jù) 緩 沖模 塊 1輸 出 數(shù)據(jù) 選 擇單 元輸 出 數(shù)據(jù) 選 擇單 元數(shù) 據(jù) 流運 算 處理 模 塊數(shù) 據(jù) 流運 算 處理 模 塊 圖 35 乒乓結(jié)構(gòu)示意圖 綜上所述 FFT整體模塊結(jié)構(gòu) 如圖 36所示 cl kr stst a r tI i n [ 1 1 . . 0 ]Q i n [ 1 1 . . 0 ]f f t I [ 1 1 . . 0 ]f f t Q [ 1 1 . . 0 ]cf f t 4 st a r tf a ct o r st a r ti n p u t b u syo u t d a t a e nw e nw d a t a I [ 1 1 . . 0 ]w d a t a Q [ 1 1 . . 0 ]r a d d r [ 9 . . 0 ]w a d d r [ 9 . . 0 ]O u t P o si t i o n [ 9 . . 0 ]cl k acl k bw e aa d d r a [ 9 . . 0 ]a d d r b [ 9 . . 0 ]d i a [ 1 1 . . 0 ]d o b [ 1 1 . . 0 ]cl k acl k bw e aa d d r a [ 9 . . 0 ]a d d r b [ 9 . . 0 ]d i a [ 1 1 . . 0 ]d o b [ 1 1 . . 0 ]cl ki n v e r tr stst a r tI [ 1 1 . . 0 ]Q [ 1 1 . . 0 ]I o u t [ 1 3 . . 0 ]Q o u t [ 1 3 . . 0 ]cl kD [ 1 5 . . 0 ]Q [ 1 1 . . 0 ]cl kD [ 1 5 . . 0 ]Q [ 1 1 . . 0 ]cl kr sta n g l e [ 9 . . 0 ]I [ 1 3 . . 0 ]Q [ 1 3 . . 0 ]I o u t [ 1 5 . . 0 ]Q o u t [ 1 5 . . 0 ]cl ki n v e r tr stst a r ta n g l e [ 9 . . 0 ]DE N AQP R EC L Ra d d re s s : A a d d re s sd i v 4 l i m i t : I l i m i td i v 4 l i m i t : Q l i m i tm u l f a ct o r: a m u l f a ct o rcl krs ts t a rti n v e rti n p u t b u s yo u t d a t a e nI i n [ 1 1 . . 0 ]Q i n [ 1 1 . . 0 ]I o u t [ 1 3 . . 0 ]Q o