新版第4章-快速傅里葉變換(-f-f-t)-課件ppt(編輯修改稿)
2025-09-12 01:09 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ，這就意味著計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù) 可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元 (數(shù)組元素 )。 ?這樣， 經(jīng)過(guò) M級(jí)運(yùn)算后，原來(lái)存放輸入序列數(shù)據(jù)的 N個(gè) 存儲(chǔ)單元 (數(shù)組 A)中便依次存放 X(k)的 N個(gè)值。 第 4章 快速傅里葉變換 (FFT) 8點(diǎn) DITFFT運(yùn)算流圖的畫(huà)法 第 4章 快速傅里葉變換 (FFT) 2． 旋轉(zhuǎn)因子的變化規(guī)律 如上所述， N點(diǎn) DITFFT運(yùn)算流圖中，每級(jí)都有 N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子 ，稱(chēng)其為 旋轉(zhuǎn)因子 ，p為旋轉(zhuǎn)因子的指數(shù)。但各級(jí)的旋轉(zhuǎn)因子都有所不同。 為了畫(huà)出蝶形圖，應(yīng)先找出旋轉(zhuǎn)因子 與運(yùn)算級(jí)數(shù)的關(guān)系。用 L表示從左到右的運(yùn)算級(jí)數(shù) (L=1， 2， … M)。觀(guān)察圖 ，第 L級(jí)共有 2L－ 1個(gè)不同的旋轉(zhuǎn)因子。 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)因子 。 第 4章 快速傅里葉變換 (FFT) 3． ?DITFFT算法的輸入序列的排序看起來(lái)似乎很亂，但仔 細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于 N=2M， 因此順序數(shù)可用 M位二進(jìn)制數(shù) (nM－ 1 nM－ 2… n1n0)表示。 ?表 N=8時(shí)以二進(jìn)制數(shù)表示的順序數(shù)和倒序 數(shù)，由表顯而易見(jiàn)， 只要將順序數(shù) (n2n1n0)的二進(jìn)制位 倒置，則得對(duì)應(yīng)的二進(jìn)制倒序值 (n0n1n2) 第 4章 快速傅里葉變換 (FFT) 表 第 4章 快速傅里葉變換 (FFT) 頻域抽取法 FFT(DIFFFT) 在基 2FFT算法中，頻域抽取法 FFT也是一種常用的快速算法，簡(jiǎn)稱(chēng) DTF FFT 設(shè)序列 x(n)長(zhǎng)度為 N=2M，首先將 x(n)前后對(duì)半分開(kāi) ，得到兩個(gè)子序列，其 DFT可表示為如下形式： 10/ 2 1 10 / 2/ 2 1 / 2 1( / 2 )00/ 2 1/20( ) D F T [ ( ) ] ( )( ) ( )()2()2NknNnNNk n k nNNn n NNNk n k n NNNnnNk N k nNNnX k x n x n Wx n W x n WNx n W x n WNx n W x n W???????????????????? ? ??????? ??? ? ???????????????第 4章 快速傅里葉變換 (FFT) 式中 ?將 X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng) k取 偶數(shù) (k=2m, m=0, 1, … , N/2－ 1)時(shí) /2 1( 1 )1k N kNkWk??? ? ?? ???偶 數(shù)奇 數(shù)，/ 2 120/ 2 1/20( 2 ) ( )2()2NmnNnNmnNnNX m x n x n WNx n x n W?????? ??? ? ??????????? ??? ? ??????????? （ ） 第 4章 快速傅里葉變換 (FFT) 當(dāng) k取奇數(shù) (k=2m+1, m=0, 1, … , N/2－ 1)時(shí)， 令 122102)()(2)()(21?????????????????????????????????NnWNnxnxnxNnxnxnxnN，，， ?/ 2 1( 2 1 )0/ 2 1/20( 2 1 ) ( )2()2NnmNnNn nmNNnNX m x n x n WNx n x n W W??????? ??? ? ? ??????????? ??? ? ? ??????????? () 第 4章 快速傅里葉變換 (FFT) 將 x1(n)和 x2(n)分別代入 ()和 ()式，可得 ()式表明， X(k)按奇偶 k值分為兩組，其偶數(shù)組是x1(n)的 N/2點(diǎn) DFT，奇數(shù)組則是 x2(n)的 N/2點(diǎn) DFT。x1(n)、 x2(n)和 x(n)之間的關(guān)系也可用圖 形運(yùn)算流圖符號(hào)表示。圖 N=8時(shí)第一次分解的運(yùn)算流圖。 / 2 11 / 20/ 2 12 / 20( 2 ) ( )( 2 1 ) ( )NmnNnNmnNnX m x n WX m x n W?????????? ?????? （ ） 第 4章 快速傅里葉變換 (FFT) 圖 DTF－ FFT蝶形運(yùn)算流圖符號(hào) 序列的前半部分 序列的后半部分 第 4章 快速傅里葉變換 (FFT) 圖 DIFFFT 第一次分解運(yùn)算流圖（ N=8） 第 4章 快速傅里葉變換 (FFT) ?由于 N=2M， N/2仍然是偶數(shù)，繼續(xù)將 N/2點(diǎn) DFT分成 偶數(shù)組和奇數(shù)組，這樣每個(gè) N/2點(diǎn) DFT又可由兩個(gè) N/4 點(diǎn) DFT形成，其輸入序列分別是 x1(n)和 x2(n)按上下對(duì) 半分開(kāi)形成的四個(gè)子序列。 ?圖 N=8時(shí)第二次分解運(yùn)算流圖。以這種方 式分解下去，經(jīng)過(guò) M－ 1次分解，最后分解為 2M－ 1個(gè) 兩點(diǎn) DFT， 兩點(diǎn) DFT就是一個(gè)基本蝶形運(yùn)算流圖 。
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1