按時(shí)間抽取的fft算法講義-展示頁(yè)
2025-03-10 07:52本頁(yè)面
【正文】 N NW W W W? ? ? ?又2023/3/23 6 1212( ) ( ) ( )( ) ( ) ( )2kNkNX k X k W X kNX k X k W X k? ???? ?? ? ???0 , 1 , ..., / 2 1kN??? 一個(gè)“蝶形運(yùn)算”包含 1次乘法， 2次加法 2023/3/23 7 2023/3/23 復(fù)數(shù)乘法 復(fù)數(shù)加法 一個(gè) N / 2點(diǎn) DFT (N / 2)2 N / 2 (N / 2 –1) 兩個(gè) N / 2點(diǎn) DFT N 2 / 2 N (N / 2 –1) 一個(gè)蝶形 1 2 N / 2個(gè)蝶形 N / 2 N 總計(jì) 8 分解后的運(yùn)算量： ?運(yùn)算量減少了近一半 22/ 2 / 2/2NNN??? ?2/ 2 1/2N N NN???2023/3/23 N / 2仍為偶數(shù)，進(jìn)一步分解 ： N / 2 N / 4 ?9 1314( 2 ) ( )( 2 1 ) ( )x l x lx l x l?????? 0 , 1 , ..., / 4 1lN??1 3 / 2 41 3 / 2 4( ) ( ) ( )( ) ( ) ( )4kNkNX k X k W X kNX k X k W X k? ???? ? ? ?? 0 , 1 , ..., 14Nk2023/3/23 10 2/2kkNNWW ?統(tǒng)一系數(shù)：10 同理 ： 2 5 / 2 62 5 / 2 6( ) ( ) ( )( ) ( ) ( )4kNkNX k X k W X kNX k X k W X k? ???? ? ? ??? 0 , 1 , ..., 14Nk ??其中： 5 5 2( ) [ ( ) ] [ ( 2 ) ]X k D F T x l D F T x l??6 6 2( ) [ ( ) ] [ ( 2 1 ) ]k D F T x l D F T x l? ? ?0 , 1 , ..., / 4 1lN這樣逐級(jí)分解，直到 2點(diǎn) DFT 基 2時(shí)間抽取 FFT算法流圖 11 N=2 x[k]={x[0], x[1]} ]1[]0[]0[02 xWxX ?? ]1[]0[]1[ 12 xWxX ??]0[x]1[x]0[X102W ]1[X]1[]0[02 xWx ??2023/3/23 4點(diǎn)基 2時(shí)間抽取 FFT算法流圖 12 x[0] x[2] x[1] x[3] X1[0] X1[1] X2[0] X2[1] 2點(diǎn) DFT 2點(diǎn) DFT ?1 ?1 ?1 ?1 04W14W02W02W X [0] X [1] X [2] X [3] 1,0],[][][ 241 ??? mmXWmXmX m 1,0],[][]2[ 241 ???? mmXWmXm m2023/3/23 13 x [ 0 ]x [ 2 ]x [ 1 ]x [ 3 ]? 1? 1? 1?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1