利用FFT IP Core實現FFT算法

摘要:結合工程實踐，介紹了一種利用FFT IP Core實現FFT的方法，設計能同時對兩路實數序列進行256點FFT運算，并對轉換結果進行求模平方運算，且對數據具有連續處理的能力。設計采用低成本的FPGA實現，具有成本低、性能高、靈活性強、速度快等特點，而且通過工程應用證明了設計是正確可行的。

    由于FFT(快速傅里葉變換)的問世，促進了數字信號處理這門學科的成熟，它可應用于傅里葉變換理論所能涉及的任何領域。FFT傳統實現
方法無非是軟件(軟件編程)和硬件(專用芯片ASIC)兩種，FPGA的出現使人們在FFT的實現方面又多了一種選擇。FPGA同時具有軟件編程的靈活性和ASIC電路的快速性等優點，適合高速數字信號處理。大多數FPGA廠商都提供了可配置的邏輯核(Core)實現各種算法功能，其中包括FFT IP Core(知識產權核)。使用這些資源允許設計師將更多的時間和精力放在改善增加系統功能上，這無疑將大大減少設計風險及縮短開發周期。
    本設計采用了Altera公司的FFT IP Core實現FFT功能，可同時實現兩路256點實數數據的FFT轉換，并對轉換結果進行求模平方運算，設計對數據具有連續處理的能力。FPGA芯片選用的是有史以來成本最低的Altera公司的Cyclone系列的芯片，FFT內核是Altera MegaCore FFT-V2.0.0，整個設計成本低、性能好，已經成功地應用到雷達產品中。

2  算法原理和FFT Core介紹
    設計用到的算法包括同時計算兩個實函數的FFT算法和CORDIC算法。
2.1  同時計算兩個實函數的FFT算法
    DFT(離散傅里葉變換)的定義為：
 
式(1)中，都假定時間函數x(n)是一個復函數。但是在許多FFT的實際應用中，時間函數往往是實函數。下面介紹的算法可以有效地減少實數序列FFT的計算工作量，從而提高計算速度。該方法可歸納為如下幾個步驟：
①函數h(n)和g(n)是兩個實函數，n=0，1，…，N-1；
②將其中的一個作為實部而另一個作為虛部，構成復函數z(n)為：
  z(n)=h(n)+jg(n)，  n=0，1，…，N-1；
③計算z(n)的N點DFT得：
 
式中，Zr(k)和Zi(k)分別是Z(k)的實部和虛部；
④從z(k)中分析出H(k)和G(k)：
 
式中，H(k)和G(k)分別是h(n)和g(n)的DFT。
    詳細的推導過程參見文獻[2]。

2.2 CORDIC算法原理
  CORDIC(The Coordinate Rotational Digital Computer)算法是一種循環迭代算法，其基本思想是用一系列與運算基數相關角度的不斷偏擺從而逼近所需旋轉的角度。從廣義上講它是一個數值性計算逼近的方法，由于這些固定的角度與計算基數有關，運算只有移位和加減。可用該算法來計算的函數包括乘、除、平方根、正弦、余弦正切、向量旋轉(即復數乘法)以及指數運算等。CORDIC的基本原理如下。
    向量x+jy，旋轉角度θ到向量x'+jy'，假設的方向用δ表示，旋轉的角度為θi，并且θi滿足關系：tanθi=2ⁱ。則由文獻[3]的推導可知:
 
假設x[0]=b,y[0]=a,z[0]=0,則有：
 
式中， 為畸變因子，對于字長一定的運算，它為一常數，如字長為16位時，K=1.6667。δi表示每一次旋轉的方向，當y[i]≥0時，其值為1；當y[i]≤0時，其值為-1。

2.3 FFT Core簡介
    FFT-V2.0.0是Altera公司2004年2月新發布的FFT知識產權核，它是一個高性能、高度參數化的快速傅里葉變換(FFT)處理器，支持Cyclone、
Stratix II、Stratix GX、Stratix系列FPGA器件。該FFT Core功能是執行高性能的正向復數FFT或反向的FFT(IFFT)，采用基2/4頻域抽取(DIF)的FFT算法，其轉換長度為2m，這里6≤m≤14。在其內部，FFT采用塊浮點結構，以在最大信噪比(SNR)和最小資源需求之間獲得最大的收益。FFT Core接收一個長度為N的、二進制補碼格式、順序輸入的復數序列作為輸入，輸出轉換域的、順序的復數數據序列。同時，一個累加塊指數被輸出，表示塊浮點的量化因子。FFT Core的轉換方向事先由一個輸入端口為每個數據轉換塊指定。
   FFT Core可以設置兩種不同的引擎結構：四輸出(Quad-output FFT engine)和單輸出(Single-output FFT engine)。對于要求轉換時間盡量小的
應用，四輸出引擎結構是最佳的選擇；對于要求資源盡量少的應用，單輸出引擎結構比較合適。為了增加整個FFT Core的吞吐量，可以采用多并行引擎結構。
    FFT Core支持3種I/O數據流結構：連續(streaming)、緩沖突發(Buffered Burst)、突發(Burst)。連續I/O數據流結構允許處理連續輸入數據，輸出連續復數數據流，而不中斷輸入和輸出數據；緩沖突發I/O數據流結構與連續結構相比，需要更少的存儲資源，但是，這是以減少平均吞吐
量為代價的；突發數據流結構的操作與緩沖突發方式基本上一致，但突發方式則需要更少的存儲資源，這也是以降低吞吐量為代價的。

3  硬件設計
 
圖1整體原理圖
    設計的整體原理圖如圖1所示。輸入和輸出緩沖器分別存儲預處理數據和FFT轉換結果；FFT運算器負責FFT運算；控制器為輸入和輸出緩沖器提供讀寫地址，并控制FFT運算的時序和緩沖器的讀寫操作；后處理單元從單路復數輸入頻譜數據中分離出兩路實數輸入頻譜數據；求模運算器實現CORDIC算法，求取轉換結果的平方根。設計的輸入為兩路實數序列，一路作為實部，另一路作為虛部，由連續的256點的數據段組成；輸出是間斷的256點數據段，各數據段的前128點為第一路的頻譜數據，后128點是第二路的頻譜數據。根據FFT頻譜關于中心點對稱的結果，只截取前半段頻譜數據并不會丟失任何信息。
    整個系統的工作時序為：
①數據以5MHz的速率輸入到輸入緩沖器；
②FFT運算器以40MHz的速率從輸入緩沖器中取數進行運算；
③FFT運算結束時，將轉換結果存入到輸出緩沖器中；
④輸出緩沖器數據以20MHz的速率被送到后處理單元進行轉變；
⑤數據被送到求模運算器，進行CORDIC運算，輸出；
⑥當③結束時，FFT運算器又回到起始狀態，等待處理下一組數據，從而使運算周而復始地進行。整個設計由控制器嚴格控制。
    輸入和輸出緩沖器由FPGA內部的RAM實現，這些都相對簡單。下面重點介紹。FFT運算器、控制器、后處理單元和求模運算器。
 
3.1  FFT 運算器
    FFT運算器采用FFT Core實現，其引擎結構為雙Single-output，I/O數據流采用突發(Burst)方式。FFT Core采用Atlantic Interface協議，輸入
接口視為主接收器，輸出接口視為主發送器。具體接口定義如表1所示。

     具體的工作流程：系統復位后，數據源將master_sink_dav置位，表示有采樣數據等待輸入；作為回應，FFT Core將master_sink_ena置位，表示可以接收輸入數據；數據源加載第一個復數數據，同時master_sink_sop置位，表示輸入數據塊的起始；下一個時鐘，master_sink_sop被清零，輸入數據按照自然順序被加入。輸入數據達到256點時，系統自然啟動FFT運算。通過inv_i信號的置位/清零可以改變單個數據塊的FFT轉換方向，inv_i信號必須和master_sink_sop信號嚴格同步。當FFT轉換結束時，子接收器已經將master_source_dav信號置位，表示子接收器可以接收FFT的轉換結果；同時，master_source_ena信號置位，FFTCore按照自然順序輸出運算結果；在輸出過程中，
master_source_sop和master_source_eop信號被置位，表示輸出數據塊的起始和結束。詳細的描述參見文獻[4]。

3.2 控制器與后處理單元
    控制器大體可分為三個部分：輸入緩沖控制(c_i)、FFT運算控制(c_f)、輸出緩沖控制(c_o)。c_i為輸入緩沖器提供讀/寫地址和相應的讀/寫
控制信號；c_f為FFT運算器提供控制信號，嚴格控制FFT Core的工作時序;c_o為輸出緩沖器提供讀/寫地址及讀/寫控制信號。控制器通過VHDL語言編程的狀態機方式可以輕易實現。
    后處理單元其實是式(2)和式(3)的硬件實現，具體的原理如圖2所示。
 
圖2后處理單元原理圖
    圖中標識“mux”、“+”、“-”、“1/2”分別表示選擇器、加法器、減法器和除法器，dr、di、dnr、dni分別與式(1)和式(2)中的Zr(k)、
Zi(k)、Zr(N-k)、Zi(N-k)相對應。當sel等于0時，提取第一路實序列的頻譜數據G(k)，實現式(1)功能；當sel等于1時，提取第二路實序列的頻譜數據，實現式(2)功能。

3.3 求模運算器
    由于工程只要求求平方根，不涉及角度的計算，因此，CORDIC的角度計算部分沒有給出，但這并不會影響到幅度的計算。整個CORDIC采用全流水線結構，設計總共有16級流水線單元，各流水線單元結構相似。CORDIC流水線結構如圖3所示。
 
圖3 CORDIC流水線原理圖
    該結果并不是最終結果，還要加一級幅度校正，以去除畸變因子的影響。

4  結束語
    設計的輸入和輸出工作頻率相對較低，因而很容易滿足，關鍵是FFT Core的性能指標。根據工程需要，輸入數據速率采用5MHz，FFT Core工作在40MHz，輸出轉換結果采用20MHz時鐘，在此條件下對設計進行硬件測試，結果證明設計功能正確、工作穩定、性能優越。另外，經軟件時序仿真可知，FFT Core最高工作頻率可達到117.52MHz，通過提高運算時鐘，還可獲得更快的運算能力。
    設計選用Altera公司的FFT Core，成功地在FPGA中實現了兩路連續256點實數序列FFT的算法，其設計成本低、性能好，已經成功地應用到
雷達產品中。由于FFT Core的可塑性很強，通過改動參數設置，就可輕易地使設計適應于不同的產品。

參考文獻
[1]Uwe Meyer-Baese.數字信號處理的FPGA實現[M].北京：清華大學出版社，2003.
[2]侯朝煥，閻世尊，蔣銀林.實用FFT信號處理技術[M].北京：海洋出版社，1990.
[3]談宜育，卞文兵，李元等.一種基于CORDIC算法的R-θ變換ASIC[J].微電子學，2000，30(3)：166～167.
[4]李滔，韓月秋.基于流水線CORDIC算法的三角函數發生器.系統工程與電子技術[J]，2000，22(4)：85-87.