在FPGA上實(shí)現(xiàn)FFT的高效串行流水線結(jié)構(gòu)

朱永前 李 霄

(南京長(zhǎng)峰航天電子科技有限公司 南京 211800)

0 引言

快速傅里葉變換(FFT)是信號(hào)處理領(lǐng)域最重要的算法之一,信號(hào)的時(shí)頻域轉(zhuǎn)換、信號(hào)與特征卷積、信道化等都需要FFT算法[1]。高效的FFT實(shí)現(xiàn)方法能降低信號(hào)處理資源占用及提升運(yùn)算速度,在卷積計(jì)算中,為了使參與卷積的特征向量足夠長(zhǎng),往往需要大點(diǎn)數(shù)FFT[2]。FPGA中數(shù)據(jù)并行FFT實(shí)現(xiàn)方式資源消耗非常大,無(wú)法做到較大點(diǎn)數(shù),本文介紹頻域切分基4-FFT算法的一種串行實(shí)現(xiàn)方法,資源消耗少,FFT點(diǎn)數(shù)可變,通過(guò)巧妙設(shè)計(jì)每級(jí)蝶形變換省去碼位倒置排序,是一種高效串行流水線結(jié)構(gòu)。下文以4096點(diǎn)FFT為例,其它4的次冪點(diǎn)FFT同樣適用,FFT點(diǎn)數(shù)為2的次冪非4的次冪時(shí),只需最后一級(jí)蝶形變換用基2變換,無(wú)本質(zhì)差異,文中不再贅述。

1 基4-FFT算法

數(shù)字信號(hào)x的離散傅里葉變換[3]X定義為:

按基4頻域切分推導(dǎo)FFT算法如式(1)所示。

(1)

如公式(1),N點(diǎn)傅里葉變換經(jīng)蝶形變換拆分成4組N/4點(diǎn)傅里葉變換,且N/4點(diǎn)傅里葉變換結(jié)果按模4取余放置即為N點(diǎn)傅里葉變換的結(jié)果,如此遞推即為基4頻域切分FFT。對(duì)于4096點(diǎn)FFT,經(jīng)6級(jí)蝶形變換得到最終結(jié)果,每級(jí)進(jìn)行1024次蝶形運(yùn)算。

2 串行結(jié)構(gòu)設(shè)計(jì)

算法實(shí)現(xiàn)整體結(jié)構(gòu)如圖1所示,4096點(diǎn)原始數(shù)據(jù)串行輸入,基4拆分后成4路1024點(diǎn)串行數(shù)據(jù),再經(jīng)6級(jí)蝶形變換,基4合并后形成4096點(diǎn)FFT結(jié)果串行輸出。

圖1 4096點(diǎn)基4-FFT流水線結(jié)構(gòu)

2.1 基4拆分及合并

根據(jù)基4-FFT遞推公式(1),基4拆分將數(shù)據(jù)按時(shí)間先后拆分成4路,前1024點(diǎn)為第一路;第1025～2048點(diǎn)為第二路;第2049～3072點(diǎn)為第三路;第3073～4096點(diǎn)為第四路,四路數(shù)據(jù)對(duì)齊后接入蝶形變換?；?合并與基4拆分是完全相反的過(guò)程,如圖2所示。

圖2 基4拆分及合并示意圖

2.2 蝶形變換

蝶形變換分為旋轉(zhuǎn)因子產(chǎn)生模塊、蝶形運(yùn)算單元、串并串轉(zhuǎn)換模塊,如圖3所示。旋轉(zhuǎn)因子產(chǎn)生模塊接收數(shù)據(jù)序數(shù),返回旋轉(zhuǎn)因子給蝶形運(yùn)算單元,蝶形運(yùn)算單元接收數(shù)據(jù)和旋轉(zhuǎn)因子,進(jìn)行蝶形運(yùn)算后將數(shù)據(jù)接入串并串轉(zhuǎn)換模塊,轉(zhuǎn)成下一級(jí)蝶形變換需要的數(shù)據(jù)序列后輸出。

圖3 蝶形變換

2.2.1 旋轉(zhuǎn)因子

記蝶形變換的級(jí)數(shù)為S(S從0～5),隨著4路1024點(diǎn)數(shù)據(jù)傳入,數(shù)據(jù)序數(shù)k從0遞增至1023,記kc

2.2.2 蝶形運(yùn)算

記x1(k)、x2(k)、x3(k)、x4(k)為4路數(shù)據(jù),k從0遞增至1023,由公式(1)可知,蝶形運(yùn)算式為

(2)

每級(jí)蝶形變換有1個(gè)蝶形運(yùn)算器,4路數(shù)據(jù)各1024點(diǎn)串行輸入,以流水線形式依次完成1024次蝶形運(yùn)算。

2.2.3 串并串轉(zhuǎn)換

串并串轉(zhuǎn)換模塊的功能是接收蝶形運(yùn)算后數(shù)據(jù),并轉(zhuǎn)成下一級(jí)蝶形變換需要的數(shù)據(jù)序列。該模塊是本文方法與其他FFT實(shí)現(xiàn)方法[4-6]的核心區(qū)別,其他方法將同一路的連續(xù)數(shù)據(jù)塊拆分到4路上,而本文方法將同一時(shí)刻4路的數(shù)據(jù)塊合并到1路上。

第S級(jí)蝶形變換,串并串轉(zhuǎn)換模塊4路輸入數(shù)據(jù),每路以4S個(gè)數(shù)據(jù)為一塊,以塊為單位,將時(shí)間序數(shù)據(jù)轉(zhuǎn)換為路優(yōu)先數(shù)據(jù),即按數(shù)據(jù)到來(lái)先后優(yōu)先填充第1路,第1路填充完1024個(gè)數(shù)據(jù)后填充第2路,以此類推完成4路數(shù)據(jù)的填充,如圖4為第1級(jí)蝶形變換數(shù)據(jù)序列調(diào)整示意圖。為保證4路輸出數(shù)據(jù)時(shí)序?qū)R,需將數(shù)據(jù)先串轉(zhuǎn)并,再并轉(zhuǎn)串。數(shù)據(jù)序列調(diào)整設(shè)計(jì)巧妙,所有蝶形變換完成后,無(wú)需進(jìn)行四進(jìn)制碼位倒置輸出[7-8]。

圖4 第1級(jí)蝶形變換數(shù)據(jù)序列調(diào)整示意圖

3 仿真分析

輸入信號(hào)為頻率60MHz脈寬16μs的點(diǎn)頻脈沖信號(hào),在Vivado軟件中進(jìn)行仿真,FPGA時(shí)鐘頻率為200MHz,計(jì)算結(jié)果如圖5所示。仿真用時(shí)41.14μs,其中基4拆分消耗3072個(gè)時(shí)鐘周期,除最后一級(jí)外,每級(jí)蝶形變換的串并串轉(zhuǎn)換消耗1024個(gè)時(shí)鐘周期,合計(jì)3072+1024×5=8192個(gè)時(shí)鐘周期,200MHz時(shí)鐘下共40.96μs,其余少量時(shí)間為蝶形運(yùn)算乘法和加法消耗。為驗(yàn)證計(jì)算結(jié)果的正確性,將Vivada仿真結(jié)果與Matlab中直接FFT結(jié)果對(duì)比,如圖6所示,忽略定點(diǎn)運(yùn)算導(dǎo)致的微小數(shù)值精度誤差,計(jì)算結(jié)果完全一致。

圖5 FFT仿真結(jié)果

圖6 FFT結(jié)果(絕對(duì)值)對(duì)比

與碼位倒置排序FFT串行實(shí)現(xiàn)方法相比,本文方法無(wú)需碼位倒置排序過(guò)程,資源消耗及運(yùn)算時(shí)間都會(huì)更少,理論上運(yùn)算時(shí)間少1024個(gè)時(shí)鐘周期,200MHz時(shí)鐘頻率下為5.12μs。在同樣的FPGA硬件(xc7vx690tffg1927-2)條件下,在Vivado軟件中進(jìn)行仿真、綜合、實(shí)現(xiàn),兩者布局布線后的資源占用及計(jì)算用時(shí)對(duì)比如表格1,可見(jiàn)本文方法串并轉(zhuǎn)換設(shè)計(jì)優(yōu)于其他方法,且計(jì)算時(shí)間相差46.26-41.14=5.12μs,與理論分析一致。

表1 碼位倒置方法與本文方法資源及耗時(shí)對(duì)比

4 結(jié)束語(yǔ)

本文提出在FPGA上實(shí)現(xiàn)FFT的一種設(shè)計(jì)方案,推導(dǎo)了頻域切分基4-FFT的蝶形變換公式,給出了FFT的串行流水線結(jié)構(gòu),詳細(xì)講解了蝶形變換每個(gè)模塊的設(shè)計(jì)思路,通過(guò)巧妙設(shè)計(jì)每級(jí)蝶形變換的數(shù)據(jù)序列,節(jié)省了重排序步驟,從而無(wú)需碼位倒置即可得到自然序的FFT結(jié)果。對(duì)4096點(diǎn)數(shù)據(jù)進(jìn)行了仿真,需要的資源少,耗時(shí)短,仿真結(jié)果正確。