4.2按時(shí)間抽選的基-2FFT算法設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。若不滿足，則補(bǔ)零1、將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。一、算法原理則x(n)的DFT:再利用周期性求X(k)的后半部分時(shí)間抽選法蝶形運(yùn)算流圖符號(hào)按時(shí)間抽選，將一個(gè)N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N/2點(diǎn)DFT(N/2)2(N/2)(N/2–1)兩個(gè)N/2點(diǎn)DFTN2/2N(N/2–1)一個(gè)蝶形12N/2個(gè)蝶形N/2N總計(jì)結(jié)論：運(yùn)算量減少了近一半N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4同理：其中：圖4-4按時(shí)間抽選，將一個(gè)N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)DFT這樣逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1

圖4-5

N＝8按時(shí)間抽選法FFT運(yùn)算流圖二、DIT-FFT算法的特點(diǎn)1、運(yùn)算結(jié)構(gòu)DIT-FFT的運(yùn)算結(jié)構(gòu)由如圖所示的蝶形運(yùn)算結(jié)構(gòu)組合而成

時(shí)，一共分了

每級(jí)包含碟形運(yùn)算數(shù)由此推廣到的情況：一共需分解成L級(jí)運(yùn)算，每級(jí)包含個(gè)碟形運(yùn)算，總共碟形運(yùn)算個(gè)數(shù)為個(gè)。

運(yùn)算量當(dāng)N=2L時(shí)，共有L級(jí)蝶形，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形需1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT

2、原位運(yùn)算及存儲(chǔ)單元1）原位計(jì)算m表示第m級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)，k,j節(jié)點(diǎn)變量經(jīng)蝶形運(yùn)算后仍放回k,j節(jié)點(diǎn)，只需N個(gè)存儲(chǔ)單元。按時(shí)間抽選碟形運(yùn)算結(jié)構(gòu)3、倒位序的實(shí)現(xiàn)倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n200011011001101存儲(chǔ)單元A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)自然順序輸入x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)

變址倒位序x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)

倒位序的變址處理4.蝶形運(yùn)算兩結(jié)點(diǎn)的距離對(duì)N=2L點(diǎn)FFT，輸入倒位序，輸出自然序，第1級(jí)（每碟形）兩點(diǎn)距離為1，第2級(jí)為2，第3級(jí)為4，第m級(jí)運(yùn)算每個(gè)蝶形的兩節(jié)點(diǎn)距離為2m–1第m級(jí)運(yùn)算：[例4-2]

設(shè)x(n)={0,1,0,1,1,1}，現(xiàn)對(duì)x(n)進(jìn)行譜分析。畫出按時(shí)間抽選基-2FFT的流程圖并計(jì)算出每級(jí)碟形運(yùn)算的結(jié)果。解：首先將序列x(n)={0,1,0,1,1,1}進(jìn)行補(bǔ)零值點(diǎn)成為8點(diǎn)有限長(zhǎng)序列：x(n)={0,1,0,1,1,1,0,0}這樣，按時(shí)間抽選的基-2FFT的流程圖如圖4-8所示。第一級(jí)蝶形運(yùn)算的結(jié)果：第二級(jí)蝶形運(yùn)算的結(jié)果：

第三級(jí)蝶形運(yùn)算的結(jié)果：