第3章_FFT(1)

1、3.1 引言：引言： 1. DFT運(yùn)算量的估計(jì)運(yùn)算量的估計(jì) 設(shè)x(n)為復(fù)序列，則計(jì)算每一X(k)需1010)(1)()()(NknkNNnnkNWkXNnxWnxkX N次復(fù)乘（N-1）次復(fù)加完成一次DFT計(jì)算需（k=0,1,2N-1）若用實(shí)數(shù)乘法統(tǒng)計(jì)：復(fù)乘運(yùn)算：(a+jb)(c+jd)=(ac-bd)+j(ad+bc) =(a-b)d+a(c-d)+j(a-b)d+b(c+d)完成一次DFT計(jì)算運(yùn)算量為： 2. 提高提高DFT運(yùn)算效率途徑運(yùn)算效率途徑 利用 的性質(zhì)：周期性、可約性、共軛對(duì)稱性周期性、可約性、共軛對(duì)稱性 把長(zhǎng)序列化解成短序列進(jìn)行計(jì)算，通過疊代運(yùn)算來減少 DFT的運(yùn)算量。N2次

2、復(fù)乘N（N-1）次復(fù)加 N2實(shí)乘：4N2實(shí)加：2N(N-1)+2N2=4N2-2NnkNW(3次實(shí)乘，5次實(shí)加)3. 基（基（Radix）的定義：）的定義：在FFT運(yùn)算中最小DFT單元序列的長(zhǎng) 度稱為基基；4. FFT按分解方法不同可分為：按分解方法不同可分為： Radix2 (N=2m) 時(shí)間抽選(DIT)Decimation In Time頻率抽選(DIF) Decimation In Frequency) 1 () 0() 1 () 0() 1 () 0(1111) 1 () 0() 1 () 0() 1 , 0() 1 () 0()()(1202020222102xxxxxxxxWWW

3、WXXkWxWxWnxkXkknnk實(shí)質(zhì)性乘法：指除去(1), (j)之外所需的乘法； 例：3點(diǎn)DFT（用于Radix3） )2(x) 1 (x)0(xWWWWWWWWW)2(x) 1 (x)0(xWWWWWWWWW)2(X) 1 (X)0(X13230323130303030343230323130303030313232313WWWW13232313WWWW(Butterfly Computation)2 , 1 , 0()2() 1 ()0()()(23303203kWxWxWxWnxkXkknnk) 1 ( x)0( x)0(X1) 1 (X三點(diǎn)信號(hào)流圖： x(0) X(0) x(1)

4、 X(1) x(2) X(2) 13W23W23W43W 5.高效算法標(biāo)準(zhǔn)：高效算法標(biāo)準(zhǔn)： 乘、加次數(shù)最少； 算法結(jié)構(gòu)的簡(jiǎn)單程度；（取指方便） 算法占用的存儲(chǔ)量少；3。2 時(shí)間抽選時(shí)間抽選FFT算法算法(Radix 2DITFFT) N=2m 1.算法原理：算法原理：時(shí)間抽選是把n序號(hào)按奇、偶分解 例：N=8=23 x(n)= （ 也稱為信號(hào)的多相分解）0, 2, 4, 6=x(2r)=e(r) E(k)N/21, 3, 5, 7=x(2r+1)=f(r) F(k)N/2(0rN/2) )k(FW)k(E)2Nk(X)k(FW)k(E)k(X)k(FW)k(EW)1r2(xW)r2(x)k(X

5、kNkN2/NkN2/Nk)1r2(N12N0rrk2N12N0r(0kN-1)12Nk0 其流圖如教材圖3.2.2 先做二個(gè)N/2點(diǎn)的DFT需2(N/2)2次乘法； 再做(N/2)個(gè)2點(diǎn)的DFT勿需任何乘法； 級(jí)間需(N/2)個(gè)旋轉(zhuǎn)因子旋轉(zhuǎn)因子(TwiddleFactor FFT Algorithm)； 經(jīng)第一次分解后，總共需復(fù)乘次數(shù)：mc= 2(N/2)2+N/2=N/2(N+1)E(0)E(1)E(2)E(3)F(0)F(1)F(2)F(3)再次分解如圖3.2.3完整的8點(diǎn)流圖如3.2.4x0 x1 x2 x3 2. Radix 2DITFFT算法特點(diǎn)算法特點(diǎn): (1)分解級(jí)數(shù)： FFT

6、點(diǎn)數(shù)為：N=2m, 則總共有m級(jí)； 每級(jí)共有（N/2）個(gè)蝶形運(yùn)算 xL-1(i) xL(i) xL-1 (j) xL (j) xL(i)= xL-1(i)+ xL-1 (j) xL(j)= xL-1(i) xL-1 (j) 1rNWrNWrNW (2)運(yùn)算量估計(jì)： 每個(gè)蝶形運(yùn)算需：復(fù)乘次數(shù) 1 次；復(fù)加次數(shù) 2 次 總共所需復(fù)乘和復(fù)加次數(shù)： 如果考慮去除 ，則復(fù)乘次數(shù)可減至 如果再去除 ，則復(fù)乘次數(shù)可減至 與直接計(jì)算相比較 (圖3.2.5)N(logN)2(logNNma)N(log2N)2(log2N2Nmm2m2c2m2c0NW) 1N()N(log2Nm2c4NNW)2N23(Nlog2

7、Nm2cNlogN2Nlog2NNK222 (3)原位運(yùn)算（In place） 利用同一存儲(chǔ)單元存儲(chǔ)蝶形輸入、輸出數(shù)據(jù)的方法； (4)序列的倒位序排列 目的：滿足同址運(yùn)算的要求； 表示方法： 實(shí)現(xiàn)：表3.2.2變址處理：IJ，不做處理 I=J不做交換；IJ已經(jīng)交換完了，不再交換； IJ , 進(jìn)行交換； 軟件編程實(shí)現(xiàn)：圖3.2.8, 虛框表示逆記數(shù)；21020122nn2n2nnn2n2n0ni1i=0, 1, 2 3.3 N=8=222, Radix 2DITFFT的數(shù)學(xué)表示式及其對(duì)應(yīng)的數(shù)學(xué)表示式及其對(duì)應(yīng) 的流圖的流圖 1。運(yùn)算表示式及幾點(diǎn)說明 設(shè)置變量及其維數(shù)；0n01 0k01 0n11

8、0k11 0n21 0k21 列寫輸入輸出 n、k的表達(dá)式： 列出運(yùn)算表示式，并對(duì)n分解（DI T），分別化簡(jiǎn)：01222102kk2k2knn2n2n互為倒序表示：)0k1k22k22)(2n1n20n22(8102n2102101n100nW)nn2n2(x)k(X )W)nn2n2(x(WWW)nn2n2(x002100122201221210012202kn210n10n10n01220)kk2k2(n8)kk2k2(n2810n10n10n)kk2k2(n280122001kn28W()W11kn48)kk2(n8012W()W22kn4810n10n0122121)kn2n2(x(

9、01kn28W)W11kn2)kk2(n8012W()W22kn4801kn28W()kk2(n8012W(01kn28W)kk2(n8012W(10n012222)kk2n2(x)kk2(n8012W22kn2W)k(X)kk2k2(x01223說明：(1) n、k 互為倒序排列（與要求的流圖排序無關(guān)）； (2) FFT運(yùn)算是一逐級(jí)疊代過程，每次求和消去一個(gè)ni 代之以ki； (3) 求和運(yùn)算時(shí)，若DI T，則按n做分解；若DI F，則 按k做分解，對(duì)表示式進(jìn)行化簡(jiǎn)； (4) n表示式中的最高位，表示流圖的第一級(jí)，不管n k如何表示，求和總是從n表示式中最高位開始； (5) 同一表示式可以有

10、多個(gè)流圖與之對(duì)應(yīng)； 2. 根據(jù)表示式畫出相應(yīng)的流圖： 輸入倒序輸出正序形式)nnn(nnn2n2n2, 1,02102 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 )k,k,k(kkk2k2k0120122 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 101kn28W)kk2(n8012W3.組的概念：流圖中的每一組有相同的結(jié)構(gòu)和相同的 分布 結(jié)構(gòu)包括：蝶形運(yùn)算類型；運(yùn)算結(jié)點(diǎn)的間距rNWL=1L=2L=3 組的計(jì)算：第L級(jí)有： 組，每組內(nèi)有 種蝶形， 每個(gè)蝶形的間距 ； 旋轉(zhuǎn)因子的分布： 例：

11、設(shè)FFT的點(diǎn)數(shù)為N=256=28，輸入為倒位序排列，問第 L=5級(jí)，有幾組蝶形，每組有幾種蝶形，每個(gè)蝶形的間距 是幾點(diǎn)，旋轉(zhuǎn)因子共有幾個(gè)，具體值是什么？ 解： 有23=8組蝶形，每組內(nèi)有256/(82) =16 種蝶形， 每個(gè)蝶形的間距是16點(diǎn)，Lm21L21L2i2N2i22i2LmLmLmLLWWW) 12(1Li=(0, 1, 2, 3 )76524334251607nn2n2n2n2n2n2n2n旋轉(zhuǎn)因子分布： (0i15)具體蝶形運(yùn)算形式： xL-1(i) xL(i) xL-1 (j) xL (j) j=i+ 3.4 Radix-2 DITFFT的其他流圖形式：的其他流圖形式： 其他

12、流圖形式的獲取原則：保持各結(jié)點(diǎn)所連的支路及 其傳輸系數(shù)不變，只是數(shù)據(jù)的提取和存放次序的不 同。（見圖3.4.1 3.4.2） i82562i256i32i2WWWW3Li2NLmW1L2)nnn(nnn2n2n2, 1,02102)k,k,k(kkk2k2k0120122 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 101kn28W 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1)kk2(n8012W輸入正序輸出倒位序排列的流圖：級(jí)間幾何圖形相同的DI TFFT流圖（圖3.4.2） 3。2 頻率抽選

13、頻率抽選FFT算法算法(Radix 2DIFFFT) N=2m 1. 基本原理：基本原理：DIF是把X(k)分解成短序列(對(duì)k分解) 12N0nnr2NnN12N0nnr2N12N0nnkNk12N0nk)2Nn(N12N0nnkN1N2NnnkN12N0nnkNWW)2Nn(x)n(x)1r2(X1r2kW)2Nn(x)n(x)r2(Xr2kW)1)(2Nn(x)n(xW)2Nn(xW)n(xW)n(xW)n(x)k(X逐次分解流圖表示：nNW N=23=8點(diǎn)DI FFFT完整流圖： 基本蝶形運(yùn)算： xL-1(i)o o o oxL(i) xL-1(j)o o o oxL(j)1rNW xL

14、(i)=xL-1(i)+xL-1(j) xL(j)=xL-1(i) xL-1(j)rNW 2. N=8=222, Radix 2DIFFFT的數(shù)學(xué)表示式及其對(duì)應(yīng) 的流圖 1) Radix 2DIFFFT的數(shù)學(xué)表示式： 設(shè)置變量及其維數(shù)； 0n01 0k01 0n11 0k11 0n21 0k21 列寫輸入輸出 n、k的表達(dá)式： 互為倒序表示： 列出運(yùn)算表示式，并對(duì)k分解（DI F），分別化簡(jiǎn)：21020122kk2k2knn2n2n)kk2k2)(nn2n2(810n012210n10n21020122012W)nn2n2(x)k(X000111010001110122201201222012

15、21012012202nk2nk28nk210n10n01221nk2nk28nk2)nn2(k8kn210n10n10n0122)nn2n2(k8)nn2n2(k2810n10n10n)nn2n2(k280122WW)W)nn2k2(x()W)(WW()W)(W)nn2n2(x(WWW)nn2n2(x)nn2(k8012W01nk28W01nk28W)kk2k2(xWW)nk2k2(x01223nk2nk2810n012220001001nk28W)nnn(nnn2n2n0, 1,20122)k,k,k(kkk2k2k2102102 =X(k) 2) 流圖表示： 0 0 0 1 0 0 0

16、1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 10 0 00 0 10 1 00 1 11 0 01 0 1 1 1 01 1 101nk28W)nn2(k8012W 3) DI T與DI F的關(guān)系： 相同點(diǎn)： 分解級(jí)數(shù)都是m級(jí)； 乘法次數(shù)都是 ； 都是同址運(yùn)算； 都有不同流圖對(duì)應(yīng)相同的表達(dá)式； 區(qū)別：蝶形運(yùn)算結(jié)構(gòu)不同： DI TFFTNlog2N2DI FFFT由DI TFFT碟形解出： xL-1(i)= （xL(i)+xL(j)） xL-1(j)= xL-1(i) xL-1(j)若去除 ，并把 改為 ，即為DI F蝶形流圖， DI T和DI F在流圖形式上互為轉(zhuǎn)置關(guān)系。r

17、NW2121rNWrNW21 4) 用DI T與DI F的組合來過濾x(n)DI TFFTDI FIFFTx(n) 正 y(n)正倒倒H(k) 5) 如何用DFT（FFT）模塊做I FFT？ 3.6 高組合數(shù)的高組合數(shù)的FFT算法算法旋轉(zhuǎn)因子算法旋轉(zhuǎn)因子算法 （混合基FFT，多基多進(jìn)制算法） 1。N為組合數(shù)時(shí)，DI TFFT算法原理： N=N0N1N2Nm-1=M0 Nm-1 物理概念見教材(p.139)M0設(shè)：0m05，0n22； 0 5，0k22 n=3m0+n2 k=6 k2+ 2222202022222020222020kn3n18m620n2050m)k6(n18)k6(m31820

18、n2050m)k6)(nm3(1820n2050mWW)W)nm3(x(WW)nm3(xW)nm3(x)k(X22n18W 對(duì)應(yīng)流圖見教材圖3.6.1； 經(jīng)第一次分解后乘法次數(shù)的估算： mc=3 62+18+6 32=18022互為倒序排列 2。N=18=233分解的DI TFFT運(yùn)算表示式及其流圖 （見教材p.141和圖3.6.3） 3。算法特點(diǎn)： 1)混合基FFT： 定義； DI T、DIF的物理概念及其具體做法； 2) 廣義倒序： 定義； 廣義倒序排序方法：式(3.6.7) 、(3.6.8) 3) 旋轉(zhuǎn)因子算法概念 （與之對(duì)應(yīng)的是素因子算法：p.148） 4）旋轉(zhuǎn)因子算法運(yùn)算量估計(jì)n0n

19、1n2012210kkkknnnn 3 9 26oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo210nn3n9nn(n0, n1, n2) 0 0 0 x(0) 1 0 0 x(9) 0 1 0 x(3) 1 1 0 x(12) 0 2 0 x(6) 1 2 0 x(15) 0 0 1 x(1) 1 0 1 x(10) 0 1 1 x(4) 1 1 1 x(13) 0 2 1 x(7) 1 2 1 x(16) 0 0 2 x(

20、2) 1 0 2 x(11) 0 1 2 x(5) 1 1 2 x(14) 0 2 2 x(8) 1 2 2 x(17)k,k,k(kkk2k6k012012X(0) 0 0 0X(1) 0 0 1X(2) 0 1 0X(3) 0 1 1X(4) 0 2 0X(5) 0 2 1X(6) 1 0 0X(7) 1 0 1X(8) 1 1 0X(9) 1 1 1X(10) 1 2 0X(11) 1 2 1X(12) 2 0 0X(13) 2 0 1X(14) 2 1 0X(15) 2 1 1X(16) 2 2 0X(17) 2 2 111111111101kn318W)kk2(n18012W318W018W618W018W018W018W018W018W318W318W618W618W018W118W218W318W418W518W018W218W4