??? 摘? 要： 在寬帶數字接收機中，需要對數字檢波輸出的信號流進行實時FFT運算。提出了一種用于寬帶數字接收機的基于Xilinx的Virtex-IV芯片的高速FFT 的設計與實現方法，采用了多級串行流水線結構及優化的數據存取方式，設計出用單片FPGA實現了2 048點實數的FFT方案。其完成2 048點FFT的時間約為4.57 μs，能很好地滿足系統處理的實時性要求，在工程實踐中有很大的應用前景。?
??? 關鍵詞： FPGA； FFT算法； 數字接收機；多級流水線
?
??? 在寬帶數字接收機中，需要對接收機輸出的零中頻信號進行實時的譜分析，因此FFT的高速實現一直是寬帶數字接收機的重要研究內容之一，而以DSP為代表的數字信號處理芯片的應用使得FFT的運行效率產生了質的飛躍，而超大規模FPGA的應用更是極大地提高了FFT的實現速度，這是由于當今最先進的FPGA芯片內部集成了大量乘法器和存儲資源，其內部規模達到千萬門量級，總線速度接近550 MHz，這些可編程硬件資源為FFT的高速實現提供了可能。?
??? 參考文獻[1]論述了一種基于FPGA的FFT實現方法，在系統時鐘為100 MHz時,采用Xilinx公司Vertex-IIPro完成1 024點復數FFT運算僅需要2.56 μs，但由于系統時鐘速度較低，輸入輸出數據的速度較慢。參考文獻[3]論述了基于FPGA的FFT算法實現，其設計的1 024點復數基4-FFT處理器在100 MHz的主時鐘頻率下運算速度為51．29 μs，其速度同樣不能滿足寬帶數字接收機實時譜分析的要求?；诖?，本文論述了一種基于單片FPGA的高速FFT設計與實現技術。?
??? Virtex-IV SX 芯片中集成了XtremeDSP Slice，支持40多個動態控制的操作模式，包括乘法器、乘法器－累加器、乘法器－加法器/減法器，三輸入加法器、桶形移位器、寬總線多路復用器或寬計數器，可以獨立達到500 MHz的性能，或整列組合在一起以實現DSP功能。本系統即選用了XC4VSX55芯片，在單片FPGA上完成了2 048點的FFT高速運算。?
1 基4-FFT算法簡介?
??? 系統需要對于2 048點實序列完成FFT實時處理，這里選用基4-FFT算法。基4-FFT共需log4N=r次迭代運算，每次迭代包含N/4個碟形單元，基4-蝶形運算單元見圖1。?
?
?
2 頻域抽取基4-FFT的FPGA設計與實現?
2．1總體實現結構設計?
??? 在得到1 024點復數序列的FFT結果后，再進行一級蝶形運算就可得到2 048點實序列的FFT，這種算法減小了每一級蝶形運算的數據量，提高了整個FFT運算的工作頻率。1 024點復序列的基4-FFT共需5級蝶形運算，每一級需256個蝶形運算單元，再加上1級結果轉換單元和1級求模值運算單元，完整的2 048點實序列的基4-FFT共需7級運算，考慮到頻域抽取基4-FFT算法的特點，本文采用級間順序運算、級內并行加流水的實現結構?？傮w實現結構框圖如圖2所示。?
?
?
??? 系統實現流程為：首先，數據緩沖模塊暫存輸入數據流，并進行必要排序處理，然后，狀態控制邏輯單元啟動蝶形運算，第i級蝶形運算利用第i-1級的輸出結果和對應的旋轉因子完成本級蝶形運算，把運算結果存儲到對應的存儲單元中，第i級運算完成后，使能第i+1級運算，以此類推，經過5級蝶形運算，就可以得到1? 024點復序列的FFT結果，運算結果經數據轉換單元就可以得到2 048點實序列的FFT結果；時鐘分配模塊把輸入時鐘進行緩沖、分頻、調理等處理，為各級運算單元、存儲單元提供同步時鐘，狀態控制邏輯單元完成各級運算單元之間的轉換控制功能。?
2．2 數據存儲單元設計?
??? 依據頻域抽取基4-FFT算法的要求，輸入數據是順序輸入的，設由實序列組合得到的1 024點復序列為X(0)、X(1)、…、X(N-1)，數據緩沖模塊把該序列分成4組進行緩沖存儲，具體為：數據X(0)、X(4)、…、X(1 020)為第1組；X(1)、X(5)、…、X(1 021)為第2組；X(2)、X(6)、…、X(1 022)為第3組；X(3)、X(7)、…、X(1 023)為第4組，4組數據分別順序存儲于雙端口RAM中(DPRAM1(0)、DPRAM2(0)、DPRAM3(0)、DPRAM4(0))，產生的存儲地址為st_addr(i+1)=st_addr(i)+1，存儲器的存儲深度為256。輸入數據的存儲結構如表1所示。?
?
?
??? 依據基4-FFT算法的運算規則，第1級蝶形運算的數據量為4，即輸入數據量、輸出數據量都為4。對于1 024點復序列，參與第1級蝶形運算的4個數據分別為X(i)、X(i+256)、X(i+512)、X(i+768)，i=0,1,…,255，可以看出，第1級蝶形運算單元的輸入數據可以分別從DPRAM1(0)、DPRAM2(0)、DPRAM3(0)及DPRMA4(0)讀取，而不會出現交叉讀取數據的現象，這樣，可以方便地采用4個蝶形運算單元并行工作模式，從而提高工作速度。?
??? 記第1級蝶形運算的輸出數據為X(i)，i=0,1,…,255，其中，每個X(i)為一次蝶形運算結果，包括4個元素。把第1級運算的輸出數據分成4組，分別順序存儲于4個雙端口RAM中(DPRAM1(1)、DPRAM2(1)、DPRAM3(1)及DPRAM4(1))，存儲地址也是順序產生的，即st_addr(i+1)=st_addr(i)+1，第1級蝶形運算輸出結果的存儲結構如表2所示。?
?
?
??? 第2級蝶形運算的數據量為16，具體描述為：把數據組X(i)、X(i+64)、X(i+128)及X(i+192)分成一組，記為第i組，其中，i=0,1,…,63，運算時，從這4個數據組中依次讀取對應元素作為蝶形運算單元的輸入數據，例如，分別取X(i)、X(i+64)、X(i+128)及X(i+192)中的第1個元素作為一次蝶形運算的輸入數據，依次類推。第2級蝶形運算的輸出數據記作X(i,i),i=0,1,…,63，每個X(i,i)是第i組數據的運算結果，包含16個元素；該級蝶形運算的輸出數據也分成4組，分別順序存儲于DPRAM1(2)、DPRAM2(2)、DPRAM3(2)及DPRMA4(2)，其存儲結構如表3所示。?
?
?
??? 第3級蝶形運算單元的數據量為64，把數據組X(i,i)、X(i+16,i+16)、X(i+32,i+32)及X(i+48,i+48)作為第i組數據，其中，i=0,1,…,15，運算時，從數據組X(i,i)、X(i+16,i+16)、X(i+32,i+32)及X(i+48,i+48)中依次取對應元素作為該級蝶形運算單元的輸入數據。第3級蝶形運算的輸出數據記為X(i,i,i),i=0,1,…,15，每個X(i,i,i)是第i組數據的運算結果，包含64個元素；該級蝶形運算的輸出數據分成4組，分別順序存儲于DPRAM1(3)、DPRAM2(3)、DPRAM3(3)及DPRMA4(3)，其存儲結構如表4所示。?
?
?
??? 第4級蝶形運算的數據量為256，把數據組X(i,i,i)、X(i+4,i+4,i+4)、X(i+8,i+8,i+8)及X(i+12,i+12,i+12)分成一組，作為第i組數據，其中，i=0,1,…,15。運算時，從數據組X(i,i,i)、X(i+4,i+4,i+4)、X(i+8,i+8,i+8)及X(i+12,i+12,i+12)中依次取對應元素作為該級蝶形運算單元的輸入數據。第4級蝶形運算的輸出數據量記為X(i,i,i,i),i=0,1,2,3，每個X(i,i,i,i)有256個元素。把該級蝶形運算的輸出數據分成4組，分別順序存儲于DPRAM1(4)、DPRAM2(4)、DPRAM3(4)及DPRMA4(4)，其存儲結構如表5所示。?
?
?
??? 第5級蝶形運算的數據量為1 024，從數據組X(0,0,0)、X(1,1,1,1)、X(2,2,2,2)及X(3,3,3,3)中依次讀取對應數據作為該級蝶形運算單元的輸入數據。該級蝶形運算的輸出數據量為1 024，也分成4組順序存儲于DPRAM1(5)、DPRAM2(5)、DPRAM3(5)、DPRAM4(5)。?
2．3 流水結構的蝶形運算單元設計?
??? 本設計的基4-蝶形運算單元采用串行輸入/輸出、并行運算的結構，其中，串行輸入/輸出數據流是由時鐘信號clk1控制的，而內部并行運算是由時鐘信號clk2控制的，clk2是clk1四分頻后的結果。同時，設計采用增加流水級的辦法進一步提高運算速度，復數乘運算采用全并行結構實現，共需2級流水，整個蝶形運算共需6級流水，第1級是4個串行輸入數據緩沖，第2、3級是復數乘，第4、5級是兩級加減運算，第6級是4個輸出結果在時鐘clk1控制下串行輸出。圖3是蝶形運算單元的實現框圖，圖4是復數乘運算的并行實現框圖。?
?
?
?
2．4 狀態控制單元設計?
??? 狀態控制單元主要完成每級運算之間的狀態轉換功能，產生相應的使能信號。根據前面的分析，2 048點實序列的基4-FFT共需要5級蝶形運算、一級數據轉換和求模值運算和一級數據讀出單元，這樣，整個基4-FFT功能模塊共需7個狀態，分別用stage1~stage7來表示，設計采樣有限狀態機加以實現，產生的控制使能信號分別為butter1_cal_en、butter2_cal_en、butter3_cal_en、butter4_cal_en、butter5_cal_en、change_en及read_en，每個狀態對應于一級蝶形運算，實現的具體功能包括：使上一級存儲器的讀出使能信號有效，使本級蝶形運算單元和本級存儲器的存儲使能信號有效。狀態控制單元的Modelsim仿真結果如圖5所示。?
?
?
3? 基4-FFT模塊的性能分析?
3．1資源消耗及運算速度估計?
??? 按照本文設計，每個復數乘法器消耗4個硬件乘法器、而每個蝶形運算單元有3個復數乘法器，這樣，每個蝶形運算單元共消耗12個硬件乘法器。并在設計時，根據數據存儲結構特點，各級運算采用4個蝶形運算單元并行工作的方式，另外，數據轉換單元的蝶形運算包含1個復數乘法器，也采用4路并行工作方式，由于第1級蝶形運算不需要復數乘法運算，所以，整個FFT模塊共消耗3×4×12+12+4×4＝172個硬件乘法器資源；本文設計的基4-FFT模塊共需6個狀態來完成，每個狀態對應一級蝶形運算，每級蝶形運算消耗的總時間包括數據讀出時間和流水延時時間兩部分。這樣，第1級蝶形運算共需256+4×4=272個 clk時鐘，第2、3、4級蝶形運算共需3×(256+6×4)＝840個clk時鐘，第5級需要256+4=260個clk時鐘，這樣，整個FFT模塊共需要1 370個clk時鐘周期完成，在clk頻率為300 MHz時，完成FFT運算共需4.57 μs。?
3．2 實現結果?
??? 本文利用單片FPGA實現2 048點FFT計算，采用實際信號數據注入實驗驗證，注入單點頻信號并加入高斯白噪聲時，信噪比SNR=0 dB，圖6(a)是FFT模塊的輸出結果，可以看出，輸出結果將在歸一化頻率100和其鏡像頻率1 948位置產生兩個峰值點；注入3個點頻加入高斯白噪聲，SNR=0 dB，圖6(b)是FFT模塊的輸出結果。?
?
?
??? 本文針對高速數字接收機頻譜實時估計的需求，設計了基于Xilinx的Virtex-IV系列的XC4VSX55芯片的FFT算法設計并實現，實測結果與計算機仿真結果一致?？梢婋S著總線速度可達550 MHz的Virtex-V的出現及更加豐富的資源置于片內，使得全并行結構的實現成為可能，為FFT的高速實現與應用提供了更有效的手段。?
參考文獻?
[1] 張敖華，張正鴻，堯德中.一種基于FPGA的高性能FFT處理器設計. 電子對抗技術，2005，20(7).?
[2]?譚 磊，張朝陽，陳文正.高速定點快速傅立葉變換處理器的設計與實現[J]. 浙江大學學報(工學版)，2005,39(3):407-413.?
[3]?伍萬棱，邵杰，冼楚華.FPGA實現的基4-FFT處理器高效排序算法研究[J]. 南京航空航天大學學報，2005,37(2):222-226.?
[4]?朱冰蓮，劉學剛.FPGA實現流水結構的FFT處理器[J].重慶大學學報，2004,27(9)：33-36.?
[5]?SUKHSAWAS S. A high-level implementation of a high?performance pipleline FFT on Virtex-E FPGAs [6].Proceedings of the IEEE Coputer Society Annual Symposium on VLSI Emerging Trends in VLSI Systems Design[J].2004.?
[6]?胡廣書. 數字信號處理理論、算法與實現. 北京：清華大學出版，2003.08?
[7]?蘇濤，吳順君，李真芳,等. 高性能DSP與高速實時信號處理. 西安電子科技大學出版社, 2002.