劉 智

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

0 引言

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

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

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

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

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

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

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

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

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

按頻率抽樣的基-2 的蝶形單元運(yùn)算表達(dá)式為：[3]

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

按頻率抽樣的基-4 的蝶形單元運(yùn)算表達(dá)式為：[3]

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

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

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

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

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

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

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

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

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

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

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

運(yùn)算速度K 是計(jì)算一次FFT 所用的運(yùn)算時(shí)間，對(duì)于順序型和并聯(lián)型，它們的每一級(jí)都要通過(guò)相同的蝶形單元計(jì)算，所用時(shí)間為L(zhǎng) 個(gè)計(jì)算周期。即

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

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

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

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

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

計(jì)算公式為：

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

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

3 FPGA 最高頻率分析

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

圖1 寄存器傳送圖Fig1 Register transfer

式中：tclk為時(shí)鐘的最小周期；

Microtco為寄存器固有時(shí)鐘輸出延時(shí)；

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

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

Microtsu為寄存器固有時(shí)鐘建立延時(shí)；

tclkskew為時(shí)鐘偏斜。

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

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

也就是執(zhí)行一個(gè)運(yùn)算周期的頻率。

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

4 驗(yàn)證

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

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

5 結(jié)論

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

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

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

［3］張?bào)镁?基于FPGA 的可變點(diǎn)FFT 處理器的設(shè)計(jì)與實(shí)現(xiàn)[D].南京理工大學(xué)，2009.

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

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