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

第四章快速傅里葉變換FFT:FastFourierTransform學(xué)習(xí)目標(biāo)理解按時間抽選的基-2FFT算法的算法原理、運(yùn)算流圖、所需計算量和算法特點(diǎn)引言FFT:

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

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

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

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

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

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

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

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

m位，把右邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。

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