大點(diǎn)數(shù)FFT設(shè)計(jì)中提高資源利用率的方法

李 斌,田素雷,孫雪晶

(中國電子科技集團(tuán)公司第五十四研究所,河北石家莊050081)

0 引言

快速傅里葉變換作為時(shí)域和頻域轉(zhuǎn)換的基本運(yùn)算,是頻譜分析的必要前提,在數(shù)字通信、語音信號(hào)分析、圖象處理、雷達(dá)、地震和生物醫(yī)學(xué)工程等數(shù)字信號(hào)處理領(lǐng)域有著極為廣泛的應(yīng)用。

隨著數(shù)字信號(hào)處理技術(shù)的飛速發(fā)展,應(yīng)用系統(tǒng)對(duì)于高速大點(diǎn)數(shù)的FFT處理器需求越來越大,這就意味著芯片的資源、面積、功耗和成本都將大幅提高。在目前FFT算法已經(jīng)相當(dāng)成熟的條件下,系統(tǒng)運(yùn)算量難以減少,因此只能通過改善實(shí)現(xiàn)方式,即增加資源,提高并行度,提高工作頻率,才能達(dá)到更高的變換速度。

該文介紹了2種用于提高大點(diǎn)數(shù)FFT設(shè)計(jì)中資源利用率的方法,通過提高運(yùn)算單元和存儲(chǔ)單元的利用率,能夠有效地減少變換時(shí)間和資源面積。以一個(gè)64 K點(diǎn)FFT處理器的設(shè)計(jì)為例,對(duì)2種方法進(jìn)行了詳細(xì)分析。

1 FFT算法

FFT算法的基本思想:利用WNr函數(shù)(旋轉(zhuǎn)因子)的周期性、對(duì)稱性,將原有的N點(diǎn)序列分解成2個(gè)或者多個(gè)較短的序列,這些短序列的傅里葉變換(DFT)可以重新組合成原序列的DFT,并且總的運(yùn)算次數(shù)比直接的DFT運(yùn)算次數(shù)少的多,從而達(dá)到提高速度的目的。

長(zhǎng)度為N的FFT變換可以寫為:

式中,k,n∈[0,N-1],N為運(yùn)算點(diǎn)數(shù)。

由FFT算法可知,基數(shù)越高,總運(yùn)算量越少,因此采用高基數(shù)的蝶形運(yùn)算方式,能夠提高運(yùn)算速度?；?6按時(shí)域抽取(DIT)可以寫為:

式中,m∈[0,N/16-1];j∈[0,15];k∈[0,N-1],N為運(yùn)算點(diǎn)數(shù)。

令

式中,i∈[0,15]。

觀察Yi可知,Yi為N/16點(diǎn)的FFT運(yùn)算,可以將N點(diǎn)降為N/16點(diǎn)的FFT運(yùn)算。

而式(2)按照基16分解為 x(16m),x(16m+1),x(16m+2),…,x(16m+15)分別抽取,可以分解為:

式中,X(k+jN/16)表示基16運(yùn)算的第 j個(gè)輸出點(diǎn),而Yi則可以通過N/16點(diǎn)FFT來實(shí)現(xiàn),從而實(shí)現(xiàn)迭代運(yùn)算。

2 提高運(yùn)算單元的利用率

傳統(tǒng)的FFT變換分為3個(gè)階段,首先將輸入數(shù)據(jù)全部存入RAM,之后進(jìn)行各級(jí)蝶形運(yùn)算,蝶形運(yùn)算全部完成后再從RAM中輸出數(shù)據(jù),這樣運(yùn)算一組數(shù)據(jù)需要的時(shí)間即為(載入時(shí)間+運(yùn)算時(shí)間+輸出時(shí)間)。

在這種載入、運(yùn)算和輸出順序進(jìn)行的結(jié)構(gòu)中,只有數(shù)據(jù)全部輸入后運(yùn)算單元才開始工作,同樣,只有運(yùn)算全部結(jié)束后才能進(jìn)行數(shù)據(jù)輸出。這樣在大點(diǎn)數(shù)FFT變換中,輸入輸出會(huì)占用大量時(shí)間,而此時(shí)運(yùn)算單元?jiǎng)t處于空閑狀態(tài)。因此,對(duì)變換過程進(jìn)行了改進(jìn),將輸入的部分?jǐn)?shù)據(jù)與運(yùn)算數(shù)據(jù)重疊,輸出的部分?jǐn)?shù)據(jù)也可與運(yùn)算數(shù)據(jù)重疊,使得運(yùn)算單元能夠在數(shù)據(jù)輸入或輸出的同時(shí)進(jìn)行運(yùn)算,減少其在整個(gè)變換過程中的空閑時(shí)間。

按照蝶形算法的運(yùn)算順序,在一組數(shù)據(jù)的FFT運(yùn)算中,當(dāng)?shù)趉級(jí)的運(yùn)算進(jìn)行到第n=3×4(s-k-1)=3N/4(k+1)(s為運(yùn)算N個(gè)數(shù)據(jù)的FFT所需要的總級(jí)數(shù))個(gè)數(shù)據(jù)時(shí),第k+1級(jí)運(yùn)算即可開始。根據(jù)這一特點(diǎn),變換過程的“載入-變換-輸出”3個(gè)階段可以進(jìn)行重疊,既輸入的同時(shí)進(jìn)行第1級(jí)蝶算,第4級(jí)蝶算的同時(shí)進(jìn)行輸出。

受到FFT算法的限制,運(yùn)算和輸出重疊的條件是變換結(jié)果倒序輸出。如果需要正序輸出結(jié)果,那么最后一級(jí)運(yùn)算結(jié)束之后才能夠進(jìn)行輸出。輸入和運(yùn)算重疊則沒有條件限制。

以64 K點(diǎn)的FFT為例,此設(shè)計(jì)采用的是16輸入的基16蝶形運(yùn)算,共需4級(jí),每級(jí)4 K個(gè)時(shí)鐘周期的運(yùn)算時(shí)間。不同階段變換的重疊部分示意圖如圖1所示。

對(duì)于一組64 K點(diǎn)數(shù)據(jù)的FFT變換,由于數(shù)據(jù)按時(shí)鐘采樣取數(shù),所以64 K個(gè)數(shù)據(jù)需要64 K個(gè)時(shí)鐘周期來完成輸入,根據(jù)算法,第1級(jí)蝶算需要的數(shù)據(jù)為 n,n+4 K,n+8 K,…,n+56 K,n+60 K(n∈[0,4 095]),因此輸入到第60 K個(gè)數(shù)據(jù)時(shí),就可以開始進(jìn)行第1級(jí)蝶算,即當(dāng)64 K數(shù)據(jù)輸入完成時(shí),數(shù)據(jù)的第1級(jí)運(yùn)算也隨之完成。這樣,載入和變換可以有4 K個(gè)時(shí)鐘周期的重疊時(shí)間,如圖1(a)所示。

圖1 不同階段重疊的變換示意圖

輸出時(shí)采用數(shù)據(jù)倒序輸出。根據(jù)蝶算單元中基4倒序輸出的規(guī)律,當(dāng)?shù)?級(jí)蝶算每時(shí)鐘周期產(chǎn)生16個(gè)變換結(jié)果時(shí),將這16個(gè)結(jié)果數(shù)據(jù)中的第1個(gè)直接進(jìn)行輸出,其余數(shù)據(jù)仍存放回原位置。完成第4級(jí)蝶算共需要4 K個(gè)時(shí)鐘周期,可以輸出4 K個(gè)數(shù)據(jù),這樣就實(shí)現(xiàn)了邊運(yùn)算邊輸出,變換和輸出有了4 K個(gè)時(shí)鐘周期的重疊,如圖1(b)所示。

3 提高存儲(chǔ)單元的利用率

受限于FFT算法本身,要提高數(shù)據(jù)吞吐率最好的方法就是多組數(shù)據(jù)之間采用流水實(shí)現(xiàn)連續(xù)的運(yùn)算,在實(shí)際應(yīng)用中,系統(tǒng)也往往需要FFT模塊具有連續(xù)運(yùn)算的能力。常見的方法是通過3倍的乒乓隨機(jī)存儲(chǔ)器(RAM)來實(shí)現(xiàn)流水線,但對(duì)于大點(diǎn)數(shù)設(shè)計(jì),這樣會(huì)造成電路規(guī)模和面積的大幅增加。為減少不必要的資源占用,可以通過RAM的循環(huán)使用來實(shí)現(xiàn)流水設(shè)計(jì),只需增加部分RAM進(jìn)行緩沖,就能達(dá)到數(shù)據(jù)連續(xù)變換的目的。

下面同樣以64 K點(diǎn)的FFT設(shè)計(jì)來進(jìn)行詳細(xì)介紹。設(shè)計(jì)中使用了必需的4組RAM,每組16 K,以及部分緩沖RAM。

載入時(shí)RAM整體使用示意圖如圖2所示,斜線表示未運(yùn)算數(shù)據(jù),方格表示正在進(jìn)行運(yùn)算的數(shù)據(jù)。4個(gè)子圖中每個(gè)標(biāo)準(zhǔn)矩形表示1組4塊的4 K×32的SRAM。圖2(a)表示第1次載入時(shí),前60 K數(shù)據(jù)載入后RAM的使用情形,這時(shí)只有第4組RAM的后1/4(也就是最后一塊RAM)是空的,并且沒有開始變換。圖2(b)表示載入60～64 K數(shù)據(jù)的情形,這部分?jǐn)?shù)據(jù)沒有載入到第4組RAM的后1/4(也就是最后一塊RAM),而是將直接進(jìn)行第1級(jí)變換,當(dāng)然,變換的結(jié)果需要存入這部分RAM。圖2(c)和圖2(d)為第2和第3級(jí)變換,在這段時(shí)間里,數(shù)據(jù)被載入到第5組進(jìn)行緩沖的RAM中。

圖2 載入時(shí)RAM整體使用示意圖

輸出時(shí)RAM使用示意圖如圖3所示,斜線表示未運(yùn)算數(shù)據(jù),方格表示正在進(jìn)行運(yùn)算的數(shù)據(jù),網(wǎng)格表示等待輸出的數(shù)據(jù)。

圖3 輸出時(shí)RAM使用示意圖

圖3(a)和圖3(b)中4個(gè)較大的矩形表示第1組中的4塊RAM,它們內(nèi)部存放的數(shù)據(jù)在第4級(jí)時(shí)都由第1號(hào)蝶算單元進(jìn)行運(yùn)算。圖3(a)表示第1塊RAM中的數(shù)據(jù)運(yùn)算后不再存回,直接輸出,以便新的數(shù)據(jù)可以載入。每一塊RAM的讀取都是完全正序的,即按照0,1,2,…,15,…,4 K-1的順序。由于這4塊數(shù)據(jù)同時(shí)參與運(yùn)算,所以第2、第3和第4塊RAM的數(shù)據(jù)被寫回原地址保存。這4塊RAM運(yùn)算完成需要4 K個(gè)時(shí)鐘周期。4塊RAM運(yùn)算完成后,第1塊RAM也完全空了,其他3塊RAM則裝滿了變換結(jié)果,如圖3(b)所示。

圖3(c)和圖3(d)中4個(gè)較大的矩形表示第2、第3和第4組中的任意一組的4塊RAM,它們內(nèi)部存放的數(shù)據(jù)在第4級(jí)時(shí)分別由第2、第3和第4號(hào)蝶算單元進(jìn)行運(yùn)算。圖3(c)表示第4級(jí)運(yùn)算正在進(jìn)行中,這些運(yùn)算和第1組的4塊RAM中數(shù)據(jù)的運(yùn)算同時(shí)進(jìn)行。每一塊RAM的讀取都是完全正序的,即按照0,1,2,…,15,…,4 K-1的順序。運(yùn)算的結(jié)果即變換的結(jié)果被寫回原地址保存。這4塊RAM運(yùn)算完成也需要4 K個(gè)時(shí)鐘周期。4塊RAM運(yùn)算完成后,都裝滿了變換結(jié)果,等待輸出,如圖3(d)所示。

第4級(jí)運(yùn)算時(shí),第1組(中的第1塊)RAM就可以同時(shí)輸出數(shù)據(jù),也能夠夠載入新的數(shù)據(jù)。當(dāng)?shù)?級(jí)運(yùn)算結(jié)束后,第1組RAM開始純粹的輸出。第1組RAM輸出完畢后,依次序是第2、第3和第4組 RAM輸出。數(shù)據(jù)輸出的存儲(chǔ)單元就可以載入新的數(shù)據(jù)了。

以上是連續(xù)變換時(shí),一組數(shù)據(jù)存儲(chǔ)、變換和輸出的整個(gè)過程。同時(shí)上述部分也詳細(xì)分析了只使用少量RAM就可以實(shí)現(xiàn)的連續(xù)變換的方法,其核心思想是3個(gè)合并:把一組運(yùn)算數(shù)據(jù)的輸入和其第1級(jí)運(yùn)算合并,把第4級(jí)運(yùn)算和輸出合并,把輸出和下一組數(shù)據(jù)的輸入合并。這樣只需增加少量的RAM就可以實(shí)現(xiàn)連續(xù)變換,緩沖RAM的大小取決于中間運(yùn)算需要的時(shí)鐘周期數(shù)。

4 結(jié)束語

在并行度、時(shí)鐘頻率和蝶算基數(shù)相同的情況下(16輸入基16蝶算,流水線運(yùn)算),未采用文中所述方法時(shí),電路的運(yùn)算時(shí)間為16 K個(gè)時(shí)鐘周期,占用的存儲(chǔ)器為192K的SRAM。采用文中所述方法后,電路的運(yùn)算時(shí)間為8 K個(gè)時(shí)鐘周期,占用的存儲(chǔ)器為72 K的SRAM。

由此可見,文中的2種提高資源利用率的方法確實(shí)有效的減少了變換時(shí)間和資源占用。

[1]CHEN Yuan,LIN Yu-wei,TSAO Yu-chi,et al.A 2.4-Gsample/s DVFS FFT Processor forMIMO OFDM Communication Systems[C].IEEE Journal of Solid-state Circuits,2008:1260-1266.

[2]OPPENHEIM A V,WILLSKY A S.Signals and Systems[M].Prentice-Hall,1983.

[3]譚 征,張曉林,杜永久.一種基于FPGA的超高速FFT處理器設(shè)計(jì)[J].遙測(cè)遙控,2005,26(6):46-49.

[4]管吉興.FFT的FPGA實(shí)現(xiàn)[J].無線電工程,2005,35(2):43-46.

[5]程培青.數(shù)字信號(hào)處理教程[M].北京:清華大學(xué)出版社,1995.

[6]趙 鑫.VHDL與數(shù)字電路設(shè)計(jì)[M].北京:機(jī)械工業(yè)出版社,2005.

[7]高西全,丁玉美,闊永紅.數(shù)字信號(hào)處理-原理、實(shí)現(xiàn)及應(yīng)用[M].北京:電子工業(yè)出版社,2006.