實數(shù)二維FFT及其改進算法的FPGA實現(xiàn)

劉冀川

（中國電子科技集團公司第五十四研究所，河北石家莊050081）

0 引言

快速傅里葉變換（FFT）是最常用的信號處理方法之一，在通信對抗領(lǐng)域得到廣泛的應(yīng)用[1]。隨著高速跳頻通信和突發(fā)通信技術(shù)的發(fā)展，對信號的快速檢測能力有了更高的要求，對FFT處理速度要求也越來越高[2]。

目前，F(xiàn)PGA設(shè)計都是使用廠商提供的FPGA軟核，處理速度無法進一步提高。為了實現(xiàn)更快的處理速度，需要利用一些計算技巧，自主開發(fā)新的FFT處理模塊。對多個快速算法及其工程可實現(xiàn)性進行評估后，選擇了基于二維處理的FFT快速實現(xiàn)算法，并結(jié)合FPGA芯片的編程特性對算法進行了改進，在FPGA內(nèi)實現(xiàn)并在試驗平臺上進行了功能測試和驗證工作。

1 二維FFT的實現(xiàn)原理

設(shè)序列x（n）的長度為N，且N為2的自然數(shù)次冪，其DFT為X（k）[3]。則，

若N=M×L，將x（n）進行重新排序為L行M列的矩陣。假設(shè)，

將n、k代入X（k）的表達式，整理后得到:

由上式可以看出，方括號內(nèi)是L點的FFT，一共M個。而最外層的求和項是M點的FFT，一共L個。這樣就把一個基于一維處理的FFT運算轉(zhuǎn)換為基于二維處理的FFT運算。

二維FFT的算法流程圖如圖1所示。

圖1 二維FFT算法流程圖

具體實現(xiàn)步驟如下[4]:①數(shù)據(jù)重排，將N點數(shù)據(jù)排成L×M點格式;②做M個L點的一維FFT變換;③將L點數(shù)據(jù)輸出乘以旋轉(zhuǎn)因子得到中間數(shù)據(jù)矩陣;④做L個M點一維FFT變換;⑤整序輸出。

由上可知，即使兩次FFT的IP核復(fù)用，F(xiàn)PGA完成二維FFT計算也需要至少個IP核，所以當M=L時，最省資源。例如，1024點FFT最少需要32個IP核，需要大量的硬件邏輯資源，給FPGA實現(xiàn)帶來的難度。

2 算法改進

針對上述的硬件資源消耗太大的問題，對實數(shù)二維FFT算法進行了改進，以節(jié)省硬件資源，從而降低硬件成本。在許多情況下，時域中的時間序列信號都是實數(shù)值，對于實值信號，可以利用實數(shù)信號FFT結(jié)果的對稱性，以及通過復(fù)值FFT（CFFT）計算實值FFT（RFFT）的方法來提高運算效率[5]。

FPGA的FFT IP核是針對復(fù)數(shù)來進行計算的，對于實數(shù)，以前的做法是把虛部全部設(shè)為0，這樣，計算出來的結(jié)果就是實數(shù)的FFT結(jié)果。但是，現(xiàn)在要減少IP核數(shù)量，所以要想辦法把虛部也利用上。

利用復(fù)值FFT計算實值FFT，當N=2m時，對于實值信號x（n）和y（n），其中（n=0，1，…，N－1），設(shè)置一個z（n）=x（n）+jy（n），并設(shè){z（n）}的FFT（即CFFT）為{Z（k）}。下面分析用Z（k）求X（k）和Y（k）的方法[6]。

設(shè)

則下式成立:

于是X（k）和Y（k），（k=0，1，…，N－1）可表示為:

而且，有ZR（N）=ZR（0），ZI（N）=ZI（0）。

經(jīng)過上述計算以后，還原出了兩路FFT結(jié)果X（k）和Y（k），這樣，通過M/2個IP核就能實現(xiàn)M列變換。根據(jù)上面提到的二維FFT的具體實現(xiàn)步驟可知，得到的列變換的FFT結(jié)果X（k）和Y（k）后，乘以旋轉(zhuǎn)因子，再進行行變換，根據(jù)實數(shù)FFT結(jié)果的對稱性[7]，那么只需要（L/2）+1行數(shù)據(jù)進行行變換，需要的IP核數(shù)量也為（L/2）+1，這樣，2次FFT計算所使用的IP核復(fù)用，實際使用的IP核數(shù)量為max{M/2，L/2+1}，當M=L時，使用的IP核最少，即（L/2）+1。

3 算法的仿真與性能分析

3.1 算法仿真

針對上述二維FFT及其改進算法，對1024點正弦數(shù)進行了MATLAB仿真[8]，結(jié)果如圖2所示。與一維FFT相比，結(jié)果完全相同，從而證明了算法的正確性。

圖2 二維FFT及其改進算法仿真結(jié)果

3.2 用時比較

在工作時鐘為150MHz時鐘下，速度最快的IP核算法和二維改進算法用時的比較如表1所示[9]。

表1 FFT用時比較

從表中可以看出，二維FFT并行算法的用時相對于最快的IP核速度的10倍多。

3.3 資源耗用率

此算法在Xilinx公司的XC4VSX55芯片上實現(xiàn)，其主要資源耗用率如表2所示[10]。

表2 FFT主要資源耗用率

與之相比，改進后算法的硬件資源DSP48S為78%，如果用未進行改進的二維FFT算法，1024點的FFT所需要的DSP48S已超出XC4VSX55的資源上限，由此可見，改進的二維FFT算法大大節(jié)省了硬件資源，從而降低了硬件成本。

4 結(jié)束語

在分析二維FFT算法的基礎(chǔ)上，利用實數(shù)FFT結(jié)果具有對稱性的特性，結(jié)合FPGA的優(yōu)勢，提出并實現(xiàn)了流水結(jié)構(gòu)的FFT算法。該算法采用并行的組織結(jié)構(gòu)，進一步的減少了處理時間和硬件資源，更好地滿足了FFT處理數(shù)據(jù)時間的需要。該算法已應(yīng)用于工程實踐當中，解決了關(guān)鍵性技術(shù)，取得了很好的效果。

[1]王旭東，劉渝.全并行結(jié)構(gòu)FFT的FPGA實現(xiàn)[J].南京航空航天大學學報，2006，38（1）:96－100.

[2]黃寧，朱恩，榮黃寧.高速FFT芯片設(shè)計及結(jié)構(gòu)研究[J].電子器件，2008，31（2）:511－515.

[3]張麗君.大點數(shù)FFT的二維算法FPGA并行實現(xiàn)[J].無線電通信技術(shù)，2013，39（3）:86－88.

[4]張傲華.基于FPGA的高速實時信號處理技術(shù)研究[D].成都:電子科技大學，2005:22－27.

[5]李伯全，胥保文，潘海彬，等.基于FPGA的FFT高速運算器設(shè)計[J].儀器儀表學報，2008，29（4）:51－53.

[6]谷荻隆嗣.快速算法與并行信號處理[M].北京:科學出版社，2003.

[7]鄧波，戎蒙恬，湯曉峰.可配置高速高精度FFT的硬件實現(xiàn)[J].計算機工程，2006，32（17）:254－256.

[8]李偉.1024點基4FFT處理芯片及接口設(shè)計研究[D].南京:東南大學，2009:39－40.

[9]Xilinx.LogiCORE IP Fast Fourier Transform v7.1[M].USA:Xllinx，2010.

[10]Xilinx.Virtex4 User Guide[M].USA:Xllinx，2005.