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