按時間抽取的FFT算法

FFT算法分類:時間抽選法

DIT:Decimation-In-Time頻率抽選法

DIF:Decimation-In-Frequency§7-2按時間抽取的FFT算法§7-2

按時間抽取的FFT算法一、按時間抽取的算法原理二、按時間抽取的算法特點三、按時間抽取FFT算法的其他形式22023/9/2一、按時間抽取的算法原理設(shè)序列點數(shù)N=2L，L為整數(shù)。若不滿足，則補零N為2的整數(shù)冪的FFT算法稱基-2FFT算法。將序列x(n)按n的奇偶分成兩組：32023/9/24則x(n)的DFT:2023/9/25再利用周期性求X(k)的后半部分2023/9/26一個“蝶形運算”包含1次乘法，2次加法2023/9/272023/9/2復(fù)數(shù)乘法復(fù)數(shù)加法一個N/2點DFT(N/2)2N/2(N/2–1)兩個N/2點DFTN2/2N(N/2–1)一個蝶形12N/2個蝶形N/2N總計8分解后的運算量：運算量減少了近一半2023/9/2N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/492023/9/210同理：其中：這樣逐級分解，直到2點DFT基2時間抽取FFT算法流圖11N=2x[k]={x[0],x[1]}2023/9/24點基2時間抽取FFT算法流圖12x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2點DFT2點DFT-1-1-1-1X

[0]X

[1]X

[2]X

[3]2023/9/2132023/9/24點基2時間抽取FFT算法流圖8點基2時間抽取FFT算法流圖144點DFT4點DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-12023/9/2154點DFT4點DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-18點基2時間抽取FFT算法流圖2023/9/2基2時間抽取FFT算法16第一級第二級第三級2023/9/2二、按時間抽取的算法特點171.計算速度當(dāng)N=2L時，共有L級蝶形，每級N/2個蝶形，每個蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT

2023/9/2182023/9/2算法的計算復(fù)雜度19復(fù)乘次數(shù)NN22023/9/2例.如果一臺通用計算機的速度為平均每次復(fù)乘，每次復(fù)加，用它來計算512點的，問直接計算需要多少時間，用運算需要多少時間。解：(1)直接利用計算：復(fù)乘次數(shù)為，復(fù)加次數(shù)為。

復(fù)乘所需時間復(fù)加所需時間所以直接利用DFT計算所需時間：2023/9/220復(fù)乘所需時間復(fù)加所需時間所以用FFT

計算所需時間(2)利用計算：復(fù)乘次數(shù)為，復(fù)加次數(shù)為。2023/9/2212.倒序排列n0n1n200011011001101倒位序自然序00000000100410010102201011063011001141001015510101136110111771112223倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]010101012023/9/2

3