按時(shí)間抽取的fft算法(參考版)
2025-05-02 07:25本頁(yè)面
【正文】 ? ?24 ～ 0NW 142?NNW02NW12 ?NNW～ 三、按時(shí)間抽取 FFT算法的其它形式 25 2022/5/27 26 2022/5/27 27 2022/5/27 28 2022/5/27 。 DFT2N ? ?1NN ?復(fù)乘所需時(shí)間 6 2 6 21 5 1 0 5 1 0 5 1 2 1 . 3 1 0 7 2T N s??? ? ? ? ? ? ?復(fù)加所需時(shí)間 ? ?? ?6260 .5 1 0 10 .5 1 0 5 1 2 5 1 2 1 0 .1 3 0 8 1 6T N Ns??? ? ? ? ?? ? ? ? ? ?所以直接利用 DFT 計(jì)算所需時(shí)間： 12 1 . 4 4 1 5 3 6T T T s? ? ?2022/5/27 20 復(fù)乘所需時(shí)間 612625 1 0 l o g25125 1 0 l o g 5 1 2 0 .0 1 1 5 22NTNs??? ? ?? ? ? ?622620 .5 1 0 l o g0 .5 1 0 5 1 2 l o g 5 1 2 0 .0 0 2 3 0 4T N Ns??? ? ?? ? ? ?復(fù)加所需時(shí)間 所以用 FFT 計(jì)算所需時(shí)間 12 0 . 0 1 3 8 2 4T T T s? ? ?(2) 利用 計(jì)算： 復(fù)乘次數(shù)為 ，復(fù)加次數(shù)為 。 2l o g22FNNm L N??復(fù)數(shù)乘法 ： 2l o gFa N L N N??復(fù)數(shù)加法 ： 222( ) 2( ) l ogl og2FFm D F T N NNm F F T NN??比較 DFT 2022/5/27 18 2022/5/27 算法的計(jì)算復(fù)雜度 19 復(fù)乘次數(shù) N N 2 NN 2log22022/5/27 例 .如果一臺(tái)通用計(jì)算機(jī)的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來(lái)計(jì)算 512點(diǎn)的 ，問(wèn)直接計(jì)算需要多少時(shí)間，用 運(yùn)算需要多少時(shí)間。 若不滿足，則補(bǔ)零 ? N為 2的整數(shù)冪的 FFT算法稱(chēng)基 2FFT算法。FFT算法分類(lèi) :
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1