-按時間抽取的fft算法(存儲版)
【正文】 ogFa N L N N??復(fù)數(shù)加法 ： 222( ) 2( ) l ogl og2FFm D FT N NNm FF T NN??比較 DFT 2023/3/28 18 2023/3/28 算法的計算復(fù)雜度 19 復(fù)乘次數(shù) N N 2 NN2log22023/3/28 例 .如果一臺通用計算機(jī)的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來計算 512點的 ，問直接計算需要多少時間，用 運(yùn)算需要多少時間。 將序列 x(n)按 n的奇偶分成兩組 ： 3 ? ? ? ?? ? ? ?12221x r x rx r x r???0 , 1 , ..., / 2 1rN??2023/3/28 4 ? 則 x(n)的 DFT: ? ? ? ? ? ? ? ?1 1 10 0 0N N Nnk nk nkN N Nn n nX k x n W x n W x n W? ? ?? ? ?? ? ?? ? ?n為 偶 數(shù)n為 奇 數(shù) ? ? ? ? ? ?/ 2 1 / 2 1 212002 2 1NN rkrkNNrrx r W x r W?? ???? ? ???? ? ? ? ? ? ? ?/ 2 1 / 2 12212 rk rkkN N Nx r W W x r W?? ? ? ? ?/ 2 1 / 2 11 / 2 2 / 2rk k rkN N Nx r W W x r W? ? ? ?12 kNX k W X k, 0 , 1 , ... / 2 1r k N??2023/3/28 5 ? 再利用周期性求 X(k)的后半部分 ? ? ? ?? ? ? ?121 1 2 2, / 222X k X k NNNX k X k X k X k? ? ? ?? ? ? ? ?? ? ? ?? ? ? ?是以 為周期的/22Nk N k kN N N NW W W W? ? ? ?又2023/3/28 6 1212( ) ( ) ( )( ) ( ) ( )2kNkNX k X k W X kNX k X k W X k? ???? ?? ? ???0 , 1 , ..., / 2 1kN??? 一個“蝶形運(yùn)算”包含 1次乘法， 2次加法 2023/3/28 7 2023/3/28 復(fù)數(shù)乘法 復(fù)數(shù)加法 一個 N / 2點 DFT (N / 2)2 N / 2 (N / 2 –1) 兩個 N / 2點 DFT N 2 / 2 N (N / 2 –1) 一個蝶形 1 2 N / 2個蝶形 N / 2 N 總計 8 分解后的運(yùn)算量： ?運(yùn)算量減少了近一半 22/ 2 / 2/2NNN??? ?2/ 2 1/2N N NN???2023/3/28 N / 2仍為偶數(shù)，進(jìn)一步分解 ： N / 2 N / 4 ?9 1314( 2 ) (
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1