第七講快速傅里葉變換fft-展示頁
2024-10-29 12:48本頁面
【正文】 運(yùn)算流圖如下圖所示 。 由此可見 ， 僅僅經(jīng)過一次分解就能使運(yùn)算量減少近一半 ！ 因?yàn)?N/2仍然是偶數(shù)，可以作進(jìn)一步的分解： 與第一次分解相同，將 x1(r)按奇偶分解成兩個(gè) N/4的子序列 x3(l)和 x4(l), 即： 則， X1(k)又可表示為： 同理， X3(k)和 X4(k)的周期性和 WN的對(duì)稱性，到最后我們能夠得到： 同理可得： 其中： 這樣 ， 又將 N/2點(diǎn)的 DFT分解為兩個(gè) N/4點(diǎn)的 DFT。 計(jì)算一個(gè) N/2點(diǎn) DFT需要 (N/2)2復(fù)數(shù)乘和 N/2(N/21)次復(fù)數(shù)加法 。 下圖是 N＝ 8時(shí)的一個(gè)分解運(yùn)算圖。上述運(yùn)算可用右下圖來表示，稱為蝶形運(yùn)算符號(hào)。 FFT的發(fā)展歷程： 1965年 ， J. W. Cooley和 J. W. Tukey巧妙應(yīng)用 DFT中W因子的周期性及對(duì)稱性提出了最早的 FFT， 這是基于時(shí)間抽取的 FFT。 三、 FFT發(fā)展簡介 FFT的實(shí)質(zhì)： 快速傅里葉變換 (FFT)并不是一種新的變換 ， 是為了改進(jìn)和提高離散傅里葉變換 (DFT)運(yùn)算速度基于 DFT運(yùn)算特點(diǎn)而發(fā)展起來的 DFT快速算法 ， 其實(shí)質(zhì)還是 DFT。 總之 ， WN因子具有如下所述周期性及對(duì)稱性： 由上述特性還可得出： 利用上述對(duì)稱特性 ， 可使 DFT運(yùn)算中有些項(xiàng)可以合并 ， 這樣 ， 可使乘法次數(shù)減少大約一半；利用 WN矩陣的對(duì)稱性及周期性 ， 可以將長序列的 DFT分解為短序列的 DFT， N越小 ， 運(yùn)算量能夠減少 。 二、 DFT運(yùn)算的特點(diǎn) 實(shí)際上 ， DFT運(yùn)算中包含有大量的重復(fù)運(yùn)算 。 例如： N＝ 1024時(shí) , 需要 1,048,576次復(fù)數(shù)乘法 , 即4,194,304次實(shí)數(shù)乘法 對(duì)于象雷達(dá) 、 通信 、 聲納等需要實(shí)時(shí)處理的信號(hào) ，因?yàn)槠溥\(yùn)算量更大 ， 所以無法滿足信號(hào)處理的實(shí)時(shí)性要求 。 一、直接計(jì)算 DFT存在的問題 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ù)加法 。第七講 快速傅里葉變換 (FFT) Qamp。A 辦公室 : 51971617 手 機(jī)： 13466573224 Email: 本講在分析直接計(jì)算 DFT的特點(diǎn)的基礎(chǔ)上介紹DFT的快速算法 快速傅里葉變換 (FFT)；同時(shí)簡要介紹了 FFT算法的發(fā)展歷程；此外還要介紹 FFT的兩種最常用的算法－－基于時(shí)間抽取的 FFT（ DIT：庫利－圖基算法 ） 和基于頻率抽取的 FFT（ DIF：桑德－圖基算法 ） 。 在 N較大時(shí)計(jì)算量很大 。 迫切需要有新的算法 。 在 WN 矩陣中 ， 雖然其中有 N2個(gè)元素 ， 但由于 WN的周期性 ， 其中只有 N個(gè)獨(dú)立的值 ， 即 ， 且這 N個(gè)值也有一些對(duì)稱關(guān)系 。 例如 ， 對(duì)于四點(diǎn)的 DFT， 直接計(jì)算需要 16次復(fù)數(shù)乘法 ， 根據(jù)上述特性可以有以下形式的算法： 第二列和第三列交換，則： 則有： 由此得出： 從上例可知 ， 通過應(yīng)用對(duì)稱性和周期性 ， 4點(diǎn)的 DFT實(shí)際上只需要進(jìn)行一次復(fù)數(shù)乘法 。 FFT發(fā)展的原因 ： DFT是信號(hào)分析與處理中的一種重要變換 ， 廣泛應(yīng)用于通信 、 圖像處理 、 雷達(dá)及聲納等領(lǐng)域 ， 由于其計(jì)算量與變換區(qū)間長度 N的平方成正比 ， 在 N較大時(shí) ， 計(jì)算量很大 ， 使得直接應(yīng)用 DFT進(jìn)行實(shí)時(shí)處理信號(hào)是不現(xiàn)實(shí)的 。 具有里程碑式的貢獻(xiàn) (運(yùn)算量縮短兩個(gè)數(shù)量級(jí) ) 1966年 ， G. Sand提出了基于頻率抽取的 FFT算法 1975年 ， Winogard提出 WFTA法； 1977年 Kolha和Parks提出素因子算法 （ PFA） 1984年 ， P. Dohamel和 H. Holl
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1