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