數(shù)字信號處理第四章

第四章快速傅里葉變換FFT:FastFourierTransform學習目標理解按時間抽選的基-2FFT算法的算法原理、運算流圖、所需計算量和算法特點引言FFT:

FastFourierTransform1965年，Cooley-Turky發(fā)表文章《機器計算傅里葉級數(shù)的一種算法》，提出FFT算法，解決DFT運算量太大，在實際使用中受限制的問題。FFT的應用。頻譜分析、濾波器實現(xiàn)、系統(tǒng)分析等。DSP芯片實現(xiàn)。TI公司的TMS320c30，10MHz時鐘，基2-FFT1024點FFT時間15ms。一、直接計算DFT的問題及改進途徑運算量復數(shù)乘法復數(shù)加法一個X(k)NN–1N個X(k)(N點DFT)N2N(N–1)實數(shù)乘法實數(shù)加法一次復乘42一次復加2一個X(k)4N2N+2(N–1)=2(2N–1)N個X(k)(N點DFT)4N22N(2N–1)FFT算法分類:時間抽選法

DIT:Decimation-In-Time頻率抽選法

DIF:Decimation-In-Frequency二、按時間抽選的基-2FFT算法1、算法原理設序列點數(shù)N=2L，L為整數(shù)。若不滿足，則補零將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。N/2點DFT則x(n)的DFT:再利用周期性求X(k)的后半部分由兩個N/2點DFT得到N點DFT分解后的運算量：復數(shù)乘法復數(shù)加法一個N/2點DFT(N/2)2N/2(N/2–1)兩個N/2點DFTN2/2N(N/2–1)一個蝶形12N/2個蝶形N/2N總計運算量減少了近一半N/2仍為偶數(shù)，進一步分解：N/2N/4這樣逐級分解，直到2點DFT當N=8時，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1計算2點DFT也是一個基本蝶形運算

2、運算量當N=2L時，共有L級蝶形，每級N/2個蝶形，每個蝶形有1次復數(shù)乘法2次復數(shù)加法。復數(shù)乘法：復數(shù)加法：比較DFT3、算法特點1）原位計算（同址運算）m表示第m級迭代，k，j表示數(shù)據(jù)所在的行數(shù)蝶形運算輸出可以放回輸入的存儲器地址2）倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111輸入

輸出0041226314553677x(n)X(k)3）蝶形運算蝶形運算兩節(jié)點間距離對N=2L點FFT，輸入倒位序，輸出自然序，

第m級運算每個蝶形的兩節(jié)點距離為2m–1

每個蝶形兩節(jié)點距離22－1＝2

蝶形運算兩節(jié)點的第一個節(jié)點為k值，表示成L位二進制數(shù)，左移L–

m位，把右邊空出的位置補零，結果為r的二進制數(shù)。

r=(101)*23-2=0104）存儲單元輸入序列x(n):N個存儲單元系數(shù)：N/