固定幾何結(jié)構(gòu)的FFT算法及其FPGA實(shí)現(xiàn)

1、固定幾何結(jié)構(gòu)的fft算法及其fpga實(shí)現(xiàn)dft及英快速算法fft是信號(hào)處理領(lǐng)域的核心組成部分。fft算法多種多樣，按數(shù)據(jù)組合 方式不同一般分時(shí)域和頻域，按數(shù)據(jù)抽取方式的不同又可分為基2,基4等。各算法的優(yōu)缺 點(diǎn)視不同的制約因素而不同。fft的實(shí)現(xiàn)方法也多種多樣，可以用軟件實(shí)現(xiàn)，也可以用硬 件實(shí)現(xiàn)，用軟件在pc機(jī)或工作站上實(shí)現(xiàn)則計(jì)算速度很慢。一般多結(jié)合具體系統(tǒng)用硬件實(shí)現(xiàn)。 例如用單片機(jī)或dsp實(shí)現(xiàn)。但是速度仍然很慢，難以與快速的a/d器件匹配。在雷達(dá)信號(hào) 處理領(lǐng)域主要追求的目標(biāo)是速度，即實(shí)時(shí)性的要求非常高。針対這種快速信號(hào)處理的要求及 fpga器件的特點(diǎn)，木文采用的是一種基2同定兒何結(jié)構(gòu)的fft

2、算法。采用的是altera公 司推出的最新器件stratix來做硬件仿真。stratix器件是一款采用高性能結(jié)構(gòu)體系的pld器 件。它結(jié)合了強(qiáng)人內(nèi)核性能，人存儲(chǔ)帶寬，數(shù)字信號(hào)處理（dsp）功能，高速i/o性能和模 塊化設(shè)計(jì)與一體的pldo jt內(nèi)嵌的dsp模塊具冇很高的乘法運(yùn)算速度。在用vhdl編程時(shí) 可以用megawizard的方法指定用dsp模塊生成乘法器，用這種乘法器來做蝶形，用多個(gè) 蝶形來構(gòu)成fft運(yùn)算級(jí)，通過循環(huán)即可實(shí)現(xiàn)fft核心運(yùn)算的并行化。用altera公司的qu artus軟件做邏輯分析和波形分析。quartus軟件具有很強(qiáng)的硬件仿真和邏輯分析功能，它 可將川vhdl編寫的硬件

3、描述綜合到fpga屮。2.算法介紹為了說明問題的方便，下面以基2,八點(diǎn)fft為例加以說明。傳統(tǒng)的基2變兒何結(jié)構(gòu)算法 如下（圖一）：箭頭上的數(shù)字代表旋轉(zhuǎn)因了屮的k°圖屮輸入采用的是按碼位顛倒的順序 排放的。輸出是h然順序。這種結(jié)構(gòu)的特點(diǎn)是每個(gè)蝶形的輸出數(shù)據(jù)仍然放在原來的輸入的數(shù) 據(jù)存儲(chǔ)單元內(nèi)，這樣只需要2n個(gè)存儲(chǔ)單元（fft屮的數(shù)據(jù)是復(fù)數(shù)形式，每點(diǎn)需要兩個(gè)單元 存儲(chǔ)）。其缺點(diǎn)是不同級(jí)的同一位置蝶形的輸入數(shù)據(jù)的尋址不固定，難以實(shí)現(xiàn)循環(huán)控制。用 fpga編程時(shí)難以并行實(shí)現(xiàn)，數(shù)據(jù)處理速度慢。當(dāng)fft的點(diǎn)數(shù)增加時(shí)更是如此。通過觀察 傳統(tǒng)結(jié)構(gòu)的fft算法可以發(fā)現(xiàn)，如果將笫-級(jí)中間的兩個(gè)蝶形交換，

4、則可以得到如下結(jié)構(gòu)（圖二）：對(duì)此結(jié)構(gòu)進(jìn)行進(jìn)一步的變換，將第二級(jí)的輸岀不送冋原處而是將其存儲(chǔ)起來并按順序存放, 則笫三級(jí)中間的兩個(gè)蝶形跟著調(diào)換，并把輸入按順序排列，就變成了如下（圖三）所示的固 定結(jié)構(gòu)的fftto在蝶形變換的同時(shí)，具旋轉(zhuǎn)因子也跟看調(diào)換。出數(shù)據(jù)的順序是不變的，因此每級(jí)兒何結(jié)構(gòu)是固定的。用這種結(jié)構(gòu)尋址方便，易于用fpga 編程，實(shí)現(xiàn)內(nèi)部并行的fft碩件結(jié)構(gòu)，從而嘰顯加快fft的運(yùn)算速度。3. fpga硬件實(shí)現(xiàn)fpga器件的特點(diǎn)是可用硬件描述語言對(duì)其進(jìn)行靈活編程。利用fpga廠商提供的軟件可 仿真硬件的功能。使硬件設(shè)計(jì)如同軟件設(shè)計(jì)一樣靈活方便?？s短了系統(tǒng)研發(fā)周期。利用jt ag接口 “

5、j對(duì)具進(jìn)行isp（ln system programmable在系統(tǒng)編程）提高了系統(tǒng)的靈活性。隨 著芯片集成度的提高，單片fpga內(nèi)不僅擁冇人量的邏輯單元而fl還能集成ram,rom,1/ 0及dsp塊等。從而使soc（system on_a_chip片上系統(tǒng)）成為現(xiàn)實(shí)。本文采用的是alt era公同的stratix系列芯片的ep1s25o用altera公訶的quartusll2.0軟件做硬件仿真和邏 輯分析。并將輸出結(jié)果matlab仿真結(jié)果進(jìn)行了比較。系統(tǒng)框圖如下（圖四）:代碼川vhdl硬件描述語言實(shí)現(xiàn)。本系統(tǒng)的結(jié)構(gòu)特點(diǎn)是：1。為捉高數(shù)據(jù)精度，系統(tǒng)全部川 16位寬。用data_array,

6、write_array和fly_array三個(gè)數(shù)組實(shí)現(xiàn)了內(nèi)核的并行處理，可在1 0個(gè)時(shí)鐘周期內(nèi)算完32點(diǎn)復(fù)fft。時(shí)鐘周期為25納秒，因此32點(diǎn)fft只需250納秒。2。 實(shí)現(xiàn)了數(shù)據(jù)的流水輸入輸出。在計(jì)算第i組數(shù)據(jù)的同時(shí)，第i1纟r的數(shù)據(jù)fft結(jié)果正在串行 輸出，第i+1組的數(shù)據(jù)則正在串行輸入。因?yàn)閮?nèi)核計(jì)算是并行的，速度快，所以可以有很高 的串行輸入。本系統(tǒng)的a/d采樣頻率町達(dá)200mhz。仿真所用的信號(hào)是：x(t)= (0.5*sin(2*n*pi/4.7)+0.5*sin(2*n*pi/16.3)+0.1*rand(1,32)*1000 輸入數(shù)據(jù)為32點(diǎn)復(fù)數(shù)，系統(tǒng)仿真波形如下（局部）： 用

7、fpga輸出的fft的結(jié)果（圖六）和用matlab計(jì)算的fft理論結(jié)果（圖七），其頻譜如f：此信號(hào)是由兩個(gè)正弦波證加一個(gè)隨機(jī)函數(shù)構(gòu)成的。信噪比為14dbo為切合工程實(shí)際，仿真 信號(hào)采用的是實(shí)信號(hào)，其頻譜具有對(duì)稱性，因此圖中只取32點(diǎn)仿真結(jié)果的一半即16點(diǎn)便 可。4.結(jié)論通過比較可以看出仿真結(jié)果與理論值吻合的很好c altera公司采用傳統(tǒng)結(jié)構(gòu)的fft算法英3 2點(diǎn)的運(yùn)算吋間大于1.0uso用dsp做的32點(diǎn)fft吋間也要1.0us以上。本系統(tǒng)的最人優(yōu) 勢(shì)在于利用fpga器件豐富的邏輯資源，內(nèi)嵌的ram,rom塊及其靈活的可編程特性采用 固定兒何結(jié)構(gòu)的fft算法使運(yùn)算速度較傳統(tǒng)方法有了很人捉高。當(dāng)然付出的代價(jià)