基于FPGA的移位寄存器流水線結構FFT處理器設計與實現

2010-04-12 00:00:00郝小龍,韋高,劉娜

現代電子技術 2010年9期

摘要:設計實現了基于FPGA的256點定點FFT處理器。處理器以基-2算法為基礎，通過采用高效的兩路輸入移位寄存器流水線結構，有效提高了碟形運算單元的運算效率，減少了寄存器資源的使用，提高了最大工作頻率，增大了數據吞吐量，并且使得處理器具有良好的可擴展性。詳細描述了具體設計的算法結構和各個模塊的實現。設計采用Verilog HDL作為硬件描述語言，采用Quartus Ⅱ設計仿真工具進行設計、綜合和仿真，仿真結果表明，處理器工作頻率為72 MHz，是一種高效的FFT處理器IP核。

關鍵詞:FFT處理器; 流水線結構; FPGA; Quartus Ⅱ; Verilog HDL

中圖分類號:TP391 文獻標識碼:A

文章編號:1004-373X(2010)09-0172-05

Design and Implementation on FFT Processor of FPGA-based

Shift Register Pipelined Architecture

HAO Xiao-long， WEI Gao， LIU Na

(School of Electronic and Information，Northwestern Polytechnical University， Xi’an 710129， China)

Abstract:A 256 point FPGA-based fixed-point FFT processor is designed. The processor is based on radix-2 DIF algorithm. The operating efficiency of butterfly arithmetic union is enhanced， the use of register is redaced and the maximum operating frequency is improved and the data throughput is enhanced by adopting an efficient shift register pipelined architecture. The designed FFT processor also has good scalability. The algorithm architecture and the realization of each module are described in detail. The design uses Verilog HDL as the hardware description language， and uses Quartus Ⅱ for the design， synthesis and simulation. The simulation results show that the processor is a high efficient FFT processor IP core with 72 MHz work frequency.

Key words:FFT processor; pipelined architecture; FPGA; Quartus Ⅱ; Verilog HDL

0 引言

快速傅里葉變換(FFT)在雷達、通信和電子對抗等領域有廣泛應用。近年來現場可編程門陣列(FPGA)的飛速發展，與DSP技術相比，由于其并行信號處理結構，使得FPGA能夠很好地適用于高速信號處理系統。由于Altera等公司研制的FFT IP核，價錢昂貴，不適合大規模應用，在特定領域中，設計適合于自己領域需要的FFT處理器是較為實際的選擇。

本文設計的FFT處理器，基于FPGA技術，由于采用移位寄存器流水線結構，實現了兩路數據的同時輸入，相比傳統的級聯結構，提高了蝶形運算單元的運算效率，減小了輸出延時，降低了芯片資源的使用。在OFDM系統的實際應用中[1]，因它可以采用快速傅里葉變換，能方便快捷地實現調制和解調，故結合MIMO技術，設計的FFT處理器結構，可以很好地應用于2根天線的MIMO-OFDM系統中。

1 FFT處理的應用及DIF FFT算法原理

圖1給出一個2根天線MIMO-OFDM系統中FFT的使用。快速傅里葉變換算法基本上分為兩大類:時域抽取(DIT)和頻域抽取(DIF)[2]，這里設計的FFT處理器采用基-2 DIF算法。

圖1 FFT處理器應用于一個2根天線的MIMO-OFDM系統

對于N點序列x(N)，其傅里葉變換定義為:

X(k)=∑N-1n=0x(n)WnkN， k=0，1，2，…，N-1，

WN=e-j2πN(1)

將x(n)分成上、下兩部分，得:

X(k)=∑N/2-1n=0x(n)WnkN+∑N/2-1n=0x(n+N/2)WnkNWNk/2N(2)

分別令k=2r，k=2r+1，r=0，1，2，…，N/2-1，得:

X(2r)=∑N/2-1n=0[x(n)+x(n+N2)]WnrN/2(3)

X(2r+1)=∑N/2-1n=0[x(n)-x(n+N2)]WnrN/2WnN(4)

這樣將兩個N點的DFT分成兩個N/2點的DFT，分的方法是將X(k)按序號k的奇、偶分開。通過這種方式繼續分下去，直到得到兩點的DFT。采用DIF方法設計的FFT，其輸入是正序，輸出是按照奇偶分開的倒序。

2 移位寄存器流水線結構的FFT

在傳統流水線結構的FFT中，需要將全部數據輸入寄存器后，可開始蝶形運算。在基-2 DIF算法中[3]可以發現，當前N/2個數據進入寄存器后，運算便可以開始，此后進入的第N/2+1個數據與寄存器第一個數據進行蝶形運算，以此類推。

由于采用頻域抽取法，不需要對輸入的數據進行倒序處理，簡化了地址控制，這樣，可以采用移位寄存器的方式，依次將前N/2個數據移入移位寄存器，在N/2+1時刻，第一個數據移出移位寄存器，參與運算。相對于傳統的RAM讀寫方式，采用移位寄存器存儲結構綜合后的最大工作頻率為500 MHz，遠大于RAM方式的166 MHz。

當移位寄存器相繼有數據移出時，在移位寄存器中會出現空白位。此時，引入第二路數據，在第一路數據依次移出進行蝶算時，第二路數據依次補充到移位寄存器的空白位中，為運算做準備。通過這樣一種類似“乒乓操作”的結構，可以使蝶形運算模塊中的數據不間斷地輸入，運算效率達到100%。不同于傳統的“乒乓操作”結構，由于使用移位寄存器，不需要兩塊RAM，可以省掉一半的寄存器。圖2為256點FFT處理器的第一級結構。

基于上述基本原理，將這種移位寄存器結構擴展到整個FFT系統的各級，可以發現各級使用的移位寄存器數量是遞減的。現使用一個8點結構來進行說明。

如圖3所示，數據由輸入1和輸入2進入第一級。通過開關進行選通控制。由于是N=8的運算，所以各級分別加入4級、2級和1級的移位寄存器。

圖2 N=256的FFT處理器的第一級結構

圖3 N=8的FFT處理器整體結構

分兩路來說明運算過程:

將K1打到位置①，第一路數據進入移位寄存器，待第一路的前4個數據存入4級移位寄存器后，第一路進入的第5個數據與移位寄存器移出的第1個數據進行蝶形運算。

由于輸出結果有上下兩路，第二級是一個四點的DFT，所以對于上路的輸出結果x0(0)+x0(4)類似于第一級，直接存入下一級寄存器，為四點運算做準備，下路的輸出，(x0(0)-x0(4))W0N先存入本級2級移位寄存器中，等到上路的四點運算開始，第二級的移位寄存器有空白位時，移入第二級，為下路的四點運算做準備。所以第一級蝶形運算上路輸出前N/4=2個進入下一級寄存器，下路輸出的數據依次存入本級移位寄存器中。

當第一級的輸出前N/4=2個數據x0(0)+x0(4)和x0(1)+x0(5)存入第二級移位寄存器時，運算便可以開始，這時開關K2打到位置②，此時第一級上路輸出的數據x0(2)+x0(6)，即第一級上路輸出的第三個數據與第二級移位寄存器移出的第一個數據，即x0(0)+x0(4)進行蝶形運算，輸出的第四個數據x0(3)+x0(7)與x0(1)+x0(5)進行蝶算。在這個運算過程中，第一級的2級移位寄存器移出數據依次移位存入到第二級的移位寄存器產生的空白位中。

兩個時鐘后，第一級上路輸出的四個數據完成了蝶形運算，K2打到位置①，在接下來的兩個時鐘里，第一級中2級移位寄存器的輸出依次與此時第二級中2級移位寄存器的輸出數據進行蝶形運算，即(x0(0)-x0(4))W0N與(x0(2)-x0(6))W2N，(x0(2)-x0(6))W1N與(x0(3)-x0(7))W3N，完成第一級下路輸出的四個數據的蝶形運算。

此時，第一路在第一級運算后的輸出數據，在第二級完成了全部的蝶形運算。第二級的輸出結果同第一級一樣，蝶形運算的上路輸出前N/8=1個進入下一級寄存器，后一個數據直接進入后一級進行碟算，下路輸出的數據存入本級移位寄存器中。

第三級的運算與第二級和第一級類似，即移入1級寄存器的數據與其后一個數據進行碟算，同時使前一級寄存器的輸出數據進入后一級寄存器的空白位中，然后開關打到位置②，對下路輸出數據進行碟算。

對于第二路數據，通過開關控制，在第二級中，待第一路第一級下路輸出數據進行蝶形運算時，移入寄存器的空白位，為運算做準備，由于前級運算周期是后級運算周期的兩倍，對于第二級碟算模塊而言，數據仍然是不間斷輸入的。

通過這樣兩路數據的交替運算和存儲，實現“乒乓操作”，從而提高了蝶形運算模塊的運算效率。圖4是256點FFT的具體運算輸入和輸出時序圖。

圖4 兩路數據的輸入和輸出時序圖

對于只有一路數據的應用場合，可以在前級加入，門控開關和數據緩沖寄存器分成兩路數據，實現一路數據的不間斷讀入。

由于采用移位寄存器結構，各級寄存器使用的數量都是固定的，即為N/2+N/4。其中，N為該級DFT運算的點數，各級使用的移位寄存器深度逐級遞減，從而大大降低了寄存器的使用數量。

此外，由于各級結構固定，所以大點數FFT只是小點數FFT基礎上級數的增加，而且由于移位寄存器的輸出相對于RAM而言不需要復雜的地址控制，所以這種結構的FFT處理器具有非常好的可擴展性。比如需要實現512點的FFT，只需要在256點的基礎上增加一級即可。

3 具體模塊的設計

3.1 控制與地址產生模塊

由于兩路數據同時輸入，為了防止發生兩路數據間的串擾，對數據的控制顯得極其關鍵。從上面的算法結構分析中知道，由于后級的DFT運算點數是前一級的一半，所以后一級的開關轉換周期也是前一級的一半，基于這種關系，可以使用一個8位計數器的每一位狀態來對各級開關進行控制。最高位控制第一級，同時由于上一級數據進入下一級需要一個時鐘，所以下一級的開關轉換時刻要比上一級延遲一個時鐘周期。

對于移位寄存器，在實現時，各級的前級移位寄存器深度為N/2-1，從本質而言，是使運算開始的時鐘上升沿到來時，數據已經出現在碟算模塊輸入線上，而不需要下一個時鐘的驅動來移出寄存器，比如第二級移位寄存器的級數為63。這樣，運算周期正好是2的倍數，從而方便使用計數器的各位直接對開關進行控制。

同時，計數器還可以用來產生所需旋轉因子的RAM地址。根據各級蝶形運算所需旋轉因子的規律，可以利用計數器的高位補零來產生查找表的地址。比如，對于第一級，因為需要在最低位第一次出現1時提供W0N，第二次出現1時提供W1N，…，以此類推，周期為128，所以可以使用計數器的低七位作為地址。對于第二級，由于所需要的地址為偶數，可以由計數器的[6:1]和最低位置0產生。表1為8點時使用三位計數器輸出旋轉因子的地址情況。

控制和地址產生模塊的仿真結果如圖5所示，其中sel代表開關控制，addr代表產生的地址。

圖5 控制和地址產生模塊的仿真結果

3.2 蝶形運算模塊

蝶算模塊由一個復數加法器，一個復數減法器和一個旋轉因子的復數乘法器構成，如圖6所示。

圖6 蝶形運算單元

旋轉因子乘法器通常由4次實數乘法和2次加/減法運算實現，但因為cos和sin的值可以預先存儲，通過下面的算法[4]可以簡化復數乘法器:

(1) 存儲如下三個系數:C，C+S，C-S

(2) 計算:E=X-Y和Z=C*E=C*(X-Y)

(3) 用R=(C-S)*Y+Z，I=(C+S)*X-Z，得到需要的結果。

這種算法使用了3次乘法，1次加法和2次減法，但是需要使用存儲3個表的ROM資源。

設計中數據的輸入為16位復數，所以將旋轉因子cos(2kπ/N)，sin(2kπ/N)量化成帶符號數的16位二進制數后，存儲到ROM中，由于值域不同，需要注意C+S和C-S的表要比C表多1位精度。

運算后的結果需要除以量化時乘以的倍數16b0111111111111111。具體實現時由于除法運算在FPGA器件需要消耗較多的資源，設計中采用二進制數移位的方法來實現除法運算。為了防止數據溢出，設計對輸出結果除以2。圖7為蝶形運算模塊的RTL級結構圖。

圖7 蝶形運算模塊的RTL結構圖

3.3 倒序輸出模塊

由頻域抽取的基-2算法可知，運算結果需要倒序輸出。可以先將結果存儲到RAM中，然后使用0~255的二進制數倒序產生RAM讀取地址，依次將結果讀出，其中實現一個8位二進制數倒序的算法如下:

(1) 將8位數字的相鄰兩位交換位置;

(2) 將相鄰的兩位看作1組，相鄰兩組交換位置;

(3) 將相鄰的4位看作1組，相鄰兩組交換位置。

經過這樣的交換位置后，輸出即為原來8位二進制數的倒序。

舉例對于8位二進制數10110110來說，第一次交換位置的結果是01111001，第二次交換位置的結果是11010110，最后交換位置的結果是01101101。可見正好是原來數字的倒序。

另外，由于設計的是兩路數據同時寫入，一路數據讀出，所以讀取的頻率是寫入頻率的2倍，使用PLL實現原始時鐘的二倍頻，用來讀取RAM。倒序模塊仿真結果如圖8所示。

圖8 倒序模塊仿真結果

最終生成的FFT處理器模塊圖如圖9所示。

圖9 生成的FFT處理器模塊

4 仿真結果

各級間數據時序情況如圖10所示，設計的FFT處理器仿真結果如圖11所示。采用一路階梯遞增信號和另一路XXXX信號進行仿真，通過與Matlab計算結果進行對比，結果基本一致，可以滿足系統要求。系統總的延時由延時最大的第一級決定，為第一級運算的延時加上倒序輸出的延時，總共是(256+128)×clk，相對于一般流水線結構(256×讀入周期+7×128×蝶算周期+128×讀入周期)，系統延時大為減少。

通過仿真可知，系統最大頻率由蝶形運算模塊的最大工作頻率決定。使用Quartus Ⅱ軟件時序仿真后，得到處理器的工作頻率為72 MHz。

圖10 各級間兩路數據時序情況

圖11 FFT處理器仿真結果

5 結語

通過采用移位寄存器流水線結構，可以有效地提高FFT處理器中蝶形運算單元的效率，減少寄存器的使用數量，并且簡化了地址控制，提高處理器的工作頻率，具有良好的可擴展性，同時可以實現兩路數據的同時輸

入，從而增大了一倍的數據吞吐量。對于工作頻率要

求較高，數據吞吐量較大，尤其對于需要兩路數據輸入的場合，比如兩天線的MIMO-OFDM系統，具有很大的實用價值。

參考文獻

[1]崔新瑞，張捷，張晶，等.OFDM系統原理及仿真實現[J].信息安全與通信保密，2007(12):68-69.

[2]丁玉美，高西全.數字信號處理[M].西安:西安電子科技大學出版社，2001.

[3]戴明楨.數字信號處理的硬件實現[M].北京:航空工業出版社，1998.[4]Uwe Meyer-Baese.數字信號處理的FPGA實現[M].劉凌，譯.北京:清華大學出版社，2002.

[5]Samir Palnitkar.Verilog HDL數字設計與綜合[M].夏宇聞，胡燕祥，刁嵐松，譯.北京:電子工業出版社，2004.