引言

快速傅里葉變換 (Fast Fourier Transformation，F(xiàn)FT) 作為時域和頻域轉(zhuǎn)化的基本運(yùn)算，是數(shù)字譜分析的必要前提。FFT方法是信號處理領(lǐng)域的核心算法之一，它廣泛應(yīng)用于雷達(dá)信號處理、觀測、數(shù)字通信、數(shù)據(jù)變換、定時定位處理、無線通訊、圖像處理等領(lǐng)域。為便于硬件實(shí)現(xiàn)，F(xiàn)FT 算法常采用分級運(yùn)算結(jié)構(gòu)。如今的 FFT 大多采用并行結(jié)構(gòu)，但其運(yùn)算速度往往受到數(shù)據(jù)帶寬的限制，因而需要增加成倍的存儲單元才能滿足速度要求。本文對 FFT 算法進(jìn)行了分析，基于節(jié)省運(yùn)算量、減少硬件面積和提高處理速率的考慮，給出了一個基于 FPGA的高速流水線結(jié)構(gòu)的基 4FFT 處理器的設(shè)計方法。

1 基 4FFT 算法

FFT 算法的基本思想是 ：利用 DFT 系數(shù)的特性 ( 即周期性、對稱性和可約性 ) 來合并 DFT 運(yùn)算中的某些項，把長序列 DFT 變成短序列 DFT，從而減少其運(yùn)算量，達(dá)到提高速度的目的。一般的 FFT 算法可以分為兩類 ：第一類對時間，對時間序列 x(n) 進(jìn)行逐次分解，稱為時域抽取 FFT 法(Decima-tion-In-Time-FFT，DIT-FFT)；第二類對頻率，主要對傅里葉變換序列 X(k) 進(jìn)行分解，稱為頻域抽取 FFT 法 (Decimation-In-Frequency-FFT，DIF-FFT)。本設(shè)計采用 DIT-FFT 法進(jìn)行設(shè)計。

1.1 基 4 DIT-FFT 算法

DFT 將時域信號變換成頻域信號后，長度為 N 的有限長序列 x(n) 的離散傅里葉變換可以表示為 ：

基 4 DIT-FFT 算法的基本原理是 ：將一個 N 點(diǎn)的 FFT分解為 4 個 N/4 點(diǎn)的序列，再分別進(jìn)行 DFT 計算 ；然后再將每個N/4點(diǎn)進(jìn)一步分解為 4 個N/16點(diǎn)的計算，依此類推。同理，對于多點(diǎn)數(shù)還可以進(jìn)行多級分解。其基 4 蝶形運(yùn)算如下：

其中，X(K), X(k+N/4), X(k+2N/4), X(k+3N/4) 是蝶形運(yùn)算后的結(jié)果?；?4 蝶形運(yùn)算單元可以用圖 1 表示。

1.2 算法比較與選擇

一般常用乘法次數(shù)和加法次數(shù)來衡量一個算法的性能。例如，對于基 4FFT 算法的描述為 ：每個蝶形運(yùn)算為 3 次復(fù)數(shù)乘法，每級共有 N/4 個基 4 蝶形單元，共有 m 級 ( 其中，N=4m)。表 1 所列是 4 種常用基數(shù)算法運(yùn)算量的比較，表中，l=log2N。

一般情況下，基數(shù)越高，總計算量就越少，但是，控制復(fù)雜性也會相應(yīng)提高。就復(fù)雜性而言，基 2 算法最容易控制，操作簡單 ；基 4 算法控制稍許復(fù)雜，但與基 2 相差不大 ；基 8和基 16 算法的控制復(fù)雜度與基 4 相比，難度會增大很多。綜合考慮運(yùn)算量與控制復(fù)雜度，本文選擇基 4 算法來實(shí)現(xiàn)設(shè)計。

2 基 4 FFT 算法的硬件實(shí)現(xiàn)

現(xiàn)今的 FFT 算法大多采用并行結(jié)構(gòu)來實(shí)現(xiàn)。由于并行結(jié)構(gòu)的數(shù)據(jù)輸入大多是串行連續(xù)輸入的，需要進(jìn)入串并轉(zhuǎn)換，這樣會浪費(fèi)大量時間，尤其是在一些實(shí)時高速處理的場合，并行結(jié)構(gòu)難以適應(yīng)。而流水線結(jié)構(gòu)在實(shí)時性和連續(xù)性等方面具有天然的優(yōu)勢，所以，本設(shè)計采用流水線結(jié)構(gòu)來完成設(shè)計。

FFT 算法的流水線結(jié)構(gòu)一般分為 3 種：第一種是單路延時轉(zhuǎn)接器結(jié)構(gòu) (Single-path Delay Commutator，SDC) ；第二種是多路延時轉(zhuǎn)接器結(jié)構(gòu) (Multi-path Delay Commutator，MDC) ；第三種是單路延時反饋轉(zhuǎn)接器結(jié)構(gòu) (Single-path Delay Feedback，SDF)。表 2 所列是流水線結(jié)構(gòu) FFT 各種指標(biāo)的比較，其中，k=log4N。

從表 2 可以看出，在運(yùn)算量上，SDC 占優(yōu)勢，但控制復(fù)雜度較高。綜合考慮運(yùn)算量、存儲單元及控制復(fù)雜度，SDF是最優(yōu)的選擇。因此，本設(shè)計采用 SDF 結(jié)構(gòu)。

本文設(shè)計實(shí)現(xiàn)的一個 1024 點(diǎn)流水線結(jié)構(gòu)基 4-SDF FFT的結(jié)構(gòu)框圖如圖 2 所示。

2.1 蝶形運(yùn)算單元

可以將蝶形運(yùn)算分割為下式 ：

其中，是蝶形運(yùn)算后一狀態(tài)的結(jié)果。經(jīng)過分割后，可以看出，整個蝶形運(yùn)算只有 a+b, a-b, a+jb, a-jb 四種計算，分別采用復(fù)數(shù)加法與減法器就可以完成蝶形運(yùn)算，從而可大大簡化設(shè)計和實(shí)現(xiàn)的復(fù)雜度。圖 3 與圖 4 分別是蝶形單元所用到的復(fù)數(shù)加法器與減法器的框圖。

2.2高效乘法器

一般兩個復(fù)數(shù)分別為A=a+jb, B=C+jd的復(fù)數(shù)相乘的計 算過程為：

AB=(a+j b)(c+j d)=(ac-bd)+j(ad+bc)=Fre+j Yim                      (4)

其中，Yre為 AB 結(jié)果的實(shí)部，Yim為 AB 的虛部。

顯然，一次復(fù)數(shù)乘法共需要4次實(shí)數(shù)乘法和3次實(shí)數(shù)加 法，但是，如果進(jìn)行一定的變換，就可以減少實(shí)數(shù)乘法的次數(shù)。 即：

Yx=ac-bd=ac-ad+ad-bd=(c-d)a+(a-b)d                                      (5)

Yim=ad+bc=ad-bd+bd+bc=(c+d)b+(a-b)d                                 (6)

在計算前，將c-d,c+d,a-b的結(jié)果放在存儲單元中，這樣, 一次復(fù)數(shù)乘法就只需要3次實(shí)數(shù)乘法與5次實(shí)數(shù)加法，顯然 會大大節(jié)約硬件開銷，同時也提高了計算速度。

本設(shè)計采用有符號數(shù)BOOTH編碼的乘法器，根據(jù)數(shù)據(jù) 量化，利用10位的被乘數(shù)和10位的乘數(shù)進(jìn)行運(yùn)算。其計算 結(jié)果乘積需要經(jīng)過飽和，最后取10位結(jié)果保留。

2.3旋轉(zhuǎn)因子存儲

本設(shè)計需要將旋轉(zhuǎn)因子向量= cos i +jsin i的實(shí)部和 虛部存儲在寄存器中，并利用查找表方式實(shí)現(xiàn)向量旋轉(zhuǎn)運(yùn)算。 這樣只需要取在1/8圓內(nèi)，即［0，…，n/4］之間的旋轉(zhuǎn)因子, 其他的旋轉(zhuǎn)因子都是這1/8圓周區(qū)域內(nèi)旋轉(zhuǎn)因子的變換。按照 旋轉(zhuǎn)因子的周期性和對稱性，其他區(qū)域的旋轉(zhuǎn)因子，可通過 交換實(shí)部虛部和改變正負(fù)號來得到。

例如：設(shè)點(diǎn)A為［0,…，”4］的一個旋轉(zhuǎn)因子，假設(shè)它 寫成矢量形式是A=cosx+jsinx,那么，映射到4個象限內(nèi)的 另外7個投影則是：

sinx+jcosx, -cosx +jsinx, -sinx +jcosx, -cosx+j(-sinx), -sinx+j(-cosx), sinx+j(-cosx), cosx+j(-sinx)

旋轉(zhuǎn)因子一共有8個數(shù)據(jù)。只需要將這樣的一個數(shù)據(jù)的 實(shí)部和虛部的數(shù)值(不包括符號)分別存儲在寄存器同一個地 址的數(shù)據(jù)存儲單元里，就可以在取出這個數(shù)據(jù)后，通過變換 安排好它的實(shí)部和虛部，然后重新安排它的正負(fù)號，就可得到 其他在該級運(yùn)算中所需要的另外7個旋轉(zhuǎn)因子。

2.4控制單元

每級蝶形運(yùn)算單元都有自己的控制單元，這主要是控制 蝶形運(yùn)算單元的工作模式，判斷是否進(jìn)入流水操作，操作數(shù) 的選取，RAM的選通，復(fù)數(shù)乘法的選通，以及產(chǎn)生RAM和 旋轉(zhuǎn)因子的地址。另外，控制單元還需要產(chǎn)生使能信號，以供 下一級的輸入使用。

對于蝶形單元的控制，主要是控制其工作模式。在蝶形 單元中，輸入數(shù)據(jù)先存儲到第一個存儲單元中，同時從第一個 存儲單元的相同地址中取出上一次蝶形運(yùn)算的結(jié)果，然后把第 二、三段數(shù)據(jù)存儲到第二、三個存儲單元中，同時讀出相應(yīng)的 結(jié)果；當(dāng)最后的一段數(shù)據(jù)到來時，從存儲單元中讀取相應(yīng)的 數(shù)據(jù)進(jìn)行蝶形運(yùn)算，同時輸出第一個運(yùn)算結(jié)果，并把其他3 個結(jié)果同址寫回三個存儲單元相對應(yīng)的位置。

對于旋轉(zhuǎn)因子的控制，由于在寄存器中的旋轉(zhuǎn)因子都是 無符號數(shù)，因此在進(jìn)行復(fù)數(shù)乘法之前，需要根據(jù)控制單元的 指示，重新安排它的正負(fù)號。

2.5輸出數(shù)據(jù)地址轉(zhuǎn)換

在系統(tǒng)中，F(xiàn)FT輸出的數(shù)據(jù)也許是給下一級使用。特別是 在OFDM系統(tǒng)中，也需要找回原來的順序。由于輸出數(shù)據(jù)的 地址是亂序，所以需要有地址產(chǎn)生模塊給數(shù)據(jù)產(chǎn)生地址，以 方便后級使用。輸出數(shù)據(jù)地址轉(zhuǎn)換應(yīng)按照00、01、10、11輸入, 并按照11、10、01、00順序輸出。

3仿真、綜合及FPGA實(shí)現(xiàn)

本文設(shè)計實(shí)現(xiàn)了一個1 024點(diǎn)的基4 FFT處理器，數(shù)據(jù) 處理精度為10位。采用Verilog HDL語言描述整個設(shè)計，并 編寫測試平臺。筆者利用Modelsim SE 6.5對本文的設(shè)計進(jìn)行 了功能仿真驗(yàn)證，運(yùn)算結(jié)果與Matlab計算的結(jié)果一致，從而 證明了本文算法的正確性。

在FPGA實(shí)現(xiàn)方面，本文選用Xilinx的Spartan-3E-XC- 3S500E芯片,該器件的內(nèi)部含有4個數(shù)字時鐘管理器(DCM), 73 kB 的分布 RAM, 360 kB 的 block RAM, 4 個 18X18 的專 用乘法器(Dedicated Multipliers)單元，其中乘法器的工作頻 率可達(dá)到300 MHz。綜合布線工具均采用Xilinx的設(shè)計平臺ISE9.1,表3所列是其該處理器與一些現(xiàn)有文獻(xiàn)中的FFT處 理器核的性能比較，可見本設(shè)計具有一定的優(yōu)勢。

4結(jié)語

本文通過采用SDF流水線結(jié)構(gòu)設(shè)計并實(shí)現(xiàn)了一個基于 FPGA的高速基4 FFT處理器，F(xiàn)PGA內(nèi)部資源消耗明顯減少, 并保持了比較高的工作頻率，能滿足信號處理系統(tǒng)實(shí)時處理的 要求。從實(shí)現(xiàn)結(jié)果可以看出，與并行結(jié)構(gòu)的FFT處理器相比, 流水線結(jié)構(gòu)的處理速度更快。該處理器可適用于超高速場合 以及需要密集型數(shù)字信號處理的領(lǐng)域，比如數(shù)字通信、數(shù)據(jù) 變換、定時定位處理、無線通訊、圖像處理等。

20210915_6141736b491a4__基于FPGA的高速基4FFT設(shè)計與實(shí)現(xiàn)