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

引言

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

1 基 4FFT 算法

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

1.1 基 4 DIT-FFT 算法

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

基 4 DIT-FFT 算法的基本原理是 ：將一個(gè) N 點(diǎn)的 FFT分解為 4 個(gè) N/4 點(diǎn)的序列，再分別進(jìn)行 DFT 計(jì)算 ；然后再將每個(gè)N/4點(diǎn)進(jìn)一步分解為 4 個(gè)N/16點(diǎn)的計(jì)算，依此類推。同理，對(duì)于多點(diǎn)數(shù)還可以進(jìn)行多級(jí)分解。其基 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ù)來(lái)衡量一個(gè)算法的性能。例如，對(duì)于基 4FFT 算法的描述為 ：每個(gè)蝶形運(yùn)算為 3 次復(fù)數(shù)乘法，每級(jí)共有 N/4 個(gè)基 4 蝶形單元，共有 m 級(jí) ( 其中，N=4m)。表 1 所列是 4 種常用基數(shù)算法運(yùn)算量的比較，表中，l=log2N。

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

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

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

FFT 算法的流水線結(jié)構(gòu)一般分為 3 種：第一種是單路延時(shí)轉(zhuǎn)接器結(jié)構(gòu) (Single-path Delay Commutator，SDC) ；第二種是多路延時(shí)轉(zhuǎn)接器結(jié)構(gòu) (Multi-path Delay Commutator，MDC) ；第三種是單路延時(shí)反饋轉(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)勢(shì)，但控制復(fù)雜度較高。綜合考慮運(yùn)算量、存儲(chǔ)單元及控制復(fù)雜度，SDF是最優(yōu)的選擇。因此，本設(shè)計(jì)采用 SDF 結(jié)構(gòu)。

本文設(shè)計(jì)實(shí)現(xiàn)的一個(gè) 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)過(guò)分割后，可以看出，整個(gè)蝶形運(yùn)算只有 a+b, a-b, a+jb, a-jb 四種計(jì)算，分別采用復(fù)數(shù)加法與減法器就可以完成蝶形運(yùn)算，從而可大大簡(jiǎn)化設(shè)計(jì)和實(shí)現(xiàn)的復(fù)雜度。圖 3 與圖 4 分別是蝶形單元所用到的復(fù)數(shù)加法器與減法器的框圖。

2.2高效乘法器

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

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)

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

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

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

本設(shè)計(jì)需要將旋轉(zhuǎn)因子向量= cos i +jsin i的實(shí)部和 虛部存儲(chǔ)在寄存器中，并利用查找表方式實(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)因子的周期性和對(duì)稱性，其他區(qū)域的旋轉(zhuǎn)因子，可通過(guò) 交換實(shí)部虛部和改變正負(fù)號(hào)來(lái)得到。

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

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

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

2.4控制單元

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

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

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

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

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

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

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

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

4結(jié)語(yǔ)

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

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