第七講快速傅里葉變換fft(存儲版)
【正文】 . . . xxxxxxxx輸入數(shù)據(jù)、中間運算結(jié)果和最后輸出均用同一存儲器。 n?A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) 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) 變址處理方法 存儲單元 自然順序 變址 倒位序 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 自然順序 n 二進制 n n 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。 (1)DIT輸入為倒位序 ,輸出為自然順序； DIF正好與此相反。 此方法雖然兩次取共軛 ， 但由于可以與 FFT共用一程序 ， 因而使用十分方便 。 (3)m=3 時的距離為 8/8=1。 造成倒位序的原因是輸入 x(n)按標(biāo)號 n的偶奇的不斷分組而造成 。 N＝ 2M點的 FFT共進行 M級運算 ， 每級運算有 N/2個蝶形運算構(gòu)成；同一級中 ， 每個蝶形的兩個輸入數(shù)據(jù)只對計算本蝶形有用 ， 并且每個蝶形的輸入 、 輸出數(shù)據(jù)節(jié)點又同在一條水平線上 ， 這意味著計算完一個蝶形后所得數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存貯單元 ， 這樣 ， 經(jīng)過 M級運算后 ， 原來存放輸入序列數(shù)據(jù)的 N個存貯單元中并依次存放了 X(k)的 N個值 。 由此可見 ， 僅僅經(jīng)過一次分解就能使運算量減少近一半 ！ 因為 N/2仍然是偶數(shù)，可以作進一步的分解： 與第一次分解相同，將 x1(r)按奇偶分解成兩個 N/4的子序列 x3(l)和 x4(l), 即： 則， X1(k)又可表示為： 同理， X3(k)和 X4(k)的周期性和 WN的對稱性，到最后我們能夠得到： 同理可得： 其中： 這樣 ， 又將 N/2點的 DFT分解為兩個 N/4點的 DFT。 FFT的發(fā)展歷程： 1965年 ， J. W. Cooley和 J. W. Tukey巧妙應(yīng)用 DFT中W因子的周期性及對稱性提出了最早的 FFT， 這是基于時間抽取的 FFT。 例如： N＝ 1024時 , 需要 1,048,576次復(fù)數(shù)乘法 , 即4,194,304次實數(shù)乘法 對于象雷達(dá) 、 通信 、 聲納等需要實時處理的信號 ，因為其運算量更大 ， 所以無法滿足信號處理的實時性要求 。 在 N較大時計算量很大 。 FFT發(fā)展的原因 ： DFT是信號分析與處理中的一種重要變換 ， 廣泛應(yīng)用于通信 、 圖像處理 、 雷達(dá)及聲納等領(lǐng)域 ， 由于其計算量與變換區(qū)間長度 N的平方成正比 ， 在 N較大時 ， 計算量很大 ， 使得直接應(yīng)用 DFT進行實時處理信號是不現(xiàn)實的 。 所以按剛才的方法計算 N點 DFT總的運算量為 2(N/2)2+N/2=N
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1