詳解快速傅里葉變換fft算法

1、詳解快速傅里葉變換 詳解快速傅里葉變換 FFT FFT 算法 算法 快速傅里葉變換 FFT 是離散傅里葉變換 DFT 的一種快速算法，只有 FFT 才能在現(xiàn)實(shí)中有實(shí)際應(yīng)用的意義。雖然許多學(xué)過數(shù)字信號處理這門課的同學(xué)都知道 DFT 和 FFT，但實(shí)際上真正理解其算法 原理的屈指可數(shù)，絕大部分同學(xué)知其然而不知其所以然，況且限于高校課程教學(xué)體制，課堂上不可 能把這些原理和算法講得明明白白的。為此，特意以本文講解 FFT 算法的原理與實(shí)際應(yīng)用，

2、給欲往電子信息類專業(yè)進(jìn)修和發(fā)展的同學(xué)一些課外參考。 N 點(diǎn)有限長序列 x(n)的 DFT 為 10( ) ( )WNnk NnX k x n????其中2 j nk nk NN W e? ? ?其逆變換 IDFT 為 101 x(n) X(k)WNnkNn N???? ?正逆變換的運(yùn)算量都是相同的。x(n)和 X（k）都是復(fù)數(shù)序列，計(jì)算一個(gè) X(k)值，需要 N 次復(fù)數(shù)乘法和 N-1 次復(fù)數(shù)加法。X(k)有 N 個(gè)點(diǎn)，所以總共需要 N*

3、N 次復(fù)數(shù)乘法和 N(N-1)次復(fù)數(shù)加法。復(fù)數(shù)運(yùn)算實(shí)際上是通過實(shí)數(shù)運(yùn)算來完成的。上式可以寫成： ? ? ? ? ? ?? ?10( ) Re ( ) Im ( ) Re ImNnk nkN NnX k x n j x n W j W??? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?10Re ( ) Re Im ( ) Im Re ( ) Im Im ( ) ReNnk nk nk nkN N

4、 N Nnx n W x n W j x n W x n W??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?由此可見，一次復(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ù)加法

5、。 當(dāng) N 足夠大， N>>1 時(shí)， 直接計(jì)算 DFT的乘法次數(shù)和加法次數(shù)都是和 N 的平方成正比。當(dāng) N=1024 時(shí)，DFT 的運(yùn)算量為 1048576 次，即一百 多萬次復(fù)乘運(yùn)算， 一塊嵌入式 32 位處理器的最高速度為 105 百萬指令每秒， 那么它要完全計(jì)算這個(gè)DFT 的時(shí)間最快也要 1 秒，期間還是獨(dú)占 CPU 所有運(yùn)算資源且不能有任何其他的中斷請求。這樣計(jì)算量太龐大，計(jì)算速遞太慢了，談不上實(shí)時(shí)性，根本沒有實(shí)用意

6、義。 所以，我們就要利用 DFT 的系數(shù)的固有特性來簡化計(jì)算，減少運(yùn)算量。特性如下： 1. 共軛對稱性：( )* nk nkN N W W ? ?2. 周期性： ( ) ( ) nk n N k n k NN N N W W W ? ? ? ?3. 可約性： //nk nmk nk mN N N m W W W ? ?得出： ( ) ( ) n N k N n k nkN N N W W W ? ? ? ? ?/2 1

7、N N W ? ? ( /2) k N kN N W W ? ? ?利用上述這些系數(shù)性質(zhì)就可以合并 DFT 某些項(xiàng)的計(jì)算從而減少計(jì)算量。下面僅給出按時(shí)間抽選再將 N/2 分解為兩個(gè) N/4 點(diǎn) DFT，那么 8 點(diǎn) DFT 則可分解成四個(gè) N/4=2 點(diǎn) DFT。 利用四個(gè) N/4 點(diǎn)的 DFT 及兩級蝶形組合運(yùn)算來計(jì)算 N 點(diǎn) DFT， 比只用一次分解的組合方式的計(jì)算量又減少了一半。 DFT 的運(yùn)算量集中在 N 點(diǎn) DFT