利用FFT IP Core實(shí)現(xiàn)FFT算法

摘要:結(jié)合工程實(shí)踐，介紹了一種利用FFT IP Core實(shí)現(xiàn)FFT的方法，設(shè)計(jì)能同時(shí)對(duì)兩路實(shí)數(shù)序列進(jìn)行256點(diǎn)FFT運(yùn)算，并對(duì)轉(zhuǎn)換結(jié)果進(jìn)行求模平方運(yùn)算，且對(duì)數(shù)據(jù)具有連續(xù)處理的能力。設(shè)計(jì)采用低成本的FPGA實(shí)現(xiàn)，具有成本低、性能高、靈活性強(qiáng)、速度快等特點(diǎn)，而且通過(guò)工程應(yīng)用證明了設(shè)計(jì)是正確可行的。

    由于FFT(快速傅里葉變換)的問(wèn)世，促進(jìn)了數(shù)字信號(hào)處理這門學(xué)科的成熟，它可應(yīng)用于傅里葉變換理論所能涉及的任何領(lǐng)域。FFT傳統(tǒng)實(shí)現(xiàn)
方法無(wú)非是軟件(軟件編程)和硬件(專用芯片ASIC)兩種，F(xiàn)PGA的出現(xiàn)使人們?cè)贔FT的實(shí)現(xiàn)方面又多了一種選擇。FPGA同時(shí)具有軟件編程的靈活性和ASIC電路的快速性等優(yōu)點(diǎn)，適合高速數(shù)字信號(hào)處理。大多數(shù)FPGA廠商都提供了可配置的邏輯核(Core)實(shí)現(xiàn)各種算法功能，其中包括FFT IP Core(知識(shí)產(chǎn)權(quán)核)。使用這些資源允許設(shè)計(jì)師將更多的時(shí)間和精力放在改善增加系統(tǒng)功能上，這無(wú)疑將大大減少設(shè)計(jì)風(fēng)險(xiǎn)及縮短開(kāi)發(fā)周期。
    本設(shè)計(jì)采用了Altera公司的FFT IP Core實(shí)現(xiàn)FFT功能，可同時(shí)實(shí)現(xiàn)兩路256點(diǎn)實(shí)數(shù)數(shù)據(jù)的FFT轉(zhuǎn)換，并對(duì)轉(zhuǎn)換結(jié)果進(jìn)行求模平方運(yùn)算，設(shè)計(jì)對(duì)數(shù)據(jù)具有連續(xù)處理的能力。FPGA芯片選用的是有史以來(lái)成本最低的Altera公司的Cyclone系列的芯片，F(xiàn)FT內(nèi)核是Altera MegaCore FFT-V2.0.0，整個(gè)設(shè)計(jì)成本低、性能好，已經(jīng)成功地應(yīng)用到雷達(dá)產(chǎn)品中。

2  算法原理和FFT Core介紹
    設(shè)計(jì)用到的算法包括同時(shí)計(jì)算兩個(gè)實(shí)函數(shù)的FFT算法和CORDIC算法。
2.1  同時(shí)計(jì)算兩個(gè)實(shí)函數(shù)的FFT算法
    DFT(離散傅里葉變換)的定義為：
 
式(1)中，都假定時(shí)間函數(shù)x(n)是一個(gè)復(fù)函數(shù)。但是在許多FFT的實(shí)際應(yīng)用中，時(shí)間函數(shù)往往是實(shí)函數(shù)。下面介紹的算法可以有效地減少實(shí)數(shù)序列FFT的計(jì)算工作量，從而提高計(jì)算速度。該方法可歸納為如下幾個(gè)步驟：
①函數(shù)h(n)和g(n)是兩個(gè)實(shí)函數(shù)，n=0，1，…，N-1；
②將其中的一個(gè)作為實(shí)部而另一個(gè)作為虛部，構(gòu)成復(fù)函數(shù)z(n)為：
  z(n)=h(n)+jg(n)，  n=0，1，…，N-1；
③計(jì)算z(n)的N點(diǎn)DFT得：
 
式中，Zr(k)和Zi(k)分別是Z(k)的實(shí)部和虛部；
④從z(k)中分析出H(k)和G(k)：
 
式中，H(k)和G(k)分別是h(n)和g(n)的DFT。
    詳細(xì)的推導(dǎo)過(guò)程參見(jiàn)文獻(xiàn)[2]。

2.2 CORDIC算法原理
  CORDIC(The Coordinate Rotational Digital Computer)算法是一種循環(huán)迭代算法，其基本思想是用一系列與運(yùn)算基數(shù)相關(guān)角度的不斷偏擺從而逼近所需旋轉(zhuǎn)的角度。從廣義上講它是一個(gè)數(shù)值性計(jì)算逼近的方法，由于這些固定的角度與計(jì)算基數(shù)有關(guān)，運(yùn)算只有移位和加減。可用該算法來(lái)計(jì)算的函數(shù)包括乘、除、平方根、正弦、余弦正切、向量旋轉(zhuǎn)(即復(fù)數(shù)乘法)以及指數(shù)運(yùn)算等。CORDIC的基本原理如下。
    向量x+jy，旋轉(zhuǎn)角度θ到向量x'+jy'，假設(shè)的方向用δ表示，旋轉(zhuǎn)的角度為θi，并且θi滿足關(guān)系：tanθi=2ⁱ。則由文獻(xiàn)[3]的推導(dǎo)可知:
 
假設(shè)x[0]=b,y[0]=a,z[0]=0,則有：
 
式中， 為畸變因子，對(duì)于字長(zhǎng)一定的運(yùn)算，它為一常數(shù)，如字長(zhǎng)為16位時(shí)，K=1.6667。δi表示每一次旋轉(zhuǎn)的方向，當(dāng)y[i]≥0時(shí)，其值為1；當(dāng)y[i]≤0時(shí)，其值為-1。

2.3 FFT Core簡(jiǎn)介
    FFT-V2.0.0是Altera公司2004年2月新發(fā)布的FFT知識(shí)產(chǎn)權(quán)核，它是一個(gè)高性能、高度參數(shù)化的快速傅里葉變換(FFT)處理器，支持Cyclone、
Stratix II、Stratix GX、Stratix系列FPGA器件。該FFT Core功能是執(zhí)行高性能的正向復(fù)數(shù)FFT或反向的FFT(IFFT)，采用基2/4頻域抽取(DIF)的FFT算法，其轉(zhuǎn)換長(zhǎng)度為2m，這里6≤m≤14。在其內(nèi)部，F(xiàn)FT采用塊浮點(diǎn)結(jié)構(gòu)，以在最大信噪比(SNR)和最小資源需求之間獲得最大的收益。FFT Core接收一個(gè)長(zhǎng)度為N的、二進(jìn)制補(bǔ)碼格式、順序輸入的復(fù)數(shù)序列作為輸入，輸出轉(zhuǎn)換域的、順序的復(fù)數(shù)數(shù)據(jù)序列。同時(shí)，一個(gè)累加塊指數(shù)被輸出，表示塊浮點(diǎn)的量化因子。FFT Core的轉(zhuǎn)換方向事先由一個(gè)輸入端口為每個(gè)數(shù)據(jù)轉(zhuǎn)換塊指定。
   FFT Core可以設(shè)置兩種不同的引擎結(jié)構(gòu)：四輸出(Quad-output FFT engine)和單輸出(Single-output FFT engine)。對(duì)于要求轉(zhuǎn)換時(shí)間盡量小的
應(yīng)用，四輸出引擎結(jié)構(gòu)是最佳的選擇；對(duì)于要求資源盡量少的應(yīng)用，單輸出引擎結(jié)構(gòu)比較合適。為了增加整個(gè)FFT Core的吞吐量，可以采用多并行引擎結(jié)構(gòu)。
    FFT Core支持3種I/O數(shù)據(jù)流結(jié)構(gòu)：連續(xù)(streaming)、緩沖突發(fā)(Buffered Burst)、突發(fā)(Burst)。連續(xù)I/O數(shù)據(jù)流結(jié)構(gòu)允許處理連續(xù)輸入數(shù)據(jù)，輸出連續(xù)復(fù)數(shù)數(shù)據(jù)流，而不中斷輸入和輸出數(shù)據(jù)；緩沖突發(fā)I/O數(shù)據(jù)流結(jié)構(gòu)與連續(xù)結(jié)構(gòu)相比，需要更少的存儲(chǔ)資源，但是，這是以減少平均吞吐
量為代價(jià)的；突發(fā)數(shù)據(jù)流結(jié)構(gòu)的操作與緩沖突發(fā)方式基本上一致，但突發(fā)方式則需要更少的存儲(chǔ)資源，這也是以降低吞吐量為代價(jià)的。

3  硬件設(shè)計(jì)
 
圖1整體原理圖
    設(shè)計(jì)的整體原理圖如圖1所示。輸入和輸出緩沖器分別存儲(chǔ)預(yù)處理數(shù)據(jù)和FFT轉(zhuǎn)換結(jié)果；FFT運(yùn)算器負(fù)責(zé)FFT運(yùn)算；控制器為輸入和輸出緩沖器提供讀寫(xiě)地址，并控制FFT運(yùn)算的時(shí)序和緩沖器的讀寫(xiě)操作；后處理單元從單路復(fù)數(shù)輸入頻譜數(shù)據(jù)中分離出兩路實(shí)數(shù)輸入頻譜數(shù)據(jù)；求模運(yùn)算器實(shí)現(xiàn)CORDIC算法，求取轉(zhuǎn)換結(jié)果的平方根。設(shè)計(jì)的輸入為兩路實(shí)數(shù)序列，一路作為實(shí)部，另一路作為虛部，由連續(xù)的256點(diǎn)的數(shù)據(jù)段組成；輸出是間斷的256點(diǎn)數(shù)據(jù)段，各數(shù)據(jù)段的前128點(diǎn)為第一路的頻譜數(shù)據(jù)，后128點(diǎn)是第二路的頻譜數(shù)據(jù)。根據(jù)FFT頻譜關(guān)于中心點(diǎn)對(duì)稱的結(jié)果，只截取前半段頻譜數(shù)據(jù)并不會(huì)丟失任何信息。
    整個(gè)系統(tǒng)的工作時(shí)序?yàn)椋?br /> ①數(shù)據(jù)以5MHz的速率輸入到輸入緩沖器；
②FFT運(yùn)算器以40MHz的速率從輸入緩沖器中取數(shù)進(jìn)行運(yùn)算；
③FFT運(yùn)算結(jié)束時(shí)，將轉(zhuǎn)換結(jié)果存入到輸出緩沖器中；
④輸出緩沖器數(shù)據(jù)以20MHz的速率被送到后處理單元進(jìn)行轉(zhuǎn)變；
⑤數(shù)據(jù)被送到求模運(yùn)算器，進(jìn)行CORDIC運(yùn)算，輸出；
⑥當(dāng)③結(jié)束時(shí)，F(xiàn)FT運(yùn)算器又回到起始狀態(tài)，等待處理下一組數(shù)據(jù)，從而使運(yùn)算周而復(fù)始地進(jìn)行。整個(gè)設(shè)計(jì)由控制器嚴(yán)格控制。
    輸入和輸出緩沖器由FPGA內(nèi)部的RAM實(shí)現(xiàn)，這些都相對(duì)簡(jiǎn)單。下面重點(diǎn)介紹。FFT運(yùn)算器、控制器、后處理單元和求模運(yùn)算器。
 
3.1  FFT 運(yùn)算器
    FFT運(yùn)算器采用FFT Core實(shí)現(xiàn)，其引擎結(jié)構(gòu)為雙Single-output，I/O數(shù)據(jù)流采用突發(fā)(Burst)方式。FFT Core采用Atlantic Interface協(xié)議，輸入
接口視為主接收器，輸出接口視為主發(fā)送器。具體接口定義如表1所示。

     具體的工作流程：系統(tǒng)復(fù)位后，數(shù)據(jù)源將master_sink_dav置位，表示有采樣數(shù)據(jù)等待輸入；作為回應(yīng)，F(xiàn)FT Core將master_sink_ena置位，表示可以接收輸入數(shù)據(jù)；數(shù)據(jù)源加載第一個(gè)復(fù)數(shù)數(shù)據(jù)，同時(shí)master_sink_sop置位，表示輸入數(shù)據(jù)塊的起始；下一個(gè)時(shí)鐘，master_sink_sop被清零，輸入數(shù)據(jù)按照自然順序被加入。輸入數(shù)據(jù)達(dá)到256點(diǎn)時(shí)，系統(tǒng)自然啟動(dòng)FFT運(yùn)算。通過(guò)inv_i信號(hào)的置位/清零可以改變單個(gè)數(shù)據(jù)塊的FFT轉(zhuǎn)換方向，inv_i信號(hào)必須和master_sink_sop信號(hào)嚴(yán)格同步。當(dāng)FFT轉(zhuǎn)換結(jié)束時(shí)，子接收器已經(jīng)將master_source_dav信號(hào)置位，表示子接收器可以接收FFT的轉(zhuǎn)換結(jié)果；同時(shí)，master_source_ena信號(hào)置位，F(xiàn)FTCore按照自然順序輸出運(yùn)算結(jié)果；在輸出過(guò)程中，
master_source_sop和master_source_eop信號(hào)被置位，表示輸出數(shù)據(jù)塊的起始和結(jié)束。詳細(xì)的描述參見(jiàn)文獻(xiàn)[4]。

3.2 控制器與后處理單元
    控制器大體可分為三個(gè)部分：輸入緩沖控制(c_i)、FFT運(yùn)算控制(c_f)、輸出緩沖控制(c_o)。c_i為輸入緩沖器提供讀/寫(xiě)地址和相應(yīng)的讀/寫(xiě)
控制信號(hào)；c_f為FFT運(yùn)算器提供控制信號(hào)，嚴(yán)格控制FFT Core的工作時(shí)序;c_o為輸出緩沖器提供讀/寫(xiě)地址及讀/寫(xiě)控制信號(hào)。控制器通過(guò)VHDL語(yǔ)言編程的狀態(tài)機(jī)方式可以輕易實(shí)現(xiàn)。
    后處理單元其實(shí)是式(2)和式(3)的硬件實(shí)現(xiàn)，具體的原理如圖2所示。
 
圖2后處理單元原理圖
    圖中標(biāo)識(shí)“mux”、“+”、“-”、“1/2”分別表示選擇器、加法器、減法器和除法器，dr、di、dnr、dni分別與式(1)和式(2)中的Zr(k)、
Zi(k)、Zr(N-k)、Zi(N-k)相對(duì)應(yīng)。當(dāng)sel等于0時(shí)，提取第一路實(shí)序列的頻譜數(shù)據(jù)G(k)，實(shí)現(xiàn)式(1)功能；當(dāng)sel等于1時(shí)，提取第二路實(shí)序列的頻譜數(shù)據(jù)，實(shí)現(xiàn)式(2)功能。

3.3 求模運(yùn)算器
    由于工程只要求求平方根，不涉及角度的計(jì)算，因此，CORDIC的角度計(jì)算部分沒(méi)有給出，但這并不會(huì)影響到幅度的計(jì)算。整個(gè)CORDIC采用全流水線結(jié)構(gòu)，設(shè)計(jì)總共有16級(jí)流水線單元，各流水線單元結(jié)構(gòu)相似。CORDIC流水線結(jié)構(gòu)如圖3所示。
 
圖3 CORDIC流水線原理圖
    該結(jié)果并不是最終結(jié)果，還要加一級(jí)幅度校正，以去除畸變因子的影響。

4  結(jié)束語(yǔ)
    設(shè)計(jì)的輸入和輸出工作頻率相對(duì)較低，因而很容易滿足，關(guān)鍵是FFT Core的性能指標(biāo)。根據(jù)工程需要，輸入數(shù)據(jù)速率采用5MHz，F(xiàn)FT Core工作在40MHz，輸出轉(zhuǎn)換結(jié)果采用20MHz時(shí)鐘，在此條件下對(duì)設(shè)計(jì)進(jìn)行硬件測(cè)試，結(jié)果證明設(shè)計(jì)功能正確、工作穩(wěn)定、性能優(yōu)越。另外，經(jīng)軟件時(shí)序仿真可知，F(xiàn)FT Core最高工作頻率可達(dá)到117.52MHz，通過(guò)提高運(yùn)算時(shí)鐘，還可獲得更快的運(yùn)算能力。
    設(shè)計(jì)選用Altera公司的FFT Core，成功地在FPGA中實(shí)現(xiàn)了兩路連續(xù)256點(diǎn)實(shí)數(shù)序列FFT的算法，其設(shè)計(jì)成本低、性能好，已經(jīng)成功地應(yīng)用到
雷達(dá)產(chǎn)品中。由于FFT Core的可塑性很強(qiáng)，通過(guò)改動(dòng)參數(shù)設(shè)置，就可輕易地使設(shè)計(jì)適應(yīng)于不同的產(chǎn)品。

參考文獻(xiàn)
[1]Uwe Meyer-Baese.數(shù)字信號(hào)處理的FPGA實(shí)現(xiàn)[M].北京：清華大學(xué)出版社，2003.
[2]侯朝煥，閻世尊，蔣銀林.實(shí)用FFT信號(hào)處理技術(shù)[M].北京：海洋出版社，1990.
[3]談宜育，卞文兵，李元等.一種基于CORDIC算法的R-θ變換ASIC[J].微電子學(xué)，2000，30(3)：166～167.
[4]李滔，韓月秋.基于流水線CORDIC算法的三角函數(shù)發(fā)生器.系統(tǒng)工程與電子技術(shù)[J]，2000，22(4)：85-87.