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