§7-3-按頻率抽取的FFT算法

§7-3

按頻率抽取的FFT算法一、按頻率抽取的算法原理二、按頻率抽取的算法特點(diǎn)三、與按時(shí)間抽取算法的對(duì)稱性1一、按頻率抽取的算法原理設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。假設(shè)不滿足，那么補(bǔ)零將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半23那么x(n)的DFT:4按k的奇偶將X(k)分成兩局部：令5那么X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點(diǎn)DFT，記為X1(k)和X2(k)6x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/478x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)逐級(jí)分解，直到2點(diǎn)DFT9同理：其中：3NW-12NW-11NW-10NW-1x[0]x[4]x[1]x[5]x[2]x[6]x[3]x[7]4點(diǎn)DFTX[0]X[6]X[2]X[4]4點(diǎn)DFTX[1]X[3]X[5]X[7]11X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2點(diǎn)DFT-1-12NW0NW-1-12點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT120NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-1時(shí)間抽取和頻率抽取FFT算法：二、按頻率抽取的算法特點(diǎn)131.計(jì)算速度當(dāng)N=2L時(shí)，共有L級(jí)蝶形，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：無論從流圖結(jié)構(gòu)，還是從計(jì)算速度來看，按時(shí)間抽取算法和按頻率抽取算法這兩種FFT算法是完全等價(jià)的。2.排序規(guī)那么輸入序列x〔n〕是自然順序的，輸出序列X〔k是倒置順序的。其整序規(guī)那么與按時(shí)間抽取算法是完全一致的。14

3.同址運(yùn)算該算法和按時(shí)間抽取算法一樣也是進(jìn)行同址運(yùn)算的。4.蝶距規(guī)律其蝶形系數(shù)的分布規(guī)律與按時(shí)間抽取算法是完全對(duì)稱的。15三、與按時(shí)間抽取算法的對(duì)稱性二者具有完全對(duì)稱的蝶距規(guī)律蝶形結(jié)構(gòu)