【正文】 法快速傅立葉變換 FFT就成為了數(shù)字信號處理的最基本技術(shù)之一 。 隨著技術(shù)的發(fā)展， FFT也應(yīng)用到了 眾多 的領(lǐng)域。相應(yīng)的，在這些領(lǐng)域 中普遍的 都要求 FFT處理器具 有高速度、高精度、大容量和實時處理的性能 。因此，如何更快速、更靈活地實現(xiàn) FFT變得越來越重要。 因此 對 FFT算法及其實現(xiàn)方式的研究是很有意義的 。 FFT算法的研究現(xiàn)狀 自 1965年美國庫利 ()和圖基 ()提出 FFT快速算法以來， FFT己有了多種算法。從 FFT算法理論的發(fā)展上看，主要有兩個方向 ： (1)組合數(shù) FFT算法，針對 FFT變換點數(shù) N等于 2的整數(shù)次冪，如基 2算 法、基 4算法、基 8算法、實因子算法、分裂基算法及任意組合因子算法，利用系數(shù)的周期性和對稱性，使長序列的 DFT分解成更小點數(shù)的 DFT，從而大大 減少運算工作量。 (2)N不等于 2的整數(shù)次冪的算法，以威諾格蘭德 (S． Winograd)為代表的一 類傅立葉變換算法 (Winograd Fourier Transform Algorithm，簡稱 WFTA算法， Prime Factor Transform Algorithm，簡稱 PFTA算法 )，利用下標映射和數(shù)論 以及近代數(shù)學(xué)的知識，去掉級間的旋轉(zhuǎn)因子，從而減少運算量。 PFTA和 WFTA在運算量上占優(yōu)，用的乘法器比 Coo1eyTukey算法少，但控制復(fù)雜，控制單元實現(xiàn)起來相對麻煩。在硬件實現(xiàn)中，需要考慮的不僅僅是算法運算量，更重要的是算法的復(fù)雜性、規(guī)整性和模塊化?？刂坪唵巍崿F(xiàn)規(guī)整的算法在硬件系統(tǒng)實現(xiàn)中要優(yōu)于僅僅是在運算量上占優(yōu)的算法。分裂基算法具有一定 的優(yōu)勢，綜合了基 4和基 2的運算特點，但其蝶形運算結(jié)構(gòu)在控制上要復(fù)雜一 些?；?2和基 4算法是目前普遍采取的兩種算法。 FFT處理器的研究現(xiàn)狀 FFT處理 器是 FFT算法的硬件實現(xiàn)，針對其硬件實現(xiàn)方案，主要有三種途 徑： (1)利用 DSP處理器 實現(xiàn) FFT算法 。這種實現(xiàn)方法具有軟件設(shè)計多用性的優(yōu) 點，能夠適用 各種需要 FFT運算進行信號處理的應(yīng)用場合，靈活方便。但是，通用 DSP處理器構(gòu)成的 FFT處理機 2 采用循環(huán)編碼算法，程序量小，但存在大量的冗余運算，需要許多跳轉(zhuǎn)操作， 并且 處 理速度較慢，難以滿足現(xiàn)代數(shù)字信號處理高速、大規(guī)模、實時性的要求 。 (2)利用 ASIC實現(xiàn) FFT算法 。這種方案運算速度快，可靠性高，非常適合實時 性 和對可靠性要求較高的信號處理系統(tǒng)，但 弊端是 不能重新組態(tài) ，可編程能力有限。在產(chǎn)品發(fā)展過程中，它的功能無法任意修改或改進。因此，任何的線路改版都需要重新設(shè)計并且重新制造，這不僅增加開發(fā)成本，而且 阻礙了 產(chǎn)品 的 快 速上市，不太適合處理算法和參數(shù)經(jīng)常改變的場合 。 (3)利用 FPGA來實現(xiàn) FFT算法。 FPGA芯片具備在線可編程能力，具有硬件結(jié)構(gòu)可重構(gòu)的特點，適合于算法固定、運算量大的前端數(shù)字信號處理。新近推出的 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設(shè)計和實現(xiàn) FFT就具有了很大的價值。 近幾年，隨著現(xiàn)場可編程門陣列 (Field Programmable Gate Array， FPGA)技術(shù)的迅速發(fā)展，采用并行度更大、速度更快的 FPGA芯片來實現(xiàn) FFT己成為必然趨勢。 FPGA技術(shù)的關(guān)鍵就是利用強有力的設(shè)計工具來縮短開發(fā)周期，提供元 器件的優(yōu)質(zhì)利用性，降低設(shè)計成本，并能夠并行處理數(shù)據(jù)，容易實現(xiàn)順序結(jié)構(gòu)，且升級簡便，提高設(shè)計的靈活性，這些都非常適合實現(xiàn) FFT算法。 FPGA實現(xiàn) FFT的 優(yōu)越性 由于成本、系統(tǒng)功耗和面市時間等原因，許多通訊、視頻和圖像系統(tǒng)已無法 簡單地利用DSP處理器來實現(xiàn)，基于 FPGA的信號處理器已廣泛應(yīng)用于各種信號處理領(lǐng)域。 FPGA所固有的靈活性和性能可讓設(shè)計者緊跟新標準的變化，并能提供可行的方法來滿足不斷變化的標準要求。 與 DSP相比， FPGA實現(xiàn) FFT的主要優(yōu)越性有： (1)FPGA實現(xiàn)數(shù)字信號處理最顯著的特點就是高速性能好。 FPGA有內(nèi)置的高速乘法器和加法器，尤其適合于乘法和累加等重復(fù)性的 DSP任務(wù)。 (2)FPGA的存儲量大。 DSP內(nèi)部一般沒有大容量的存儲器，但是 FFT實時處理運算需要存儲大量的數(shù)據(jù)，只能外接存儲器，這樣往往會使運算速度下降，同時電路也會更復(fù)雜和不穩(wěn)定。目前，高檔的 FPGA中有大量的高速存儲器，不用外接存儲器便可實現(xiàn) FFT實時處理運算，其速度更快，電路更簡單，集成度和 可靠性也大幅度提高。 (3)FPGA是硬件可編程的，比 DSP更加靈活。 DSP往往需要外部的接口和控制芯片配合工作，F(xiàn)PGA則不需要，這樣使得硬件更簡單和小型化 。 (4)在比較 FPGA和 DSP時，一個極為重要的系統(tǒng)參數(shù)是輸入 /輸出 (I/O)帶寬。除了一些專 3 用引腳外， FPGA上幾乎所有的引腳 均可供用戶使用，這使得 FPGA信號處理方案具有非常高性能的 I/O帶寬。大量的 I/O引腳和多塊存儲器 可讓系統(tǒng)在設(shè)計中獲得優(yōu)越的并行處理性能 。 本文研究的主要內(nèi)容 如今學(xué)界對 FFT運算軟、硬件實現(xiàn)的研究正在積極的進行，并取得了眾多突出的成果。而如何在保證系統(tǒng)對高速度、低成本的要求下，實現(xiàn)高精度的 FFT運算，已經(jīng)成為各研發(fā)機構(gòu)的研究重點。如前所述， FPGA因其在 EDA領(lǐng)域的眾多優(yōu)勢，正在漸漸替代 DSP處理器而成為數(shù)字信號處理硬件實現(xiàn)的新方法。 我國的 FPGA技術(shù)起步相對較晚，但進入 21世紀后，發(fā)展非常迅速。 目前不少大學(xué)及研究所都使用 FPGA芯片設(shè)計開發(fā)具有自主知識產(chǎn)權(quán)的 FFT。 本次論文就是在這樣一個背景下提出 的 一種基于 FPGA的高速 FFT處理器設(shè)計方法 ，以期自主設(shè)計基于 FPGA芯片的 FFT，把 FFT實時性的要求和 FPGA芯片設(shè)計的靈活性結(jié)合起來 ，提高 FFT處理速度，滿足現(xiàn)代信號處理的高速度、高可靠性要求。 當(dāng)系統(tǒng)工作頻率為 90 MHz時，完成1024點輸入為 12位復(fù)數(shù)的 FFT需要 456us。由于處理時間遠小于 1024點序列采樣時間，所以系統(tǒng)可實現(xiàn)不間斷采樣，頻譜分析的結(jié)果實時顯示，滿足了所設(shè)計數(shù)字頻譜分析儀系 統(tǒng)的實時性要求。同時，處理器是在不使用 IP核的前提下開發(fā)的，從而大大降低了實現(xiàn)成本。 本次論文 對 FFT 的 原理及其基于 FPGA 的設(shè)計進行了闡述。第一章 對 FFT 研究情況進行了簡單的闡述 ， 第二章 詳細研究 了基 2DITFFT 算法 和基 4DITFFT 算法 ，并做了簡單比較，第三章基于 FPGA 給出 FFT 處理器各個模塊的設(shè)計，第四章對基 2FFT 中采用的蝶形單元和旋轉(zhuǎn)因子復(fù)數(shù)乘法的蝶形處理器 進行 FPGA 的時序仿真。結(jié)合本次論文需要，采用基2DITFFT 算法 設(shè)計 64 點 FFT 處理系統(tǒng)并進行時序仿真。 4 第 二 章 FFT算法原理 簡介 離散傅立葉變換 及其實現(xiàn)的局限性 離散傅立葉變換 (DFT)開辟了頻域離散化的道路，使數(shù)字信號處理也可以在頻域上采用數(shù)字運算方法進行，它可以作為一種數(shù)學(xué)工具來描述離散信號的時域與頻域表示的關(guān)系，大大增加了數(shù)字信號處理的靈活性，特別是它的多種快速算法，使信號的實時處理和設(shè)備的簡化得以實現(xiàn)，所以離散傅立葉變換不僅在理論上有重要意義，而且在各種數(shù)字信號處理中起著核心的作用。 離散傅立葉變換 (DFT)是數(shù)字信號處理的一個工具，相當(dāng)于模擬信號分析的傅立葉變換。 一維 DFT中，設(shè) x(n)是長 為 N的序列，則其 DFT定義為： X(k)=???10 )(Nn nxWnkN ， k=0,1,…… N1 (21)其中 ： , (22) DFT把信號或濾波器從時域變換到頻域，這主要是為了研究信號或濾波器的頻率特性。通過 DFT的變換，將離散的數(shù)字信號變換為不同頻率分量的和，使得更加清楚地了解信號的頻 率分布。這一變換主要用來分析濾波器形狀和信號頻譜。對信號而言， DFT提供的信息稱為信號的頻譜，對濾波器而言， DFT得到的信息稱為濾波器的頻率響應(yīng)，它由兩部分組成：幅度響應(yīng)和相位響應(yīng)，幅度響應(yīng)給出了濾波器的形狀 。 考慮 x(n)為復(fù)數(shù)序列的一般情況，對 某一個 k值，直接按式 (21)計算。 X(k)值需要 N次復(fù)數(shù)乘法、 N1次復(fù)數(shù)加法。因此對于 N個 k值，共需要 次復(fù)數(shù)乘法和 N(N1)復(fù)數(shù)加法。實現(xiàn)一次復(fù)數(shù)乘法需要 4次實數(shù)乘法和 2次實數(shù)加法，一次復(fù)數(shù)加法需要兩次實數(shù)加法。因此直接計算全部 X(k)需要 4 次實數(shù)乘法和 2N(N一 1)次實數(shù)加法。當(dāng) N較大時，對實時信號處理來說，運算量相當(dāng)可觀，例如 N=1024時， N2=1048576，這不免對處理器計算速度提出了 十分苛刻的要求，于是如何減少計算離散傅立葉變換 的運算量變的至關(guān)重要。 快速傅里葉變換 FFT的原理 如 所述， DFT計算時間長，實現(xiàn)困難，直接使用譜分析和信號的實時處理是不切實際的。 為減少運算量，提高運算速度，就必須改進算法。 顯然，把 N點 DFT分解為幾個較短的 5 DFT，可使乘法次數(shù)大大減少。 基于此 ， 我們可以利 用 旋轉(zhuǎn)因子 WnkN明顯的周期性和對稱性來實現(xiàn)這一設(shè)想 ， 其 對稱性 表現(xiàn)為 ： WnkN?=(WnkN=W kNnN )( ? (23) 其 周期性 表現(xiàn)為 ： WnkN =W kNnN )( ? =W nNkN )( ? (24) 利用 DFT的上述特性，可以將長序列的 DFT分解為短序列的 DFT，這樣可以避免大量的重復(fù)運算，提高 DFT的運算速度。 FFT 算法正是基于上述的基本思路而發(fā)展起來的 ， 快速傅里葉變換 (FFT)的提出 ,從根本上改變了傅里葉變換的地位。其 基本思想就是 將 N 點序列分解成兩個或更多的較短序列，這些短序列的 DFT 可重新組合成原序列的 DFT，過程中利用 WnkN的周期性和對稱性來減少 DFT的運算次數(shù)，使運算量得到很大的改觀。這種分解可分為兩類：一類是將時間序列 x(n)進行逐次分解，稱為按時間抽取算法另一類將傅立葉變換序列 X(k)進行分解，稱為按頻率抽取算法 。兩種算法本質(zhì)上是一樣的， 接下來 以時域抽取中的基 2，基 4 為主介紹 這兩類算法的實現(xiàn)思想和具體的分解步驟。 基 2時域抽取 FFT 算法 基 2時間抽取法 FFT的基本原理是將一個 N點的計算分解為兩個 N/2點的 DFT計算，每 N/2點的計算再進一步分解為 N/4點計算，依次類推。信 號 x(n)根據(jù)采樣信號分解為奇采樣點和偶采樣。設(shè)偶采樣序列為 m(n)=x(2n)，奇采樣序列為 t(n)=x(2n+1)。 X(k)= ??偶數(shù)n nx )(WnkN + ??奇數(shù)n )(nx WnkN = ???12/0 )2(Nn nxWknN2 + ??? ?12/0 )12(Nn nxW nkN )12( ? = ???12/0 )(Nn nmWknN2 +WnkN ???12/0 )(Nn ntWknN2 (25) 其中： WkrN2 =WkrN2/ ； (26) 所以： X(k)= ???12/0 )(Nr rmWkrN2/ +WnkN ???12/0 )(Nr rtWkrN2/ 6 =G(k)+ WnkNH(k) k=0,1,?? N1 (27) 其中： G(k)和 H(k)分別是 m(n)和 t(n)的 N/2點 DFT。那么由式 (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/2點在分解成奇偶兩部分，則 N/2點的 DFT可以由兩個 N/4點的 DFT求得，依次類推，一直分解到N/2個 2點的 DFT。例如可以把一個 8點的 DFT分解為四個 2點的 DFT，分解圖如圖 22所示。 X ( 0