基于FPGA的級(jí)聯(lián)結(jié)構(gòu)FFT處理器的優(yōu)化設(shè)計(jì)

0 引 言
    數(shù)字信號(hào)處理主要研究采用數(shù)字序列或符號(hào)序列表示信號(hào)，并用數(shù)字計(jì)算方法對(duì)這些序列進(jìn)行處理，以便把信號(hào)變換成符合某種需要的形式。在現(xiàn)代數(shù)字信號(hào)處理中，最常用的變換方法就是離散傅里葉變換(DFT)，然而，它的計(jì)算量較大。運(yùn)算時(shí)間長，在某種程度上限制了它的使用范圍?？焖俑道锶~變換(FFT)的提出使DFT的實(shí)現(xiàn)變得接近實(shí)時(shí)，DFT的應(yīng)用領(lǐng)域也得以迅速拓展。它在圖像處理、語音分析、雷達(dá)、聲納、地震、通信系統(tǒng)、遙感遙測(cè)、地質(zhì)勘探、航空航天、生物醫(yī)學(xué)等眾多領(lǐng)域都獲得極其廣泛的應(yīng)用。隨著FPGA技術(shù)的高速發(fā)展以及EDA技術(shù)的成熟，采用FPGA芯片實(shí)現(xiàn)FFT已經(jīng)顯示出巨大的潛力。
    目前用FPGA實(shí)現(xiàn)的FFT處理器結(jié)構(gòu)大致分為四種：遞歸結(jié)構(gòu)、級(jí)聯(lián)結(jié)構(gòu)、并行結(jié)構(gòu)和陣列結(jié)構(gòu)。遞歸結(jié)構(gòu)只利用一個(gè)碟形運(yùn)算單元對(duì)數(shù)據(jù)進(jìn)行規(guī)律的循環(huán)計(jì)算，使用硬件資源較少，但運(yùn)算時(shí)間較長。級(jí)聯(lián)結(jié)構(gòu)每一級(jí)均采用一個(gè)獨(dú)立的碟形運(yùn)算單元來處理，相對(duì)遞歸結(jié)構(gòu)速度上有所提高，不足之處是增加了延時(shí)用的緩沖存儲(chǔ)器使用量。并行結(jié)構(gòu)對(duì)一級(jí)中的蝶形單元并行實(shí)現(xiàn)，陣列結(jié)構(gòu)是將每一級(jí)的蝶形運(yùn)算單元全部并行實(shí)現(xiàn)，這兩種結(jié)構(gòu)有很高的運(yùn)算速度，但消耗的資源過大，一般不采用。為了提高運(yùn)算速度，特別是為了適應(yīng)多批數(shù)據(jù)處理，一般采用級(jí)聯(lián)結(jié)構(gòu)實(shí)現(xiàn)FFT處理器。

1 FFT整體結(jié)構(gòu)設(shè)計(jì)
    在FFT算法中，目前大多使用基-2和基-4算法實(shí)現(xiàn)級(jí)聯(lián)結(jié)構(gòu)的FFT處理器，除此之外，也可采用基-8和基-16算法來實(shí)現(xiàn)。隨著基數(shù)的增大，對(duì)于相同點(diǎn)數(shù)的離散數(shù)列，處理器所分的級(jí)數(shù)越少，對(duì)緩沖存儲(chǔ)器的需求也越小，因此考慮采用基-16算法來實(shí)現(xiàn)FFT處理器，但基-16算法只能實(shí)現(xiàn)離散數(shù)列點(diǎn)數(shù)是16的p次冪的FFT。從而，引入混合基思想來改進(jìn)基-16算法。
    設(shè)x(n)為N點(diǎn)有限長序列，其DFT為：
   
    式中：n1=0，1，2，…，r1-1；n2=0，1，2，…，r2-1。將頻率變量k(k<N)表示為：
    k=k1r1+k0
    式中：k1=0，1，…r2-1；k0=0，1，…r1-1。
    式(1)可變換為：
   
    設(shè)r1=16P，r2=N／16P=2，4，8，式(2)先將原非16的p次冪的N點(diǎn)FFT分解為16P點(diǎn)的FFT；再分解為N／16P點(diǎn)的FFT。首先對(duì)輸入信號(hào)進(jìn)行16P點(diǎn)的FFT運(yùn)算，然后將結(jié)果乘以一個(gè)旋轉(zhuǎn)因子最后將計(jì)算出的數(shù)據(jù)進(jìn)行一次N／16P點(diǎn)FFT運(yùn)算，得到的結(jié)果即為所需要的N點(diǎn)FFT運(yùn)算結(jié)果。這樣處理，既能減少分解的級(jí)數(shù)，又能使計(jì)算離散數(shù)列點(diǎn)數(shù)只需是2的整數(shù)次冪即可。以1 024點(diǎn)為例，只需分解成兩級(jí)基-16運(yùn)算模塊和一級(jí)基-4運(yùn)算模塊即可實(shí)現(xiàn)，其FFT處理器結(jié)構(gòu)圖如圖1所示。在此結(jié)構(gòu)圖的前端增加／減少基-16運(yùn)算模塊或?qū)⒆詈笠患?jí)基-4運(yùn)算模塊改為基-2或基-8運(yùn)算模塊，就可以實(shí)現(xiàn)其他離散數(shù)列的點(diǎn)數(shù)只需是2的整數(shù)次冪的FFT運(yùn)算。

2 蝶形運(yùn)算核的實(shí)現(xiàn)
2．1 基-16蝶形運(yùn)算核
    如果直接將基-16蝶形運(yùn)算公式轉(zhuǎn)換到硬件中實(shí)現(xiàn)基-16運(yùn)算核，其結(jié)構(gòu)將十分復(fù)雜的。因此，采用易實(shí)現(xiàn)的頻域抽選基-4算法來實(shí)現(xiàn)頻域抽選基-16蝶形運(yùn)算核。由基-4蝶行運(yùn)算單元實(shí)現(xiàn)的基-16蝶行運(yùn)算單元如圖2所示。

    采用并行流水結(jié)構(gòu)實(shí)現(xiàn)的基-16運(yùn)算核，一個(gè)數(shù)據(jù)時(shí)鐘可處理16個(gè)數(shù)據(jù)。而每次蝶形運(yùn)算在一個(gè)數(shù)據(jù)時(shí)鐘內(nèi)只需要計(jì)算出一個(gè)結(jié)果，這將造成資源浪費(fèi)。因此，采用級(jí)聯(lián)結(jié)構(gòu)實(shí)現(xiàn)的基-16蝶形運(yùn)算核，用兩個(gè)基-4蝶形運(yùn)算核分別復(fù)用4次來實(shí)現(xiàn)每一級(jí)中的四個(gè)蝶行運(yùn)算，中間用一個(gè)串行出入／輸出的寄存器進(jìn)行連接，其結(jié)構(gòu)框圖如圖3所示。

2．2 基-4蝶形運(yùn)算核
    基-4蝶形運(yùn)算核的結(jié)構(gòu)如圖4所示，其中加減模塊為兩級(jí)流水結(jié)構(gòu)，一次可以計(jì)算4個(gè)數(shù)據(jù)。蝶形運(yùn)算的四個(gè)串行輸入數(shù)據(jù)經(jīng)串／并轉(zhuǎn)換器轉(zhuǎn)換為四路并行數(shù)據(jù)，進(jìn)入加減運(yùn)算單元。計(jì)算出的4個(gè)并行結(jié)果進(jìn)入并／串轉(zhuǎn)換器后，串行輸入復(fù)數(shù)乘法器和旋轉(zhuǎn)因子相乘然后輸出結(jié)果。因?yàn)閳D1中最后一級(jí)的數(shù)據(jù)只需要進(jìn)行加減運(yùn)算不需要再乘以旋轉(zhuǎn)因子，所以圖1中的基-4蝶形運(yùn)算核是沒有復(fù)數(shù)乘法器的，數(shù)據(jù)從并／串轉(zhuǎn)換器中直接輸出給緩沖存儲(chǔ)器。
2．3 復(fù)數(shù)乘法器
    雖然現(xiàn)在的高端產(chǎn)中已經(jīng)集成了可以完成乘法的DSP資源，但也是有限的。因此高效復(fù)數(shù)乘法器的設(shè)計(jì)對(duì)該設(shè)計(jì)來講仍然非常的重要。復(fù)數(shù)乘法的標(biāo)準(zhǔn)式如下：
    R+jI=(A+jB)×(C+jD)=(AC-BD)+j(AD+BC)
    式中：A，B分別為輸人數(shù)據(jù)的實(shí)部和虛部，C和D分別為旋轉(zhuǎn)因子的實(shí)部和虛部。按照這種標(biāo)準(zhǔn)表達(dá)式，執(zhí)行一次復(fù)數(shù)乘法需要進(jìn)行4次實(shí)數(shù)乘法，2次實(shí)數(shù)加法和2次實(shí)數(shù)減法。將上述公式重新整理為：R=(C-D)·B+C(A-B)，I=(C-D)A-C(A-B)優(yōu)化后的復(fù)數(shù)乘法器需要進(jìn)行3次實(shí)數(shù)乘法，2次實(shí)數(shù)加法和3次實(shí)數(shù)減法，相比傳統(tǒng)結(jié)構(gòu)多了一個(gè)減法器，少了一個(gè)乘法器。在FPGA中，加減法模塊所占用的相對(duì)裸片面積要小于相同位數(shù)的乘法器模塊。這樣的優(yōu)化還是很有價(jià)值的，在FFT吞吐量不變的情況下，可減少25％的乘法器使用量，在乘法器數(shù)量一定的情況下可高FFT吞吐量。

3 存儲(chǔ)器單元
    傳統(tǒng)的級(jí)聯(lián)結(jié)構(gòu)的FFT處理器的緩沖存儲(chǔ)器都是采用乒乓結(jié)構(gòu)，基本思想就是用兩塊相同的RAM交替讀出或?qū)懭霐?shù)據(jù)。即其中一塊RAM在寫入數(shù)據(jù)時(shí)，另一塊RAM用于讀出數(shù)據(jù)。當(dāng)用于寫入數(shù)據(jù)的RAM寫滿時(shí)交換讀寫功能。將乒乓結(jié)構(gòu)中RAM的內(nèi)部存儲(chǔ)單元地址用二進(jìn)制數(shù)a9a8a7a6a5a4a3a2a1a0表示。以寫滿其中以塊RAM為一個(gè)周期，用一個(gè)二進(jìn)制計(jì)數(shù)器m9m8m7m6m5m4m3m2m1m0生成的順序?qū)懭?，混序讀取的乒乓結(jié)構(gòu)RAM的操作地址如表1所示。

    表1中第一，二，四塊存儲(chǔ)器的寫操作地址和讀操作地址是可以互換的，也就是將數(shù)據(jù)混序?qū)懭耄樞蜃x取。因此，根據(jù)這個(gè)規(guī)律采用一塊可同時(shí)讀寫的雙端口RAM來實(shí)現(xiàn)第一，二，四塊存儲(chǔ)器。其基本思想就是對(duì)同一個(gè)地址進(jìn)行讀和寫。以用一塊雙端口RAM實(shí)現(xiàn)第一塊存儲(chǔ)器的為例，在第一個(gè)周期內(nèi)雙端口RAM按照地址m9msm7m6m5mdm3m2m1m0進(jìn)行寫操作，即數(shù)據(jù)是按照自然順序儲(chǔ)存的。在第二個(gè)周期按照地址m0m1m2m3m4m5m6m7msm9同時(shí)進(jìn)行讀寫操作，讀出的數(shù)據(jù)按照倒位序排列，寫入的數(shù)據(jù)按照倒位序儲(chǔ)存的。 在第三個(gè)周期按照地址m9msm7m6m5m4m3m2m1m0同時(shí)進(jìn)行讀寫操作，讀出的數(shù)據(jù)按照倒位序排列，寫入的數(shù)據(jù)是按照自然順序儲(chǔ)存的。依次類推下去，讀出的數(shù)據(jù)都是按照倒位序排列。同樣第二塊和第四塊存儲(chǔ)器的存儲(chǔ)地址也具有這樣類似的循環(huán)規(guī)律。因此只有第三塊存儲(chǔ)器需要用乒乓結(jié)構(gòu)的RAM實(shí)現(xiàn)，與傳統(tǒng)所有存儲(chǔ)器都用乒乓結(jié)構(gòu)RAM實(shí)現(xiàn)相比，節(jié)省了3／8的存儲(chǔ)單元。設(shè)計(jì)中用Matlab軟件直接生成旋轉(zhuǎn)因子，并將其轉(zhuǎn)化為16位有符號(hào)定點(diǎn)數(shù)寫入MIF文件。然后用ROM直接調(diào)用MIF文件，將旋轉(zhuǎn)因子預(yù)置在ROM中。

4 仿真結(jié)果
    選用Altera公司生產(chǎn)的Cyclone Ⅱ的EP2C35F484C7芯片上進(jìn)行驗(yàn)證，在QuartyusⅡ7．2軟件中進(jìn)行編譯和仿真。通過對(duì)高基核的優(yōu)化處理，該設(shè)計(jì)對(duì)邏輯單元消耗量和傳統(tǒng)用基-4算法實(shí)現(xiàn)相近，僅為4 399，但由于本文采用了高基低基組合的混合基算法，在處理1 024點(diǎn)的離散數(shù)列時(shí)，處理器所分的級(jí)數(shù)僅為3級(jí)，相對(duì)傳統(tǒng)的低基數(shù)算法，其實(shí)現(xiàn)減少了對(duì)緩沖存儲(chǔ)器塊數(shù)的需求；并通過對(duì)緩沖存儲(chǔ)器的優(yōu)化設(shè)計(jì)，又比全部用乒乓結(jié)構(gòu)RAM實(shí)現(xiàn)的傳統(tǒng)方法節(jié)省了3／8的存儲(chǔ)單元，因此占用的存儲(chǔ)資源僅為154 048 b。仿真波形如圖5所示，該仿真結(jié)果和Matlab計(jì)算結(jié)果基本一致，存在一定的誤差是由于有限字長效應(yīng)引起的。

5 結(jié) 語
    在100 MHz的時(shí)鐘下工作，完成一次1 024點(diǎn)的FFT從輸入初始數(shù)據(jù)到運(yùn)算結(jié)果完全輸出僅需要54．48μs，且連續(xù)運(yùn)算時(shí)，處理一組1 024點(diǎn)FFT的時(shí)間僅為10．24 μs，達(dá)到了高速信號(hào)處理的要求。