新版第4章-快速傅里葉變換(-f-f-t)-課件ppt-wenkub.com
2025-08-13 01:09 本頁(yè)面
【正文】 (2) DHT的正、逆變換（除了因子 1/N外）具有相同的形式。 ?所以，對(duì)實(shí)序列一定存在更高效的快速算法。而一次復(fù)數(shù)乘法需要四 次實(shí)數(shù)乘法和二次實(shí)數(shù)加法。 ?在基 rFFT算法中，基 4FFT算法運(yùn)算效率與基 8FFT很 接近，但基 4FFT算法實(shí)現(xiàn)程序簡(jiǎn)單，且判斷開(kāi)銷(xiāo)少。 本章僅介紹算法最簡(jiǎn)單、編程最容易的基 2FFT算法原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究 FFT算法的主要途徑和編程思路。 第二種方法是用 N/2點(diǎn) FFT計(jì)算一個(gè) N點(diǎn)實(shí)序列的 DFT。 這樣使運(yùn)算速度大大提高，其不足之處是占 ?? )/π2c o s ( NmW mN)/π2s i n (j Nm?mNW第 4章 快速傅里葉變換 (FFT) 實(shí)序列的 FFT算法 在實(shí)際工作中，數(shù)據(jù) x(n)常常是實(shí)數(shù)序列。顯然， 碟形單元類(lèi)型越多，編程就越復(fù)雜，但當(dāng) N較大時(shí)，乘法運(yùn)算的減少量是相當(dāng)可觀的。 8/NNW第 4章 快速傅里葉變換 (FFT) 在 DITFFT運(yùn)算流圖中，從 L=3至 L=M級(jí)，每級(jí)都包含旋轉(zhuǎn)因子 ，第 L級(jí)中， 對(duì)應(yīng) N/2L個(gè)蝶形運(yùn)算。這樣，從 L=3至 L=M共減少?gòu)?fù)數(shù)乘法次數(shù)為 0NW 4/NNW( 2 )2M NCM?? () 第 4章 快速傅里葉變換 (FFT) 因此， DITFFT的 復(fù)乘次數(shù)降至 ?下面再討論 FFT中特殊的復(fù)數(shù)運(yùn)算，以便進(jìn)一步減少 復(fù)數(shù)乘法次數(shù)。當(dāng) L=3時(shí)，有兩個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子 和 ，因?yàn)橥恍D(zhuǎn)因子對(duì)應(yīng)著 2M－ L=N/2L個(gè)碟形運(yùn)算，所以第三級(jí)共有 2在 DFT中，又稱(chēng)其值為 177。 knNW?pNW pNW?knNW第 4章 快速傅里葉變換 (FFT) 如果希望直接調(diào)用 FFT子程序計(jì)算 IFFT，則可用 由于 所以，可以先將 X(k)取復(fù)共軛，然后直接調(diào)用 FFT子程序，最后取復(fù)共軛并乘以 1/N得到序列 x(n)。比較DFT和 IDFT的運(yùn)算公式： 1010( ) D F T [ ( ) ] ( )1( ) I D F T [ ( ) ] ( ) NknNnNknNkX k x n x n Wx n X k X k WN???????????第 4章 快速傅里葉變換 (FFT) ?只要將 DFT運(yùn)算式中的系數(shù) 改為 ，最后乘以 1/N，就是 IDFT運(yùn)算公式。 ?觀察圖 ， DIFFFT算法與 DITTTF算法類(lèi)似， 共有 M級(jí)運(yùn)算，每級(jí)共有 N/2個(gè)蝶形運(yùn)算，所以?xún)煞N算法 的運(yùn)算次數(shù)亦相同。以這種方 式分解下去，經(jīng)過(guò) M－ 1次分解，最后分解為 2M－ 1個(gè) 兩點(diǎn) DFT， 兩點(diǎn) DFT就是一個(gè)基本蝶形運(yùn)算流圖 。x1(n)、 x2(n)和 x(n)之間的關(guān)系也可用圖 形運(yùn)算流圖符號(hào)表示。 N=23=8 pNWpNW第 4章 快速傅里葉變換 (FFT) 對(duì) N=2M的一般情況，第 L級(jí)的旋轉(zhuǎn)因子為： 3,2,1,0 31,0 20 1222/24/????????????JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時(shí)時(shí)時(shí)L12 , 0 , 1 , 2 , , 2 1LpJNW W J? ? ?第 4章 快速傅里葉變換 (FFT) 因?yàn)? 所以 MLMLML N ?? ???? 222212,2,1,0 122 ???? ??? ?? LJNJNpN JWWW LMML（ ） LMJp ??? 2 （ ） 這樣，就可按 ()和 ()式 確定第 L級(jí)運(yùn)算的旋轉(zhuǎn)因子 。但各級(jí)的旋轉(zhuǎn)因子都有所不同。 ?同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有 用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一條水 平線(xiàn)上，這就意味著計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù) 可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元 (數(shù)組元素 )。圖 FFT算法和直接計(jì)算 DFT所需復(fù)數(shù)乘法次數(shù) CM與變換點(diǎn)數(shù) N的關(guān)系曲線(xiàn)。因此，每一級(jí)運(yùn)算都需要 N/2次復(fù)數(shù)乘和 N次復(fù)數(shù)加(每個(gè)蝶形需要兩次復(fù)數(shù)加法 )。圖中用到關(guān)系式 。既然這樣分解對(duì)減少 DFT的運(yùn)算量是有效的，且N=2M, N/2仍然是偶數(shù)，故可以對(duì) N/2點(diǎn) DFT再作進(jìn)一步分解。 () 1210)()()( 21 ???? NkkXWkXkX kN ， ?() 1210)()()2( 21 ????? NkkXWkXNkX kN ， ?第 4章 快速傅里葉變換 (FFT) 圖 蝶形運(yùn)算符號(hào) 偶數(shù)點(diǎn)的N/2 DFT 奇數(shù)點(diǎn)的N/2 DFT kNW序列 DFT的 N/2個(gè)點(diǎn) 序列 DFT的后 N/2個(gè)點(diǎn) 第 4章 快速傅里葉變換 (FFT) 圖 8點(diǎn) DFT一次時(shí)域抽取分解運(yùn)算流圖 第 4章 快速傅里葉變換 (FFT) 由圖 ，要完成 一個(gè)蝶形運(yùn)算 ，需要 一次復(fù)數(shù)乘法 和 兩次復(fù)數(shù)加法 運(yùn)算。按 n的奇偶 把 x(n)分解為兩個(gè) N/2點(diǎn)的子序列 12( ) ( 2 ) 0 1 12( ) ( 2 1 ) 0 1 12Nx r x r rNx r x r r? ? ?? ? ? ?， ， ， ， ， ， ，第 4章 快速傅里葉變換 (FFT) 則 x(n)的 DFT為 / 2 1 / 2 12 ( 2 1 )00/ 2 1 / 2 1221200( ) ( ) ( )( 2 ) ( 2 1 )( ) ( )k n k nNNnnNNk r k rNNrrNNk r k k rN N NrrX k x n W x n Wx r W x r Wx r W W x r W?????????????? ? ?????????偶 數(shù) 奇 數(shù)因?yàn)? 2 π2 π jj22 2/2eekrkrk r k rNNNNWW??? ? ?所以 / 2 1 / 2 11 / 2 2 / 20012(
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1