離散傅立葉變換DTFT、DFT和FFT在工程與數學結合的通俗理解
1。離散時間傅立葉變換DTFT
何為DTFT?就是對連續時間非週期訊號進行抽樣(乘積),得到的離散時間非週期訊號再求傅立葉變換的過程就是DTFT。其實等同於訊號頻譜與脈衝訊號頻譜的卷積,這樣得到的就是連續且週期DTFT頻譜(把頻譜進行了週期延拓),如下圖所示。
2。離散傅立葉變換DFT
DFT其實是在DTFT的頻譜上進行取樣,使得頻譜離散化(頻譜和抽樣訊號進行乘積),這也等同於將時域訊號進行了卷積,與取樣訊號卷積就是週期延拓,得到週期離散時間訊號。
那麼在數字訊號角度分析,首先從DFT公式入手:
首先x(n)的最大週期我們可以確定下來,也就是數字處理時所擷取的那一段週期,由上面公式可知其取樣點的數目為N,最大週期T=1(角頻率w=2π,T=w/2π),即可得知x(n)的最小頻率為1(除零外),且頻率最小間隔也為1;
為了簡單化理解,我們把指數部分透過尤拉變回正餘弦表示,且幅度相位都不要了,那麼該公式就可以解釋為x(n)的N個離散值與sin(2πkn)被分成了N份的值進行相乘:
當k=1時,有
此時n取0-N,就是把2π分成了N份,每一個都對應的一個正弦值,再將每個值分別與x(n)對應值相乘後再累加,最後得到的就是這個頻率2π/2π=1時的分量!
同理可得,X(2)、X(3)。。。。。、X(N)都是按照這個方式進行計算,這樣就可以得到每個頻率的分量大小,這也就是工程上DFT變換的本質。
看了這麼多,似乎有點費腦子,要不休息一會,打把王者??
我們繼續,經過DFT例項計算後我們會發現,頻譜是中間對稱的,這又是咋回事呢?
其實這個不難理解,把每一個k對應的正弦在座標軸裡面畫出來後,會發現其實就是在圓上取點,如下情況:
k=2時,θ=0、4π/N、…… 、4π(N-1)/N
。。。。。
k=N-2時,θ=0、(2πN-4π)/N、(4πN-8π)/N、…… 、(2πN*(N-1)-4π*(N-1))/N
k=N-2進行三角變換後:
θ=0、4π/N、8π/N、…… 、4π(N-1)/N
這下就可以發現,k=N-2時與k=2時相等,這是因為他們在圓上取點是相同的,因此有中心對稱的值都是相等的。
既然所有的角度相等了,那麼正弦取值也相等,再與x(n)相乘求和必定也相等,
因此頻譜是中間對稱的,因此進行傅立葉變換後只採用其一半的頻譜進行計算。
簡單總結一下:
1。在DFT中,是將2pi、4pi、6pi、。。。、2kpi分別分成了N份,每一個都是對應k的正餘弦的最小變化步長。
2。當被採集訊號的時間長度被確定時,其最小頻率和最小頻率間隔也被確定,即為1/T;那麼每一個三角函式的間隔也被確定,即原有最小頻率的整數倍k;
3。最小角頻率以及最小角頻率的整數倍角頻率的三角函式可以表示出待求函式x(n);(注意頻率和角頻率的區別)
4。離散傅立葉變換得到的頻譜是中心對稱的頻譜,只取前N/2分析即可
那麼為何不同頻率的三角函式與原函式相乘求和就可以得到每一個頻率的分量,怎麼區別開每一個頻率的,不同頻率間不會互相干擾嗎?
這就涉及到了傅立葉級數完備正交基的概念,可以參考之前寫的文章:
舞曜:傅立葉級數和傅立葉變換的巧妙之處
3。快速傅立葉變換FFT
簡單來說FFT是DFT的最佳化演算法,是在計算機出來之後,減少DFT的計算複雜度的演算法,他的核心精髓是利用係數
的特性對DFT進行簡化:
(1) 對稱性
(2)週期性
(3)可約性
具體FFT推導咱不說,咱們關注的是結果,是工程什麼的應用,故在進行一個N個取樣點時,所需計算量如下所示:
1) DFT常規計算時
計算一個X(K)的值需要運算量
複數乘法次數:N ;複數加法次數:N-1
DFT計算全部X(K)的值需要運算量
複數乘法次數:N^2 ;複數加法次數:N*(N-1)
2) 在使用FFT計算時
DFT計算全部X(K)的值需要運算量
複數乘法次數:
;複數加法次數:
要注意的是,在計算機中,一次複數乘法需要透過4次實數乘法和2次實數加法實現。因此FFT在很大程度上減少了計算量,其實無論DFT就是把資料以某種方程變成另外一種資料,而FFT就是把這個方程的計算量進行了最佳化簡化,僅此而已。
在FFT中,值得借鑑的是FFT最佳化DFT的方法思路,利用了係數
的特徵,深究其數學特性的意義,對以後的演算法設計最佳化有很好的參考價值,也對未來的科研道路有所幫助。
以上乃是本人小生對離散傅立葉變換在工程上使用和數學公式所結合的通俗理解,希望能夠和大家共同探討,也願能夠對大家的學習和科研有所幫助,與知友、智友共勉之。
上一篇:基於引力模型的城市聯絡度分析
下一篇:心動的那個瞬間