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