怎樣用FPGA實現(xiàn)FFT算法？
cc FFT算法除了必需的數(shù)據(jù)存儲器ram和旋轉(zhuǎn)因子rom外，仍需較復(fù)雜的運算和控制電路單元，即使現(xiàn)在實現(xiàn)長點數(shù)的FFT仍然是很困難。本文提出的FFT實現(xiàn)算法是基于FPGA之上的，算法完成對一個序列的FFT計算，完全由脈沖觸發(fā)，外部只輸入一脈沖頭和輸入數(shù)據(jù)，便可以得到該脈沖頭作為起始標(biāo)志的N點FFT輸出結(jié)果。這個算法實現(xiàn)的可以是基2/4混合基FFT，也可以是純基4FFT和純基2FFT運算。
傅立葉變換和逆變換
對于變換長度為N的序列x（n）其傅立葉變換可以表示如下：
其中，W=exp(-2π/N)。當(dāng)點數(shù)N較大時，必須進(jìn)行分解，以短點數(shù)實現(xiàn)長點數(shù)的變換。而IDFT的實現(xiàn)在DFT的基礎(chǔ)上就顯得較為簡單了：
由第二個可以看出，在FFT運算模塊的基礎(chǔ)上，只需將輸入序列進(jìn)行取共軛后再進(jìn)行FFT運算，輸出結(jié)果再取一次共軛便實現(xiàn)了對輸入序列的IDFT運算，因子1/N對于不同的數(shù)據(jù)表示格式具體實現(xiàn)時的處理方式是不一樣的。IDFT在FFT的基礎(chǔ)上輸入和輸出均有一次共軛操作，但它們共用一個內(nèi)核，仍然是十分方便的。
基4和基2?
基4和基2運算流圖及信號之間的運算關(guān)系如圖1所示：、
以基4為例，令A(yù)=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運算的四個等式中有：
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)
可以看出有多個公共項和類似項，這一點得到充分利用之后可以大大縮減基4和基2運算模塊中的乘法器的個數(shù)，如上面A'至D'的四個等式中的這三對類似項：(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ù)率的時鐘進(jìn)行時分復(fù)用，最終可以做到只需要3個甚至1個復(fù)數(shù)乘法器便可以實現(xiàn)。
基2運算之所以采用圖1-(b)中的形式進(jìn)行基2運算，是為了將基本模塊做成基4/2復(fù)用模塊，它對于N有著更大的適用性和可借鑒性。在基4、基2和基4/2模塊的基礎(chǔ)上，構(gòu)建基16、基8和基16/8模塊有著非常大的意義。
算法實現(xiàn)?
傅立葉變換實現(xiàn)時首先進(jìn)行基2、基4分解，一般來說，如果算法使用基4實現(xiàn)，雖然使用的資源多了一些，但速度上的好處足以彌補。如果資源充足，使用基16、基8或基16/8復(fù)用模塊，速度可以大大提高。一般FFT實現(xiàn)簡單框圖如圖2所示。
在圖2中，運算模塊即為基2/4/8/16模塊或它們的復(fù)用模塊，Rom表中存儲的是N點旋轉(zhuǎn)因子表?？刂颇K產(chǎn)生所有的控制信號，存儲器1和2的讀寫地址、寫使能、運算模塊的啟動信號及因子表的讀地址等信號。當(dāng)然對于運算模塊為基16/8復(fù)用模塊時，控制模塊就需要產(chǎn)生模式選擇信號，如對于運算模塊是基4/2模塊時，該信號就決定了內(nèi)部運算模塊是進(jìn)行基4運算還是基2運算。
存儲器1作為當(dāng)前輸入標(biāo)志對應(yīng)輸入N點數(shù)據(jù)的緩沖器，存儲器2作為中間結(jié)果存儲器，用于存儲運算模塊計算出的各Pass的結(jié)果。在圖中的各種地址、使能和數(shù)據(jù)的緊密配合下，經(jīng)過一定延時后輸出計算結(jié)果及其對應(yīng)指示標(biāo)志。
圖2只是一定點或浮點的FFT實現(xiàn)模塊，如果是塊浮點運算，則必須加入一個數(shù)據(jù)因子控制器，控制每遍運算過程中的數(shù)據(jù)大小，并根據(jù)各個Pass的乘性因子之和的大小，對最終輸出進(jìn)行大小控制，以保證每段FFT運算輸出增益一致。
