用FPGA實(shí)現傅立葉變換算法

由式(2)可以看出，在FFT運算模塊的基礎上，只需將輸入序列進(jìn)行取共軛后再進(jìn)行FFT運算，輸出結果再取一次共軛便實(shí)現了對輸入序列的IDFT運算，因子1/N對于不同的數據表示格式具體實(shí)現時(shí)的處理方式是不一樣的。IDFT在FFT的基礎上輸入和輸出均有一次共軛操作，但它們共用一個(gè)內核，仍然是十分方便的。

基4和基2
基4和基2運算流圖及信號之間的運算關(guān)系如圖1所示：

　　　　
　　?。╝）基４蝶形算法 　　　　　　

　　　　　　　　　?。╞）基２蝶形算法
以基4為例，令A=r0+j×i0；B=r1+j×i1；C=r2+j×i2；D=r3+j×i3；Wk0=c0+j×s0：Wk1=c1+j×s1；Wk2=c2+j×s2；Wk3=c3+j×s3。分別代入圖1中的基4運算的四個(gè)等式中有：
A'=[r0+(r1×c1-i1×s1)+(r2×c2-i2×s2)+(r3×c3-i3×s3)]+j[i0+(i1×c1+r1×s1)+(i2×c2+r2×s2)+(i3×c3+r3×s3)] 式(3)
B'=[r0+(i1×c1+r1×s1)-(r2×c2-i2×s2)-(i3×c3+r3×s3)]+j[i0-(r1×c1-i1×s1)-(i2×c2+r2×s2)+(r3×c3-i3×s3)] 式(4)
C'=[r0-(r1×c1-i1×s1)+(r2×c2-i2×s2)-(r3×c3-i3×s3)]+j[i0-(i1×c1+r1×s1)+(i2×c2+r2×s2)-(i3×c3+r3×s3)] 式(5)
D'=[r0-(i1×c1+r1×s1)-(r2×c2-i2×s2)+(i3×c3+r3×s3)]+j[i0+(r1×c1-i1×s1)-(i2×c2+r2×s2)-(r3×c3-i3×s3)] 式(6)
　　可以看出，式(3)至式(6)有多個(gè)公共項和類(lèi)似項，這一點(diǎn)得到充分利用之后可以大大縮減基4和基2運算模塊中的乘法器的個(gè)數，如上面A'至D'的四個(gè)等式中的這三對類(lèi)似項：(r1×c1-i1×s1)與(i1×c1+r1×s1)、(r2×c2-i2×s2)與(i2×c2+r2×s2)、(r3×c3-i3×s3)與(i3×c3+r3×s3)以高于輸入數據率的時(shí)鐘進(jìn)行時(shí)分復用，最終可以做到只需要3個(gè)甚至1個(gè)復數乘法器便可以實(shí)現?；?運算之所以采用圖1-(b)中的形式進(jìn)行基2運算，是為了將基本模塊做成基4/2復用模塊，它對于N有著(zhù)更大的適用性和可借鑒性。在基4、基2和基4/2模塊的基礎上，構建基16、基8和基16/8模塊有著(zhù)非常大的意義。

算法實(shí)現
　　傅立葉變換實(shí)現時(shí)首先進(jìn)行基2、基4分解，一般來(lái)說(shuō)，如果算法使用基4實(shí)現，雖然使用的資源多了一些，但速度上的好處足以彌補。如果資源充足，使用基16、基8或基16/8復用模塊，速度可以大大提高。一般FFT實(shí)現簡(jiǎn)單框圖如圖2所示。

　　在圖2中，運算模塊即為基2/4/8/16模塊或它們的復用模塊，Rom表中存儲的是N點(diǎn)旋轉因子表?？刂颇K產(chǎn)生所有的控制信號，存儲器1和2的讀寫(xiě)地址、寫(xiě)使能、運算模塊的啟動(dòng)信號及因子表的讀地址等信號。當然對于運算模塊為基16/8復用模塊時(shí)，控制模塊就需要產(chǎn)生模式選擇信號，如對于運算模塊是基4/2模塊時(shí)，該信號就決定了內部運算模塊是進(jìn)行基4運算還是基2運算。存儲器1作為當前輸入標志對應輸入N點(diǎn)數據的緩沖器，存儲器2作為中間結果存儲器，用于存儲運算模塊計算出的各Pass的結果。在圖中的各種地址、使能和數據的緊密配合下，經(jīng)過(guò)一定延時(shí)后輸出計算結果及其對應指示標志。圖2只是一定點(diǎn)或浮點(diǎn)的FFT實(shí)現模塊，如果是塊浮點(diǎn)運算，則必須加入一個(gè)數據因子控制器，控制每遍運算過(guò)程中的數據大小，并根據各個(gè)Pass的乘性因子之和的大小，對最終輸出進(jìn)行大小控制，以保證每段FFT運算輸出增益一致。

　　外部輸入為N點(diǎn)數據段流和啟動(dòng)信號(N點(diǎn)之間如無(wú)間隔，則每N數據點(diǎn)輸入一脈沖信號)，一方面，外部數據存入存儲器1中，同時(shí)通過(guò)控制模塊的控制，讀出存儲器1中的前段N點(diǎn)數據和Rom表中的因子及相關(guān)控制信號送入運算核心模塊進(jìn)行各個(gè)Pass的運算，每個(gè)Pass的輸出都存入存儲器2中，最后一個(gè)Pass的計算結果存入存儲器2中，并在下一個(gè)啟動(dòng)頭到來(lái)后，輸出計算結果。對圖2的實(shí)現，除去運算模塊，關(guān)鍵是各個(gè)Pass數據因子讀寫(xiě)地址及控制信號的配合。

速度、資源和精度

　　假定輸入數據的速率為fin，則每數據的持續時(shí)間T=1/fin，運算模塊的計算時(shí)鐘頻率為fa，對于N(N=2p，p即為Pass數目)點(diǎn)FFT計算時(shí)延與Pass數目直接相關(guān)。如果使用基2運算不考慮控制開(kāi)銷(xiāo)，純粹的計算時(shí)延為td=p×N×T×fin/fa。顯然在fa>p× fin時(shí)，在N點(diǎn)內可完成FFT運算。否則不能完成，即不能實(shí)現流型的變換。這在N很大且輸入數據速率較高時(shí)以FPGA實(shí)現幾乎是不可能的，而且內部計算時(shí)鐘過(guò)高容易導致電路的工作不穩定。設基2時(shí)的最小可流型工作運算頻率為fa0，則使用基4實(shí)現流型的變換，計算時(shí)鐘fa= fa0就可以。而使用基8時(shí)計算時(shí)鐘fa= fa0便可完成，基16時(shí)為fa0的1/4。上面所討論的是純基運算，當N不為4的冪次方時(shí)(如N=2048=16×16×8，運算模塊為基16/8復用模塊)，而又希望使用較低倍的時(shí)鐘完成運算時(shí)，圖2中的運算模塊必然包括基4/2復用模塊(即基16/8復用模塊)，這也就是前面提到復用模塊的主要用意。由上面的分析可以得出結論，如果計算使用的基越大，完成速度越快。

　　但是，使用基16/8模塊所使用的邏輯資源要比基4/2模塊多將近一倍，這是因為基16/8復用模塊是以基4模塊和基4/2復用模塊構建而成。當然，可以直接實(shí)現基16/8復用模塊，但用FPGA很難解決復雜度和成本問(wèn)題。另外，如果流型運算間隔比N點(diǎn)數據長(cháng)度長(cháng)一倍以上，可以考慮在較低的計算時(shí)鐘下使用基2運算模塊實(shí)現流型FFT。

　　運算結果的精度直接與計算過(guò)程中數據和因子位數(浮點(diǎn)算法)相關(guān)，如果中間計算的位數、存儲數據位數和Rom表中的位數越大，輸出精度就越大。當然，位數增大后邏輯運算資源和存儲資源都會(huì )直線(xiàn)上升。

浮點(diǎn)、塊浮點(diǎn)和定點(diǎn)FFT
　　根據運算過(guò)程中對數據位數取位和表示形式的不同，可以將FFT分為浮點(diǎn)FFT、塊浮點(diǎn)FFT和定點(diǎn)FFT。它們在實(shí)現時(shí)對于系統資源的要求是不同的，而且有著(zhù)不同的適用范圍。

　　浮點(diǎn)FFT是基于數據表示為浮點(diǎn)的基礎之上的，即數據是由一純小數和一因子組成，輸入要轉成純小數和因子的浮點(diǎn)表示形式，所有計算過(guò)程中保存應得計算結果大小，而輸出要變成所需大小的定點(diǎn)表示形式。只要因子位數足夠大，浮點(diǎn)FFT計算是不會(huì )溢出的。而定點(diǎn)則是所有計算過(guò)程中都是定點(diǎn)運算，如果各個(gè)Pass的截位規則不適當，很容易出現溢出，必須要有溢出控制。塊浮點(diǎn)是介于它們之間的一種運算機制，它是根據本Pass的輸入數據的大小，在計算之前進(jìn)行控制(數據上移一比特或下移一比特或乘以一特定因子)，可以保證不溢出，但一般也需要溢出控制。

　　浮點(diǎn)運算沒(méi)有溢出，信號平均信噪比高，但由于因子的運算必然導致電路復雜，實(shí)現困難。定點(diǎn)運算實(shí)現簡(jiǎn)單，難以保證不溢出，需要統計得出合適的截位規則，否則溢出嚴重導致輸出結果錯誤。塊浮點(diǎn)由于每個(gè)Pass(包括最后輸出前)結束后有一統計控制過(guò)程，延時(shí)較大，但是可以保證不溢出而且電路又相對浮點(diǎn)來(lái)說(shuō)簡(jiǎn)單得多。

　　應根據具體應用的具體要求，選擇合適的FFT。如果要求精度，并且要解決頻域很高的單頻干擾，就必須使用浮點(diǎn)的FFT，使用數據位數很大的定點(diǎn)和塊浮點(diǎn)也能解決這個(gè)問(wèn)題，但位數的確定十分困難。如果不要求高精度，邏輯資源和Rom比較緊張，可考慮定點(diǎn)運算。如果輸入在頻域集中于幾個(gè)點(diǎn)上或者對精度要求一般，可以慢速處理，可以采用塊浮點(diǎn)運算，就能夠保證這幾點(diǎn)的信噪比，而忽略其他點(diǎn)處的信噪比。