數(shù)字信號(hào)處理(程佩青第三版課件)第四章快速傅里葉變換fft(編輯修改稿)
2025-03-20 14:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 出倒位序的 FFT流圖 例 用 FFT算法處理一幅 NN點(diǎn)的二維圖像，如用每秒可做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng) N=1024時(shí)，問(wèn)需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？ ?解 當(dāng) N=1024點(diǎn)時(shí)， FFT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為 次，僅為直接計(jì)算 DFT所需時(shí)間的 10萬(wàn)分之一。 即原需要 3000小時(shí)，現(xiàn)在只需要 2分鐘。 167。 按頻率抽取（ DIF）的 FFT算法q 與 DITFFT算法類似分解，但是抽取的是 X(k)。 即分解 X(k)成奇數(shù)與偶數(shù)序號(hào)的兩個(gè)序列。q 設(shè)： N = 2L， L 為整數(shù)。將 X(k)按 k的奇偶分組前，先將輸入 x(n)按 n的順序分成前后兩半：（ DecimationInFrequency)一、算法原理下面討論按 k的奇偶將 X(k)分成兩部分：顯然：令：用蝶型結(jié)構(gòu)圖表示為：x1(0)x1(1)1x1(2)x1(3)1x2(0)x2(1)1x2(2)x2(3)1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)N/2仍為偶數(shù)，進(jìn)一步分解： N/2 → N/4x3(0)x3(1)11x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)q 按照以上思路繼續(xù)分解，即一個(gè) N/2的 DFT分解成兩個(gè) N/4點(diǎn) DFT， 直到只計(jì)算 2點(diǎn)的 DFT， 這就是 DIFFFT算法。2個(gè) 1點(diǎn)的 DFT蝶形流圖 進(jìn)一步簡(jiǎn)化為蝶形流圖：1點(diǎn) DFTx3(0)1點(diǎn) DFTx3(1)X(0)X(4)X(0)X(4)x3(0)x3(1)二、按頻率抽取 FFT蝶形運(yùn)算特點(diǎn)1）原位計(jì)算1L級(jí)蝶形運(yùn)算，每級(jí) N/2個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)：m表示第 m級(jí)迭代， k， j表示數(shù)據(jù)所在的行數(shù)2）蝶形運(yùn)算對(duì) N=2L點(diǎn) FFT， 輸入自然序，輸出倒位序，兩節(jié)點(diǎn)距離： 2Lm=N / 2m第 m級(jí)運(yùn)算：q 蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為 k值，表示成L位二進(jìn)制數(shù)，左移 m1位，把右邊空出的位置補(bǔ)零，結(jié)果為 r的二進(jìn)制數(shù)。存儲(chǔ)單元輸入序列 x(n) : N個(gè)存儲(chǔ)單元
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1