第七講快速傅里葉變換（fft）-全文預(yù)覽
【正文】 7 自然順序 n 二進(jìn)制 n n n 倒位序二進(jìn)制 n n n 倒位順序 n ^ 2 1 0 0 1 2 例如 ， N=8時(shí)如下表： :2m1 其中 ,m表示第 m列 ,且 m =1,… ,L 例如 N=8=23 ,第一級(jí) (列 )距離為 211=1, 第二級(jí) (列 )距離為 221=2， 第三級(jí) (列 )距離為 231=4。 (0)=X0(0) X1(0) X2(0) X3(0)=X(0) (4)=X0(1) X1(1) X2(1) X3(1)=X(1) (2)=X0(2) X3(2)=X(2) (6)=X0(3) X3(3)=X(3) (1)=X0(4) X1(4) X2(4) X3(4)=X(4) (5)=X0(5) X3(5)=X(5) (3)=X0(6) X3(6)=X(6) (7)=X0(7) X1(7) X2(7) X3(7)=X(7) W W W W N 0 N 0 N 0 N 0 1 1 1 1 W W W WN 0 N 2 N 0 N 2 1 1 1 1 W W W W N N N N 0 1 2 3 . . . . . . . . . . . xxxxxxxx輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。 易知 N越大 ， 優(yōu)越性越明顯 。 一個(gè)完整的 8點(diǎn) DFTFFT運(yùn)算流圖如下圖所示 。 計(jì)算一個(gè) N/2點(diǎn) DFT需要 (N/2)2復(fù)數(shù)乘和 N/2(N/21)次復(fù)數(shù)加法 。上述運(yùn)算可用右下圖來(lái)表示，稱為蝶形運(yùn)算符號(hào)。 三、 FFT發(fā)展簡(jiǎn)介 FFT的實(shí)質(zhì)： 快速傅里葉變換 (FFT)并不是一種新的變換 ， 是為了改進(jìn)和提高離散傅里葉變換 (DFT)運(yùn)算速度基于 DFT運(yùn)算特點(diǎn)而發(fā)展起來(lái)的 DFT快速算法 ， 其實(shí)質(zhì)還是 DFT。 二、 DFT運(yùn)算的特點(diǎn) 實(shí)際上 ， DFT運(yùn)算中包含有大量的重復(fù)運(yùn)算 。 一、直接計(jì)算 DFT存在的問(wèn)題 N點(diǎn)序列 x(n)的 DFT變換定義為： 1,2,1,0 )(1)(1,2,1,0 )()(1010?????????????NnWkXNnxNkWnxkXNkknNNnknN??計(jì)算 X(k)的運(yùn)算量：需要 N2次復(fù)數(shù)乘法 ， N(N－ 1)次復(fù)數(shù)加法 。A 辦公室 : 51971617 手 機(jī)： 13466573224 Email: 本講在分析直接計(jì)算 DFT的特點(diǎn)的基礎(chǔ)上介紹DFT的快速算法 快速傅里葉變換 (FFT)；同時(shí)簡(jiǎn)要介紹了 FFT算法的發(fā)展歷程；此外還要介紹 FFT的兩種最常用的算法－－基于時(shí)間抽取的 FFT（ DIT：庫(kù)利－圖基算法 ） 和基于頻率抽取的 FFT（ DIF：桑德－圖基算法 ） 。 迫切需要有新的算法 。 例如 ， 對(duì)于四點(diǎn)的 DFT， 直接計(jì)算需要 16次復(fù)數(shù)乘法 ， 根據(jù)上述特性可以有以下形式的算法： 第二列和第三列交換，則： 則有： 由此得出： 從上例可知 ， 通過(guò)應(yīng)用對(duì)稱性和周期性 ， 4點(diǎn)的 DFT實(shí)際上只需要進(jìn)行一次復(fù)數(shù)乘法 。 具有里程碑式的貢獻(xiàn) (運(yùn)算量縮短兩個(gè)數(shù)量級(jí) ) 1966年 ， G. Sand提出了基于頻
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1