基于Stratix系列FPGA的FFT模塊設計與實現(xiàn)

1 引言

　　對于地面上的遠距離微波通信，當通信距離超過一定范圍時，電磁波傳播會受到地面的阻擋，隨著通信距離的增加通信信號則會衰減。為了延長通信距離和提高通信質(zhì)量，需要在通信二地之間設立若干微波中繼設備(例如微波接力機)，進行電磁波轉(zhuǎn)接并對信號進行逐段接收和放大后再發(fā)送給下一段。在微波接力通信中，通常采用擴頻方式提高系統(tǒng)的抗干擾能力。但是，擴頻系統(tǒng)過寬的頻帶帶寬很容易在通信設備密集的地方受到其他設備的干擾(窄帶干擾)。所以在微波接力機工作過程中，需要對接收信號中的窄帶干擾信號進行快速識別并利用相應的自適應陷波等技術(shù)對窄帶干擾進行抑制。由于在頻域上窄帶干擾的功率譜呈現(xiàn)尖峰狀，而擴頻信號大致呈現(xiàn)平坦特性且并容易識別。所以要在微波接力機中設計FFT模塊用于計算信號的功率譜。
對實現(xiàn)FFT的工程，目前通用的方法是采用DSP、FFT處理電路及FPGA。用DSP實現(xiàn)FFT的處理速度較慢，不能滿足某些高速信號實時處理的要求；專用的FFT處理器件雖然速度較快，但是價格相對昂貴且外圍電路相對復雜；采用新一代的FP-GA來實現(xiàn)FFT兼有二者的優(yōu)點。FPGA資源豐富、易于借助并行流水的特點來實現(xiàn)FFT，不但性能穩(wěn)定、經(jīng)濟性好，而且可以大大縮短計算的耗時。以Altera公司的Stratix系列FPGA為例，它具有多達79 040個邏輯單元、7 MB的嵌入式存儲器、優(yōu)化的數(shù)字信號處理器和高性能的I/O能力，非常方便以全并行流水方式進行FFT處理。

　　筆者選用Stratix系列中的EPlS25型FPGA來實現(xiàn)FFT，在系統(tǒng)主頻大于52 MHz的環(huán)境下穩(wěn)定工作后，完成1次256點的FFT所需要的時間小于5μs，完成1次1024點的FFT所需時間小于20μs，完全滿足實時處理的要求。

2 模塊的設計與實現(xiàn)

2.1 FFT算法選擇

　　自從1965年J.W.Tuky和T.W.Coody在《計算機數(shù)學》上發(fā)表了著名的《機器計算傅立葉級數(shù)的一種算法》論文后，經(jīng)過幾十年來的不斷改進，形成了很多FFT的高效算法。這些算法基本上分為二大類：時域抽取法FFT(DIT-FFT)和頻域抽取法FFT(DIF-FFT)。時域抽取法是把變換模塊的輸入數(shù)據(jù)在時域上按一定的倒序規(guī)則打亂，經(jīng)過變換后，輸出的FFT頻域信號是順序排列的。而頻域抽取法是把變換模塊的輸入數(shù)據(jù)在時域上按順序輸入，經(jīng)過變換后，輸出的FFT頻域信號按照倒序列規(guī)則輸出。根據(jù)運算基的不同，又可以分為基2、基4、基8及混合基算法等。
在該變換模塊的處理過程中，可以在預加窗單元方便地完成倒序操作，而且在全并行流水方式處理的過程中，采用時域抽取可以充分利用原址存儲，節(jié)省內(nèi)存。所以，在設計中選擇簡單實用的時域抽取基2FFT算法。

2.2 FFT模塊與外部電路的接口

　　FFT模塊與外部電路的接口如圖1所示。圖中，輸入信號Xin為復數(shù)零中頻信號，數(shù)據(jù)寬度為18bit，編碼格式為二進制補碼。Xout是復數(shù)變換輸出信號，數(shù)據(jù)寬度為18 bit，編碼格式也是二進制補碼。CLK和HCLK分別是系統(tǒng)的主時鐘和2倍時鐘。HCLK主要用于數(shù)據(jù)的輸入、輸出。當CLK為‘1’時，由Xin在HCLK的上升沿輸入實部數(shù)據(jù)并在Xout輸出變換數(shù)據(jù)的實部；當CLK為‘O’時，由Xin在HCLK的上升沿輸入虛部數(shù)據(jù)并在Xout輸出變換數(shù)據(jù)的虛部。iFSyne為變換輸入幀同步控制信號，oFSync為變換輸出幀同步控制信號。2個信號為‘1’時分別表示模塊輸入/輸出變換幀的第1個數(shù)據(jù)開始輸入/輸出。

2.3 全并行流水方式的實現(xiàn)

　　在FFT工作方式的設計上，充分利用FPGA內(nèi)嵌乘法器和存儲器資源豐富的特點．采用全并行的流水工作方式。如圖2所示，圖中N為進行FFT運算的點數(shù)，M=log2N。以N=256,M=8為例，當系統(tǒng)穩(wěn)定工作之后，在256個時鐘之內(nèi)，同時有l(wèi)O組數(shù)據(jù)在做不同的運算。當?shù)?組數(shù)據(jù)輸入的時候，第10組數(shù)據(jù)正在輸出，而中間的8組數(shù)據(jù)正在進行各級蝶形運算。因此，當模塊進入穩(wěn)定工作狀態(tài)后，每隔256個時鐘就有一組數(shù)據(jù)完成256點的FFT，從輸出RAM中輸出。

2.4 FFT變換模塊的內(nèi)部設計

　　FFT內(nèi)部變換模塊的設計如圖3所示。下面以N=256點的FFT為例分別予以說明。

2.4.1 加窗并倒序存儲單元

　　為了減少時域截斷造成的頻譜泄漏誤差，在進行FFT變換前應對模塊輸入的數(shù)據(jù)進行加窗處理?？紤]到本模塊主要用來分析疊加有窄帶干擾的擴頻信號，它要求精確給出每個窄帶干擾的中心頻率及其干擾強度的相對大小，所以，這里選用帶外衰減為80 dB的Chebyshev窗以獲取良好的頻譜效果。經(jīng)過加窗之后的數(shù)據(jù)按照倒序的規(guī)則存儲在RAM中，等待進入蝶形運算單元進行運算。

2.4.2 控制單元

　　控制單元是整個FFT變換模塊的核心。它主要負責以下二方面的工作。

(1)提供各個模塊的運算使能

　　當檢測到輸入口的iFSync信號為高電平后，立即啟動“加窗并倒序存儲單元”和“窗因子ROM”單元進行數(shù)據(jù)輸入、加窗、倒序存儲處理。在256個時鐘之后，啟動“各級蝶形運算”單元，并控制地址產(chǎn)生單元產(chǎn)生當前需要的各類地址。中間各級蝶形運算的使能由上l級蝶算單元產(chǎn)生。在第8級運算結(jié)束時，提供數(shù)據(jù)輸出的標志oFSync，并控制輸出RAM同步輸出數(shù)據(jù)。

(2)產(chǎn)生各級運算過程中所需的地址

　　倒序地址：用模為N的同步計數(shù)器的輸出來實現(xiàn)，把當前計數(shù)器輸出的高位與低位的對應位進行全部對調(diào)即可得到當前數(shù)據(jù)的倒序地址。
各級運算的地址：把RAM取數(shù)地址和ROM取數(shù)地址對應起來。原則是先把1個旋轉(zhuǎn)因子所對應的所有數(shù)據(jù)計算完畢再轉(zhuǎn)到下1個旋轉(zhuǎn)因子所對應的數(shù)據(jù)上。這樣的話，可以在產(chǎn)生ROM地址的同時產(chǎn)生所有RAM取數(shù)的地址。把二者的地址建立關(guān)聯(lián)之后，可以使RAM數(shù)據(jù)和ROM數(shù)據(jù)嚴格對應起來。

2.4.3 RAM模塊

　　在256點的FFT中，要進行8級蝶算，對全并行的工作方式而言需要8個不同的RAM來存儲各級的中間結(jié)果。其中，第8級的RAM可以作為輸出RAM。再加上前面加窗和倒序的1個RAM，整個系統(tǒng)共需要9個RAM。對于256點的復數(shù)，把實部和虛部分開共需要512個存儲單元。在某一級的蝶算中，由于信號及運算的延遲，不可能就在256個時鐘之內(nèi)完成本級運算，而下一組的數(shù)據(jù)在256個時鐘之后就要進行本級運算并將結(jié)果存儲在該RAM中，這樣就有可能造成數(shù)據(jù)還沒有被完全讀取就被新數(shù)據(jù)覆蓋的沖突。為了確保在全并行工作方式中實現(xiàn)數(shù)據(jù)的準確存取，可以把9個RAM都設置成1024?8 bit的存儲格式，即：把每個RAM分為二部分，地址為0～511的為前半部分，地址為512～l 023的為后半部分，用一個MSB的信號作為地址最高位來控制前后二部分存儲器。當?shù)?組數(shù)據(jù)進行本級運算時，其結(jié)果保存在RAM的前半部分；256個時鐘之后，對MSB求反，并以此控制把第I+1組數(shù)據(jù)進行本級運算的結(jié)果寫入RAM的后半部分，此時對第1組數(shù)據(jù)的讀取在前半部分進行，互不沖突。Altera的FPGA器件里有豐富的RAM資源，采用雙端口RAM可以很方便地實現(xiàn)上述操作。

2.4.4 ROM模塊

　　整個模塊共需3個ROM，一個用來存儲Chebyshev窗因子，另外二個分別用來存儲旋轉(zhuǎn)因子的實部和虛部。事先在MATLAB中計算出這些因子，并將它們按照*.mif文件格式輸出。在QuartusⅡ軟件中，例化3個ROM，并把由MATLAB產(chǎn)生的*.mif文件寫入各自ROM的初始化文件中，完成對ROM的初始化工作。

2.4.5 蝶形運算單元

(1)基本蝶形運算單元。把復數(shù)運算分解為實數(shù)運算之后，每個基本的蝶形運算單元都可由4個乘法器、1個加法器和1個減法器構(gòu)成。其中，乘法器是決定系統(tǒng)運算速度的關(guān)鍵因素。對256點FFT在全并行的工作方式下，最多要求在同一時鐘并行完成33個18x18 bit的乘法運算。而EPlS25系列FPGA有非常豐富的乘法器資源，僅DSP就可以并行完成40個18x18 bit的乘法運算，完全滿足系統(tǒng)的要求。

(2)可化簡的蝶形運算單元。在對各級蝶形進行研究的基礎上發(fā)現(xiàn)，第1級和第2級的蝶形經(jīng)過化簡完全可以不用進行乘法操作。
第1級只有1個旋轉(zhuǎn)因子won，其實部為1、虛部為O，代入基本蝶形運算單元化簡之后可得：
mx1=xl+x2；my1=yl+y2
mx2=x1-x2；my2=y1-y2
其中：x1、x2為輸入數(shù)據(jù)實部，y1、y2為輸入數(shù)據(jù)虛部，mx1、mx2為變換之后的數(shù)據(jù)實部，my1、my2為變換之后的數(shù)據(jù)虛部。
第2級有2個旋轉(zhuǎn)因子，won和w64n，對won可以沿用第一級的簡化方法。
對于w64n，其實部為0、虛部為-l，代入基本蝶算單元化簡之后可得：mx1=x1+y2；my1=y1+x2；mx2=x1-xz；my2=y1+x2這樣，總共8級的蝶形運算有2級可以不用乘法器和存儲旋轉(zhuǎn)因子的ROM，節(jié)省了25％的乘法器和ROM資源。

2.5 誤差的分析與控制

　　對FPGA而言，采用浮點運算帶來的硬件開銷太大。而如果采用文獻[3]所提出的塊浮點防溢出方案，在每一級蝶形運算結(jié)束之后，都需要找出該級計算結(jié)果中的最大值來判斷溢出的狀態(tài)，并以此確定進行下一級運算時每個數(shù)據(jù)需要移位的位數(shù)。這對全并行的工作方式而言，意味著每一級數(shù)據(jù)都會帶來更大的延遲，影響整個運算的速度。而對定點運算而言，雖然存在有限字長效應的影響，但是，只要對數(shù)據(jù)進行適當?shù)囊莆惶幚砭涂梢苑乐挂绯?；在?shù)據(jù)舍棄時，進行類似4舍5入的運算就可以有效的控制誤差。在綜合考慮之后，系統(tǒng)采用定點運算方案。在定點運算中，誤差主要體現(xiàn)在以下兩方面：

(1)乘法截斷誤差。2個18位的數(shù)據(jù)相乘得到36位的積，把該積舍入為18位就會產(chǎn)生誤差。由于來自零中頻的18位數(shù)據(jù)實際表征的是模值不大于‘1’的復小數(shù)，所以相乘不會產(chǎn)生溢出。去掉次高位多余的符號位并截去后17位。當被截去的各位是‘1’的時候,誤差最大；被截去的各位為‘O’時，沒有誤差。對被截去的部分作類似4舍5入的處理，第20位為‘1’則向上進位，為‘O’則直接舍去，可以有效減小誤差。

(2)加減法溢出誤差。2個18位的數(shù)據(jù)相加減得到19位的結(jié)果，在進行下一級運算之前，必須舍去l位,對舍棄的這l位也進行上述的4舍5入運算。2個小數(shù)的加減運算而言，把結(jié)果全部右移1位就可以防止溢出。

3 波形仿真與性能分析

波形仿真選用的輸入信號為
x(n)=Xxexp[j?03+2x127xnxπ)/256]
式中。X根據(jù)測試的需要分別取18 bit信號的最大值和達到80 dB信噪比所需的最小值13，n的取值范圍為0：255。設計工具選用VHDL93版硬件描述語言，在QuartusⅡ4.1平臺上進行邏輯綜合和時序分析，把仿真結(jié)果保存為*.tbl文件格式。在MATLAB中,讀取*.tbl文件，并與MATLAB的計算結(jié)果進行比較。由于8級運算都作了右移1位的處理,所以實際結(jié)果比用MATLAB的計算結(jié)果縮小256倍。把MATLAB的計算結(jié)果縮小256倍與0uartusⅡ4.1的計算結(jié)果比較，如圖4所示。圖中，左上圖為原始序列，右上圖為用MATLAB計算的結(jié)果，右下圖為用FPGA計算的實際結(jié)果。在左下圖中，把二個結(jié)果進行局部放大，MATLAB的計算結(jié)果用實線表示,Quartus4.1的仿真結(jié)果用“+”表示?？梢钥闯龆M結(jié)果的吻合性非常好，驗證了程序的正確性。仿真采用60 MHz系統(tǒng)主頻，在系統(tǒng)進入穩(wěn)定狀態(tài)之后(經(jīng)過38.34μs)，每完成1次256點FFT所用時間為4.26μs。對EPlS25器件資源占用情況為：邏輯單元使用15％,內(nèi)部存儲器使用18％,專用DSP使用62.5％。雖然專用DSP塊使用較多，但是邏輯單元使用得很少,可以用邏輯單元來構(gòu)成18x18的乘法器和專用DSP一起完成更多的并行乘法運算。這說明系統(tǒng)還具有很好的可擴展性，要完成更多點數(shù)的FFT,只需增加相應蝶形運算的級數(shù)即可。

　　從結(jié)果可以看出，由于運算中采用有效措施防止誤差和溢出，在最大數(shù)據(jù)運算時沒有溢出，而且最終運算結(jié)果的誤差小于10-9。在用達到80 dB信噪比所需最小數(shù)據(jù)進行運算時，也有很好的分辨率。

4 結(jié)束語

　　本文討論了微波接力機中FFT模塊的設計與實現(xiàn)過程。全部電路設計已經(jīng)過功能仿真、邏輯綜合、時延分析并成功下載到FPGA中投入實踐應用。實踐應用表明用Stratix系列FPGA實現(xiàn)FFT的速度快、穩(wěn)定性高、易于擴展。在微波接力通信,特別是在接力機對窄帶干擾快速識別的應用中有很大的優(yōu)越性。