基于FPGA實現(xiàn)的FFT速度與規(guī)模分析

劉 智

（佛山職業(yè)技術(shù)學(xué)院，廣東 佛山 528137）

0 引言

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

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

1 蝶形算法結(jié)構(gòu)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 FFT 處理器的結(jié)構(gòu)分析

根據(jù)FFT 算法的特點，硬件實現(xiàn)的結(jié)構(gòu)基本可以分為四種：順序型、級聯(lián)型、并聯(lián)型和陣列型四種結(jié)構(gòu)。

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

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

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

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

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

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

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

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

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

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

計算公式為：

取精度M=18 位的N=16 點FFT，其中每個復(fù)數(shù)乘法需要實數(shù)乘法的個數(shù)S=3，通過不同結(jié)構(gòu)在FPGA 上實現(xiàn)可得到下表的結(jié)論：

表1 不同結(jié)構(gòu)下乘法器的使用數(shù)量和運算速度表Tab.1 The use of different structure by multiplier quantity and speed

3 FPGA 最高頻率分析

如圖1，F(xiàn)PGA 中計算最小時鐘周期公式為[5]：

圖1 寄存器傳送圖Fig1 Register transfer

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

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

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

tnet為網(wǎng)線延遲；

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

tclkskew為時鐘偏斜。

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

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

也就是執(zhí)行一個運算周期的頻率。

所以執(zhí)行一次FFT 的最高頻率為：

4 驗證

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

表2 公式計算和Quartus 數(shù)據(jù)結(jié)果對比表Tab.2 The formula to calculate and parameter of Quaruts contrast table

5 結(jié)論

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

［1］高瞻.FFT 處理器設(shè)計及其應(yīng)用研究[D].西南交通大學(xué)，2006.

［2］白德風(fēng).基于FPGA 的FFT 信號處理器的設(shè)計與實現(xiàn)[D].北京工業(yè)大學(xué)，2008.

［3］張竺君.基于FPGA 的可變點FFT 處理器的設(shè)計與實現(xiàn)[D].南京理工大學(xué)，2009.

［4］劉凌.數(shù)字信號處理的FPGA 實現(xiàn)[M].清華大學(xué)出版社，2008.

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