大點數FFT設計中提高資源利用率的方法

李 斌,田素雷,孫雪晶

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

0 引言

快速傅里葉變換作為時域和頻域轉換的基本運算,是頻譜分析的必要前提,在數字通信、語音信號分析、圖象處理、雷達、地震和生物醫學工程等數字信號處理領域有著極為廣泛的應用。

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

該文介紹了2種用于提高大點數FFT設計中資源利用率的方法,通過提高運算單元和存儲單元的利用率,能夠有效地減少變換時間和資源面積。以一個64 K點FFT處理器的設計為例,對2種方法進行了詳細分析。

1 FFT算法

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

長度為N的FFT變換可以寫為:

式中,k,n∈[0,N-1],N為運算點數。

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

式中,m∈[0,N/16-1];j∈[0,15];k∈[0,N-1],N為運算點數。

令

式中,i∈[0,15]。

觀察Yi可知,Yi為N/16點的FFT運算,可以將N點降為N/16點的FFT運算。

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

式中,X(k+jN/16)表示基16運算的第 j個輸出點,而Yi則可以通過N/16點FFT來實現,從而實現迭代運算。

2 提高運算單元的利用率

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

在這種載入、運算和輸出順序進行的結構中,只有數據全部輸入后運算單元才開始工作,同樣,只有運算全部結束后才能進行數據輸出。這樣在大點數FFT變換中,輸入輸出會占用大量時間,而此時運算單元則處于空閑狀態。因此,對變換過程進行了改進,將輸入的部分數據與運算數據重疊,輸出的部分數據也可與運算數據重疊,使得運算單元能夠在數據輸入或輸出的同時進行運算,減少其在整個變換過程中的空閑時間。

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

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

以64 K點的FFT為例,此設計采用的是16輸入的基16蝶形運算,共需4級,每級4 K個時鐘周期的運算時間。不同階段變換的重疊部分示意圖如圖1所示。

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

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

輸出時采用數據倒序輸出。根據蝶算單元中基4倒序輸出的規律,當第4級蝶算每時鐘周期產生16個變換結果時,將這16個結果數據中的第1個直接進行輸出,其余數據仍存放回原位置。完成第4級蝶算共需要4 K個時鐘周期,可以輸出4 K個數據,這樣就實現了邊運算邊輸出,變換和輸出有了4 K個時鐘周期的重疊,如圖1(b)所示。

3 提高存儲單元的利用率

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

下面同樣以64 K點的FFT設計來進行詳細介紹。設計中使用了必需的4組RAM,每組16 K,以及部分緩沖RAM。

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

圖2 載入時RAM整體使用示意圖

輸出時RAM使用示意圖如圖3所示,斜線表示未運算數據,方格表示正在進行運算的數據,網格表示等待輸出的數據。

圖3 輸出時RAM使用示意圖

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

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

第4級運算時,第1組(中的第1塊)RAM就可以同時輸出數據,也能夠夠載入新的數據。當第4級運算結束后,第1組RAM開始純粹的輸出。第1組RAM輸出完畢后,依次序是第2、第3和第4組 RAM輸出。數據輸出的存儲單元就可以載入新的數據了。

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

4 結束語

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

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

[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處理器設計[J].遙測遙控,2005,26(6):46-49.

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

[5]程培青.數字信號處理教程[M].北京:清華大學出版社,1995.

[6]趙 鑫.VHDL與數字電路設計[M].北京:機械工業出版社,2005.

[7]高西全,丁玉美,闊永紅.數字信號處理-原理、實現及應用[M].北京:電子工業出版社,2006.