按時(shí)間抽取的fft算法講義(編輯修改稿)
2025-03-22 07:52 本頁面
【文章內(nèi)容簡介】 X1[0] X1[1] X1[2] X1[3] X2[0] X2[1] X2[2] X2[3] X [0] X [1] X [2] X [3] X [4] X [5] X [6] X [7] ?1 ?1 ?1 ?1 08W1828W382 點(diǎn) D F T2 點(diǎn) D F Tx [ 0 ]x [ 4 ]x [ 2 ]x [ 6 ]? 114WX 1 1 [ 0 ]X1 1[ 1 ]X1 2[ 0 ]X1 2[ 1 ]042 點(diǎn) D F T2 點(diǎn) D F T? 1? 1X2 1[ 0 ]X2 1[ 1 ]X2 2[ 0 ]X2 2[ 1 ]x [ 1 ]x [ 5 ]x [ 3 ]x [ 7 ]14W 04? 1? 1? 1? 1x [ 0 ]x [ 4 ]x [ 2 ]2808W08W 08WX1 1[ 0 ]X1 1[ 1 ]X1 2[ 0 ]X1 2[ 1 ]? 1? 1280808 08WX2 1[ 0 ]X2 1[ 1 ]X2 2[ 0 ]X2 2[ 1 ]8點(diǎn)基 2時(shí)間抽取 FFT算法流圖 2023/3/23 基 2時(shí)間抽取 FFT算法 16 x [ 0 ]x [ 4 ]x [ 2 ]x [ 6 ]X [ 0 ]X [ 2 ]X [ 1 ]X [ 3 ]? 1? 1? 1? 108W 08W08Wx [ 1 ]x [ 5 ]x [ 3 ]x [ 7 ]X [ 0 ]X [ 2 ]X [ 1 ]X [ 3 ]? 1? 1? 1? 108W 08W08W18W08W 38W28W28W28W? 1? 1? 1? 1第一級(jí) 第二級(jí) 第三級(jí) 2023/3/23 二、按時(shí)間抽取的算法特點(diǎn) 17 當(dāng) N = 2L時(shí)，共有 L級(jí)蝶形，每級(jí) N / 2個(gè)蝶形，每個(gè)蝶形有 1次復(fù)數(shù)乘法 2次復(fù)數(shù)加法 。 2l og22FNNm L N??復(fù)數(shù)乘法 ： 2l ogFa N L N N??復(fù)數(shù)加法 ： 222( ) 2( ) l ogl og2FFm D FT N NNm FF T NN??比較 DFT 2023/3/23 18 2023/3/23 算法的計(jì)算復(fù)雜度 19 復(fù)乘次數(shù) N N 2 NN2log22023/3/23 例 .如果一臺(tái)通用計(jì)算機(jī)的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來計(jì)算 512點(diǎn)的 ，問直接計(jì)算需要多少時(shí)間，用 運(yùn)算需要多少時(shí)間。 5 s? s ? ?D F T x n????FFT解： (1)直接利用 計(jì)算： 復(fù)乘次數(shù)為 ，復(fù)加次數(shù)為 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1