-按時(shí)間抽取的fft算法(已修改)
2025-03-17 01:29 本頁面
【正文】 FFT算法分類 : 時(shí)間抽選法 DIT: DecimationInTime 頻率抽選法 DIF: DecimationInFrequency 167。 72 按 時(shí)間抽取的 FFT算法 ? 一、按時(shí)間抽取的算法原理 ? 二、按時(shí)間抽取的算法特點(diǎn) ? 三、按時(shí)間抽取 FFT算法的其他形式 2 2023/3/28 一、按時(shí)間抽取的算法原理 ? 設(shè)序列點(diǎn)數(shù) N = 2L， L 為整數(shù)。 若不滿足，則補(bǔ)零 ? N為 2的整數(shù)冪的 FFT算法稱基 2FFT算法。 將序列 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??? 一個(gè)“蝶形運(yùn)算”包含 1次乘法， 2次加法 2023/3/28 7 2023/3/28 復(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/28 N / 2仍為偶數(shù)，進(jìn)一步分解 ： N / 2 N / 4 ?9 1314( 2 ) ( )( 2 1 ) ( )x l x lx l x
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1