|
|
|
詳解快速傅里葉變換 FFT 算法
下面是部分內(nèi)容預(yù)覽：
快速傅里葉變換 FFT 是離散傅里葉變換 DFT 的一種快速算法，只有 FFT 才能在現(xiàn)實(shí)中有實(shí)際應(yīng)用的意義。雖然許多學(xué)過(guò)數(shù)字信號(hào)處理這門課的同學(xué)都知道 DFT 和 FFT，但實(shí)際上真正理解其算法原理的屈指可數(shù)，絕大部分同學(xué)知其然而不知其所以然，況且限于高校課程教學(xué)體制，課堂上不可能把這些原理和算法講得明明白白的。為此，特意以本文講解 FFT 算法的原理與實(shí)際應(yīng)用，給欲往電子信息類專業(yè)進(jìn)修和發(fā)展的同學(xué)一些課外參考。
N點(diǎn)有限長(zhǎng)序列x(n)的DFT 為
0.png (71.34 KB, 下載次數(shù): 128)
下載附件
2017-11-1 02:00 上傳
由此可見，一次復(fù)數(shù)乘法需要 4 次實(shí)數(shù)乘法和 2 次實(shí)數(shù)加減法。一次復(fù)數(shù)加法需要 2 次實(shí)數(shù)加法。所以每一個(gè) X（k）計(jì)算需要 4N次實(shí)數(shù)乘法以及2N+2(N-1)=2(2N-1)次實(shí)數(shù)加法。整個(gè) DFT運(yùn)算總共需要 4N*N次實(shí)數(shù)乘法和 N*2(2N-1)=2N(2N-1)次實(shí)數(shù)加法。當(dāng) N足夠大，N>>1 時(shí)，直接計(jì)算DFT
的乘法次數(shù)和加法次數(shù)都是和 N的平方成正比。當(dāng)N=1024 時(shí)，DFT的運(yùn)算量為 1048576次，即一百多萬(wàn)次復(fù)乘運(yùn)算，一塊嵌入式 32位處理器的最高速度為 105百萬(wàn)指令每秒，那么它要完全計(jì)算這個(gè)DFT 的時(shí)間最快也要 1 秒，期間還是獨(dú)占 CPU 所有運(yùn)算資源且不能有任何其他的中斷請(qǐng)求。這樣計(jì)
算量太龐大，計(jì)算速遞太慢了，談不上實(shí)時(shí)性，根本沒(méi)有實(shí)用意義。
所以，我們就要利用DFT 的系數(shù)的固有特性來(lái)簡(jiǎn)化計(jì)算，減少運(yùn)算量。特性如下：
0.png (122.93 KB, 下載次數(shù): 153)
下載附件
2017-11-1 02:02 上傳
0.png (165.45 KB, 下載次數(shù): 132)
下載附件
2017-11-1 02:02 上傳
0.png (109.11 KB, 下載次數(shù): 136)
下載附件
2017-11-1 02:03 上傳
完整的pdf格式文檔51黑下載地址（共17頁(yè)）：
詳解快速傅里葉變換FFT算法帶程序.pdf
(1.72 MB, 下載次數(shù): 748)
2017-10-31 22:41 上傳
點(diǎn)擊文件名下載附件
下載積分: 黑幣 -5
|
評(píng)分
-
查看全部評(píng)分
|
[復(fù)制鏈接]
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
