基于FPGA實現的FFT速度與規模分析

劉 智

（佛山職業技術學院，廣東 佛山 528137）

0 引言

FFT(快速傅里葉變換)是DFT 的快速算法，是把數據從時域到頻域變換的基本運算.它是數字譜分析的必要前提，是數字信號處理的核心工具之一。現代數字信號處理是面向高速、大容量數據流的實時處理，其特點在于系統的輸入、處理、和輸出等各個處理階段都具有絕對的時間限制。對實時性提出了很高的要求[1]。而FPGA 的高速并行結構，大量的內嵌RAM 和編程的靈活性，正好為FFT 的實現提供了一個平臺。

現在已有多家FPGA 廠商提供FFT 的IP 核，但對其處理速度的研究，還只是停留在FFT 實現之后來觀測所需要的時間，來確定其處理速度。沒有一個可以在設計之前就具體估測處理速度的方式。這樣就導致在用FPGA 設計FFT 時，面臨達不到設計要求的風險。本文通過分析FPGA 實現FFT 的多種結構，研究分析了一個可計算不同結構、不同點數、不同主頻下完成一次FFT 所用時間和所用乘法器個數的計算公式。通過這個公式，可以確定滿足時間要求的FFT 的結構和確定芯片規模與型號的選取。并通過Altera 公司的軟件進行驗證。

1 蝶形算法結構分析

FFT 算法基本上分為兩大類：一類是按時間抽取(DIT)的FFT 算法，另一類是按頻率抽取(DIF)的FFT 算法。

首先，分析按時間抽取(DIT)的FFT 算法的結構。按時間抽樣的基-2 的蝶形單元算法公式為[2]：

其中A、B 和Wp都為復數，完成一次運算需要1 次復數乘法。

按時間抽樣的基-4 的蝶形單元算法公式為：[2]

其中A、B、C、D 和Wp、W2p、W3p都為復數，完成一次運算需要3次復數乘法。

由DFT 算法原理可知，對于按時間抽樣其它基-r 的蝶形單元與基-2 和基-4 具有相同的規律。因此，設按時間抽樣的其它基-r 的蝶形單元需要復數乘法次數為G1。則：

按頻率抽樣的基-2 的蝶形單元運算表達式為：[3]

其中A、B 和Wp 都為復數，完成一次運算需要1 次復數乘法。

按頻率抽樣的基-4 的蝶形單元運算表達式為：[3]

其中A、B、C、D 和Wp、W2p、W3p為復數，完成一次運算需要3 次復數乘法。

由DFT 算法原理可知，對于按頻率抽樣其它基-r 的蝶形單元與基-2 和基-4 具有相同的規律。因此，設按頻率抽樣基-r 的蝶形單元需要復數乘法次數為G2，則：

通過上面兩個結論得到，無論是按時間抽取和按頻率抽取的FFT，完成一個蝶形單元需要的復數乘法次數為：

設每個復數乘法器需要S 個實數乘法器來完成。根據高效復數乘法器的原理可知完成一個復數乘法，需要3 個實數乘法器[4]，則S=3，而一般復數乘法需要四個實數乘法器，則S=4。FPGA 中內嵌的DSP乘法器為9 位，對于數據精度為M 位的FFT，每個實數乘法器需要個[M/9]DSP 乘法器來實現，（中括號表示向無窮大取整），令：

綜上所述，不管是按時間抽樣和按頻率抽樣，我們都能得到完成一個基-r 的蝶形單元需要的DSP 乘法器個數Q 為。

2 FFT 處理器的結構分析

根據FFT 算法的特點，硬件實現的結構基本可以分為四種：順序型、級聯型、并聯型和陣列型四種結構。

在實際應用中確定FFT 的結構要考慮兩點：（1）在考慮速度的前提下，要用內嵌的DSP 乘法器來完成乘法運算。同時FPGA 中的DSP乘法器個數有限，所以FFT 的結構都采用順序型和并聯型結合的方式。（2）在考慮輸入點數N 可變的情況下，由于單獨的采用一種基-r的方式，必須滿足輸入點數N 是r 的整數倍。

采用順序型和并聯型的方式，只需要運算一級所用到的蝶形單元，其它級都復用這些蝶形單元，節省了DSP 乘法器個數。對于r 個輸入數據的基-r 蝶形單元又可以復用為2n個基-(r/2n) 的蝶形單元。例如，一個8 數據輸入的基-8 的蝶形單元可復用為2 個4 數據輸入基-4 的蝶形單元或4 個2 數據輸入基-2 的蝶形單元。這樣既節省了DSP乘法器個數，也可以滿足輸入點數可變的條件。同時采用流水線結構，這樣保證在一個時鐘周期內，所有的蝶形單元完成一次蝶形運算。在輸入RAM 和輸出RAM 之間進行數據的乒乓操作，減少了存儲單元的消耗。

比較精度為M 位的N 點的FFT，其中N=2L，L 表示總級數。第i級采用基-ri 的蝶形算法，第i 級并聯蝶形運算單元的個數為Fi。

其中i=1，2，…，logrN。

運算速度K 是計算一次FFT 所用的運算時間，對于順序型和并聯型，它們的每一級都要通過相同的蝶形單元計算，所用時間為L 個計算周期。即

而級聯型和陣列型是由多個蝶形單元同時計算，所用時間為1 個計算周期。即：

對于使用蝶形單元的個數：順序型的特點是只有一個基-r 的蝶形單元，其中r=N，所有點都由一個蝶形單元順序完成，即:

并聯型的特點是有F=N/r 個基-r 的蝶形單元，每一級都用這F 個蝶形單元運算。即:

級聯型和陣列型的特點是每一級都采用獨自的蝶形單元，所以它們使用的蝶形單元是順序型和并聯型的r 倍，而速度也是順序型和并聯型的r 倍，只有一個運算周期。

綜上所述，對于不同結構，只要已知每一級不同基的蝶形單元的個數，就能計算出FFT 處理器總共的蝶形單元的個數U。

計算公式為：

取精度M=18 位的N=16 點FFT，其中每個復數乘法需要實數乘法的個數S=3，通過不同結構在FPGA 上實現可得到下表的結論：

表1 不同結構下乘法器的使用數量和運算速度表Tab.1 The use of different structure by multiplier quantity and speed

3 FPGA 最高頻率分析

如圖1，FPGA 中計算最小時鐘周期公式為[5]：

圖1 寄存器傳送圖Fig1 Register transfer

式中：tclk為時鐘的最小周期；

Microtco為寄存器固有時鐘輸出延時；

tlogic為同步元件之間的組合邏輯延遲；

tnet為網線延遲；

Microtsu為寄存器固有時鐘建立延時；

tclkskew為時鐘偏斜。

FPGA 運行的最高頻率為最小時鐘周期的倒數。

基于FPGA 的FFT 算法實現時，FPGA 的最高頻率限制在乘法器輸入輸出寄存器之間，而tclk 主要有tlogic 和tnet 決定。所以在FPGA實現FFT 算法的時候，每執行一次乘法運算最高頻率為：

也就是執行一個運算周期的頻率。

所以執行一次FFT 的最高頻率為：

4 驗證

式（1）和式（2）分別為完成FFT 運算需要的乘法器數量計算公式和最高頻率計算公式。根據Quartus 軟件是Altera 公司推出的一款專門針對Altera 的FPGA 程序設計的一款軟件。Quartus 自帶FFT 的IP核，通過對比IP 核提供的乘法器使用數據，可以驗證本研究的計算公式的準確性。下表是Altera 的并聯型FFT 的IP 核的乘法器使用數量的對比。

表2 公式計算和Quartus 數據結果對比表Tab.2 The formula to calculate and parameter of Quaruts contrast table

5 結論

通過研究快速傅里葉變換在FPGA 中的實現，研究總結了一條經驗公式來計算需要用到的乘法器個數，以及運算速度問題。但對于大規模的FPGA 程序，不同的綜合工具，綜合得到的最高運行頻率會有不同。通過此公式可以為設計FFT 提供參考。

［1］高瞻.FFT 處理器設計及其應用研究[D].西南交通大學，2006.

［2］白德風.基于FPGA 的FFT 信號處理器的設計與實現[D].北京工業大學，2008.

［3］張竺君.基于FPGA 的可變點FFT 處理器的設計與實現[D].南京理工大學，2009.

［4］劉凌.數字信號處理的FPGA 實現[M].清華大學出版社，2008.

［5］吳繼華，王誠.Altera FPGA/CPLD 設計（高級篇）[M].人民郵電出版社，2005.