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

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

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

[!--empirenews.page--]

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

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

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

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

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

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

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