實時頻譜分析儀中并行FFT算法的FPGA設

張亞洲，張超,2，王保銳，2，向長波，2

(1.中國電子科技集團公司 第四十一研究所，青島 266555；2.電子測試技術重點實驗室)

?

張亞洲1，張超1,2，王保銳1，2，向長波1，2

(1.中國電子科技集團公司 第四十一研究所，青島 266555；2.電子測試技術重點實驗室)

摘要:針對實時頻譜分析儀對FFT計算速度高的需求提出一種并行FFT計算的方法，采用數據分開并行處理的方式達到快速計算傅里葉變換的效果。通過對比分析，本方案能夠在不多占用FPGA資源的前提下成倍提高FFT的運算速度，從而提高重疊FFT過程中的重疊點數。仿真分析證明，本方案能夠有效提高實時頻譜分析儀中的信號處理速度，提升時間分辨率指標。

關鍵詞:實時頻譜分析儀；并行FFT；重疊率；XC6VSX315T

引言

FFT作為時域數據變換為頻譜數據進行分析的快速方法，廣泛應用于雷達、數字通信等多種領域中，成為信號處理的一種高效手段。隨著無線電技術的高速發展，為了能夠實時快速測量和分析信號的變化，需要FFT處理速度更快。高性能大規模集成電路的不斷出現使硬件實現FFT成為可能，采用FPGA進行FFT計算，具有編程靈活、執行速度快等優點。但是要求具有實時、高速的FFT場景越來越多，串行FFT難以達到高速信號分析的要求，因此有必要設計一種在工程應用中計算速率高、資源占用率較低，并且開發簡單的并行FFT實現方法。

圖1　實時頻譜儀原理框圖

1應用背景與問題提出

實時頻譜分析(RTSA)是近幾年發展起來的一種新的信號頻譜分析技術。實時頻譜分析儀通過對采集后的中頻數據進行FFT處理后進一步分析而得到各種譜圖，其原理框圖如圖1所示[1]，FFT模塊完成時域到頻域的轉換。為了能夠發現微弱干擾信號，需要實時頻譜分析儀具有較高的頻域分辨率，與此同時，為了能夠測量信號瞬態特性，又需要具有較高的時域分辨率。實時頻譜分析儀通過FFT重疊技術查找非常短的頻譜事件，以及查看信號內部非常短的時間變化。因此，對于實時頻譜分析儀而言，FFT運算速率是其一項重要指標，FFT運算速率越快，單位時間內相同數據量的重疊FFT計算過程中的重疊率相應提高，這樣就可以查看一個信號的變化特性。

實時頻譜分析儀采用FPGA進行數據FFT處理，在250 MHz系統時鐘下，采用Pipelined Streaming I/O結構的FFT IP Core計算1024點的傅里葉變換，此時具有重疊功能的FFT最大能夠達到的運算速率為244 140次/s。在處理最高數據流的情況下，受限于FFT的運算速率，FFT計算過程不重疊。為了提高本產品的性能，使FFT計算速率進一步提高，但使用FPGA中的單個FFT IP Core的設計方法難以實現此目標。

為了提高FFT處理過程中的運算速率，需要尋求一種算法高效、設計簡單的并行計算方法[2]。實時頻譜分析儀在實時FFT處理模塊的并行設計過程中，通常采用直接并行FFT處理算法。直接并行FFT處理算法如圖2所示，為兩路相同FFT計算路徑的并行處理方式。本方法設計結構簡單，但是對FPGA內部資源占用大，為單路設計的兩倍，當FFT處理點數達到16 000以上時，將消耗FPGA內部大量的邏輯資源，尤其是BRAM(內部塊存儲器)資源，嚴重制約著其他功能模塊的設計，同時資源占用過多會帶來時序優化問題，導致程序難以運行到預定頻率。時序難以收斂和資源占用過多是直接并行FFT算法在設計過程中的難點，因此本文實現了一種混合并行FFT計算方法，具有資源消耗少、運算速率高的特點，成倍提高了FFT的運算速率。

圖2　N點直接并行FFT運算示意圖

2算法原理與FPGA實現

2.1算法原理

混合并行FFT處理算法能夠在不占用更多額外資源的前提下成倍提升處理速率,這種方法將N點FFT分解成更短的FFT來并行計算。設長度為N的一組數據序列{x(n)}的離散傅里葉變換[3](DFT)為：

(1)

其中，WN=e-j2π/N,0≤k≤N-1。

計算過程中根據參考文獻[4]進行推導，采用分組的方式進行處理：N分解成L和M的乘積，其中L和M為整數，N=LM。序列x(n)(其中0≤n≤N-1)映射到以l和m為索引值的矩陣中，n=l+mL。其中：l為行索引，0≤l≤L-1；m為列索引，0≤m≤M-1。同理，計算的DFT值映射為從索引k到索引對(p,q)的形式，k=Mp+q，其中0≤p≤L-1，0≤q≤M-1。式(1)可變為：

(2)

(3)

從上式可以看出，本計算可以分成如下3個步驟：

① 計算M點DFT:

② 與因子相乘:

③ 計算L點DFT:

上述推導公式的實現原理框圖如圖3所示，長度為N的數據被分解成多段較短的數據進行并行處理。

圖3　N點DFT的分解算法原理框圖

在設計過程中,用此方法對N點做傅里葉變換，當L和M均為2的冪時，可使用FFT算法作為DFT的快速運算方法。對N進行拆分，令M=N/2，L=2，則由式(3)可以得到：

(4)

其中，k =0,1,…,N-1。

令f1(m)=x(2n)，f2(m)=x(2n+1)，n=0,1,…,N/2-1,由式(4)可得：

(5)

其中，k=0,1,…,N-1，F1(k)和F2(k)為f1(m)和f2(m)的DFT，并且是周期性的，周期為N/2。故式(5)可表示為：

(6)

(7)

其中，k=0,1,…,N/2-1。

從上述推導過程可以看出，當N為2的冪次方時，對f1(m)和f2(m)的DFT可使用FFT作為快速算法，由于一組數據可以拆分成兩個較小的子序列并同時進行FFT，勢必會成倍增加運算速率。

2.2FPGA實現

根據式(6)和(7)，采用FPGA硬件實現FFT，可得如圖4所示的并行FFT計算流程圖。計算結構分為3個主要部分：①數據分配單元，負責數據的分配、重疊控制和加窗運算；②并行FFT單元，雙FFT并行運算，每個FFT計算點數為處理點數的一半；③ 后處理單元，蝶形運算，對輸出數據進行后處理并輸出。經過模塊拆解，將整個流程分成多個部分，采用流水線技術提升處理速度。

圖4　并行FFT計算流程圖

(1) 數據分配單元

中頻信號經ADC采樣后做數字抽取濾波得到IQ數據，產生的數據速率最高約2 GB/s(250 MHz的運行時鐘，連續IQ數據的位寬為64 位)的連續數據流。為了實時處理這些數據并且具有重疊FFT功能，需要FFT處理模塊具有更快的處理速度。考慮到重疊率的可任意配置性，需要對數據緩存并且合理分配到后續的FFT模塊中。

設計中采用奇偶分配的方式對數據進行緩存，從起始數據開始對輸入數據進行奇偶劃分，分別存放于緩存A和緩存B，然后根據重疊比值進行數據的分配。考慮到實際應用中要求具有靈活的重疊比，因此輸出數據根據重疊點數來進行分配，決策將數據輸入到相應的FFT模塊。

為了消除頻譜泄露問題，在傅里葉變換之前應進行加窗處理。設計中窗函數數據存放于雙口RAM中，由工控機計算出相應窗函數類型的數據后寫入，供FPGA內部模塊讀出后使用。這種方式設計簡單、應用靈活，降低了開發成本和難度。

(2) 并行FFT單元

本單元為雙并行FFT處理，每個FFT處理點數為N/2。設計中采用Xilinx公司ISE開發軟件提供的FFT IP Core來進行FFT開發。在實際硬件操作中，本模塊的執行速度是很重要的參數，故采用流水線Streaming I/O結構，以進行連續的數據處理，提升處理速度。此時，進行當前幀的N點數據的運算時，可以加載下一幀的N點數據，同時輸出前一幀的N點數據運算結果。

(3) 后處理單元

對于旋轉因子的設計，項目中采用查找表的方式[5]。k取值為0～N/2-1，即只需N/2個旋轉因子。因此在設計過程中只需要在FPGA中開辟一個存放N/2個旋轉因子的ROM即可，簡化了設計流程。

根據上述所分析的實現方案，選用Xilinx公司Virtex 6系列的XC6VLX315T型號FPGA，使用VHDL硬件描述語言實現最大處理點數為16 384并且點數可變、可任意配置的并行FFT算法。設計過程中采用模塊化設計思想，綜合后的RTL結構圖略——編者注。

3仿真驗證與對比分析

本文設計實現了基于FPGA的混合并行FFT算法，處理點數可變，最大支持16 000點的傅里葉變換。對1024點做FFT測試，Matlab產生含有50 Hz和120 Hz的固定頻率以及隨機信號的采樣序列，隨后以文件形式輸入到Modelsim和ISE中進行邏輯仿真，輸出結果略——編者注。

對于Modelsim輸出的仿真結果再次以文件的形式輸入到Matlab進行處理，從而繪制出頻譜圖，與Matlab對原信號進行分析結果進行對比，如圖5所示。圖5(a)為Matlab對原信號進行分析后的圖譜，圖5(b)為Modelsim仿真輸出結果輸入Matlab后繪制的圖譜，經分析可知兩圖形狀和數據基本一致。本設計具有良好的精度，并且FFT的運算速率成倍提高，工作頻率運行于250 MHz下的1024點的FFT計算速率能夠提高到488 281次/s。

采用兩個完全相同的FFT模塊進行處理以成倍提升FFT處理速率的傳統直接并行設計方案,與文中設計的混合并行方案相比，在具有相同處理速度和點數的情況下,比本方案所占用資源更多。設計最大計算點數為16 384的FFT，并具有相同的運算速率，采用ISE14.3軟件的默認屬性進行綜合和實現，兩種并行方案的資源占用對比如表1所列。由此可見，本文實現的混合并行FFT設計方法在資源占用上具有一定優勢，尤其是Block RAM資源的占用少了近一半，當計算大點數FFT時，FPGA中受限的資源最重要的是Block RAM，因此本設計方案對于后續擴展為具有相同或更高計算速度的32k點數FFT的工程，在資源占用方面顯著降低。

圖5　Matlab與Modelsim仿真結果對比

表1　兩種設計方案資源占用情況對比表

結語

本文基于快速傅里葉算法推導出適用于FPGA實現的混合并行FFT算法。經過仿真測試驗證了本方法的有效性，不僅能夠保證計算精度，還能成倍提高計算速率，尤其適用于實時頻譜分析儀中實時進行時域轉頻域的處理過程。采用本設計方法，在具有相同計算速率的情況下，FPGA中的資源占用約減少一半，對于大點數的FFT計算具有優勢。同樣，在占用近乎相同大小資源的前提下，其FFT計算速率能夠提升一倍，對于實時頻譜分析儀中FFT幀重疊功能可以提升重疊率，使系統在最大極限數據速率的情況下仍能保證至少50%的重疊率，從而提升時間分辨率指標，提高了捕獲和分析短時瞬態信號的能力。

編者注：本文為期刊縮略版，全文見本刊網站www.mesnet.com.cn。

參考文獻

[1] 泰克公司.實時頻譜分析儀原理及應用案例集匯編,2007.

[2] 孫世新,陳平安,張艷.與FFT并行算法相適應的體系結構探討[J].電子科技大學學報,2000,29(5):535-539.

[3] Wang Xudong,Xu Wei,Dang Xiaoyu. Novel High-speed FPGA-based FFT Processor[J].Transactionsof Nanjing University of Aeronautics&Astronautics,2013,30(1):82-87.

[4] John G Proakis,Dimitris G Manolakis.數字信號處理——原理、算法與應用[M].4版.方艷梅，劉永清，譯.北京：電子工業出版社,2007:380-382.

[5] 杜彬,海洋.基于FPGA高速并行FFT處理器設計與實現[J].儀器儀表學報,2009,30(6):156-159.

張亞洲(助理工程師)，研究方向為FPGA數字信號處理與工程實現；張超(高級工程師)，研究方向為數字信號處理和電子測量儀器。

Zhang Yazhou1,Zhang Chao1,2，Wang Baorui1,2,Xiang Changbo1,2

(1.The 41st Institute of CETC,Qingdao 266555,China;2.Key Laboratory for Electronic Measurement Technology)

Abstract：In view of the demand for high-speed of FFT computing of the real-time spectrum analyzer,a parallel FFT computing method is proposed.The effort of fast calculation of Fourier transform is achived by using separate data in the parallel processing.The advantages of this scheme is illustrated by the comparative analysis.This solution can improve the computing speed of FFT,which does not take up more FPGA resources.Therefore,overlap points can be increased in the process of overlapping FFT.The simulation analysis proves that the solution can effectively improve the signal processing speed and time resolution in the real-time spectrum analyzer.

Key words:real-time spectrum analyzer;parallel FFT;overlap rate;XC6VSX315T

收稿日期：(責任編輯：薛士然2015-12-11

中圖分類號:TN47

文獻標識碼:A