實數二維FFT及其改進算法的FPGA實現

劉冀川

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

0 引言

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

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

1 二維FFT的實現原理

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

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

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

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

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

圖1 二維FFT算法流程圖

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

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

2 算法改進

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

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

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

設

則下式成立:

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

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

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

3 算法的仿真與性能分析

3.1 算法仿真

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

圖2 二維FFT及其改進算法仿真結果

3.2 用時比較

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

表1 FFT用時比較

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

3.3 資源耗用率

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

表2 FFT主要資源耗用率

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

4 結束語

在分析二維FFT算法的基礎上，利用實數FFT結果具有對稱性的特性，結合FPGA的優勢，提出并實現了流水結構的FFT算法。該算法采用并行的組織結構，進一步的減少了處理時間和硬件資源，更好地滿足了FFT處理數據時間的需要。該算法已應用于工程實踐當中，解決了關鍵性技術，取得了很好的效果。

[1]王旭東，劉渝.全并行結構FFT的FPGA實現[J].南京航空航天大學學報，2006，38（1）:96－100.

[2]黃寧，朱恩，榮黃寧.高速FFT芯片設計及結構研究[J].電子器件，2008，31（2）:511－515.

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

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

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

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

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

[8]李偉.1024點基4FFT處理芯片及接口設計研究[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.