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

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

2、給欲往電子信息類專業(yè)進修和發(fā)展的同學(xué)一些課外參考。 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???? ?正逆變換的運算量都是相同的。x(n)和 X（k）都是復(fù)數(shù)序列，計算一個 X(k)值，需要 N 次復(fù)數(shù)乘法和 N-1 次復(fù)數(shù)加法。X(k)有 N 個點，所以總共需要 N*

3、N 次復(fù)數(shù)乘法和 N(N-1)次復(fù)數(shù)加法。復(fù)數(shù)運算實際上是通過實數(shù)運算來完成的。上式可以寫成： ? ? ? ? ? ?? ?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ù)乘法和 2 次實數(shù)加減法。一次復(fù)數(shù)加法需要 2 次實數(shù)加法。所以每一個 X（k）計算需要 4N 次實數(shù)乘法以及 2N+2(N-1)=2(2N-1)次實數(shù)加法。整個 DFT 運算總共需要 4N*N 次實數(shù)乘法和 N*2(2N-1)=2N(2N-1)次實數(shù)加法

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

6、義。 所以，我們就要利用 DFT 的系數(shù)的固有特性來簡化計算，減少運算量。特性如下： 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 某些項的計算從而減少計算量。下面僅給出按時間抽選再將 N/2 分解為兩個 N/4 點 DFT，那么 8 點 DFT 則可分解成四個 N/4=2 點 DFT。 利用四個 N/4 點的 DFT 及兩級蝶形組合運算來計算 N 點 DFT， 比只用一次分解的組合方式的計算量又減少了一半。 DFT 的運算量集中在 N 點 DFT