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

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

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

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

DIF:Decimation-In-Frequency二、按時(shí)間抽選的基-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)的后半部分由兩個(gè)N/2點(diǎn)DFT得到N點(diǎn)DFT分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N/2點(diǎn)DFT(N/2)2N/2(N/2–1)兩個(gè)N/2點(diǎn)DFTN2/2N(N/2–1)一個(gè)蝶形12N/2個(gè)蝶形N/2N總計(jì)運(yùn)算量減少了近一半N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4這樣逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1計(jì)算2點(diǎn)DFT也是一個(gè)基本蝶形運(yùn)算

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

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

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

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

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

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

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