朱永前 李 霄

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

0 引言

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

1 基4-FFT算法

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

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

(1)

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

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

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

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

2.1 基4拆分及合并

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

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

2.2 蝶形變換

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

圖3 蝶形變換

2.2.1 旋轉(zhuǎn)因子

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

2.2.2 蝶形運算

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

(2)

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

2.2.3 串并串轉(zhuǎn)換

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

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

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

3 仿真分析

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

圖5 FFT仿真結(jié)果

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

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

表1 碼位倒置方法與本文方法資源及耗時對比

4 結(jié)束語

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