第七講快速傅里葉變換fft-資料下載頁(yè)
2024-10-17 12:48本頁(yè)面
【導(dǎo)讀】迫切需要有新的算法。實(shí)際上，DFT運(yùn)算中包含有大量的重復(fù)運(yùn)算。這N個(gè)值也有一些對(duì)稱關(guān)系。總之，WN因子具有如。為短序列的DFT，N越小，運(yùn)算量能夠減少。速算法，其實(shí)質(zhì)還是DFT。應(yīng)用DFT進(jìn)行實(shí)時(shí)處理信號(hào)是不現(xiàn)實(shí)的。基于時(shí)間抽取的FFT。上式中X1和X2分別為x2和x2的N/2點(diǎn)DFT，上述運(yùn)算可用右下圖來(lái)表示，稱為蝶形運(yùn)算符號(hào)。DFT共需要計(jì)算兩個(gè)N/2點(diǎn)FFT和N/2個(gè)蝶形運(yùn)算。次乘法和N+2N/2=N2/2次復(fù)數(shù)加法運(yùn)算。直接計(jì)算時(shí)復(fù)數(shù)乘的次數(shù)為N2，加為N(N-1)次。即運(yùn)算效率提高了200多倍。易知N越大，優(yōu)越性。另外，在N＝2048時(shí)，直接運(yùn)算需要3個(gè)。小時(shí)，而采用FFT則只需不到一分鐘就能完成！根據(jù)運(yùn)算流圖可知，DIT-FFT的運(yùn)算很有規(guī)律。這種利用同一存貯單元存貯計(jì)算輸入、輸出。數(shù)據(jù)的方法稱為原位（址）計(jì)算。
【正文】 X(1) x(5) X(5) x(6) X(3) x(7) X(7) 1 1 1 1 W W W W N NN N0 1 2 3 1 1 1 1 W W W W N N N N 0 2 0 2 1 1 1 1 W W W W N N N N 0 0 0 0 每級(jí) (列 )都是由 N/2個(gè)蝶形運(yùn)算構(gòu)成 ,即 1 W N r ?????????????rNmmmmmmWjXkXjXjXkXkX)]()([)()()()(1111)(1 kX m?)(1 jXm?)()()( 11 jXkXkX mmm ?? ??rNmmm WjXkXjX )]()([)( 11 ?? ?? 一般公式為 2Lm =N/2m 例如 N=23 =8 ： (1)m=1 時(shí)的距離為 8/2=4； (2)m=2 時(shí)的距離為 8/4=2。 (3)m=3 時(shí)的距離為 8/8=1。 (1)進(jìn)行原位運(yùn)算； (2)運(yùn)算量相同 ,均為（ N/2) Log2N次復(fù)乘、 N Log2N次復(fù)加。 (1)DIT輸入為倒位序 ,輸出為自然順序； DIF正好與此相反。但 DIT也有輸入為自然順序 ,輸出為倒位序的情況。 DIT法的異同 rNmmm WjXkXjX )()()( 11 ?? ??rNmmm WjXkXkX )()()( 11 ?? ??)(1 kX m?)(1 jX m?rNW 1?(2)蝶形運(yùn)算不同 用矩陣表示 )(kXm)( jX mrNWrNW?)(1 kX m?)(1 jX m?= 1 1 用矩陣表示 )(kXm)( jX m rNW rNW?)(1 kX m?)(1 jX m?= 1 1 rNmmm WjXkXjX )]()([)( 11 ?? ??)()()( 11 jXkXkX mmm ?? ??)(1 kX m?)(1 jX m?rNW1?(3)兩種蝶形運(yùn)算的關(guān)系 －－ 互為轉(zhuǎn)置（矩陣）； 將流圖的所有支路方向都反向 ,交換輸入和輸出 ， 即可得到另一種蝶形 。 A. DIT rNWrNW?1 1 1 1 rNWrNW?FFT算法 ， 同樣可以適用于離散博里葉反變換(IDFT)運(yùn)算 ， 并簡(jiǎn)稱為 IFFT， 即快速博里葉反變換 ， 從 IDFT公式看： 而 DFT公式 比較以上兩式可知 ， 只要把 DFT運(yùn)算中的每一個(gè)系數(shù) 換成 ， 并且最后再乘以常數(shù) 1/N, 則 六、 IDFT的快速算法 IFFT 以上所有時(shí)間抽取或頻率抽取的 FFT算法都可以拿來(lái)運(yùn)算 IDFT。 此外，有一種直接采用 FFT程序計(jì)算 IFFT的方法。 對(duì) 取共軛，則： 兩邊同時(shí)再取共軛，有： 上述情況表明：在進(jìn)行 IDFT運(yùn)算的時(shí)候 ， 可以先將 X(k)取共軛 ， 直接調(diào)用 FFT子程序 ， 然后再取共軛并乘以 1/N就可得到序列 x(n)。 此方法雖然兩次取共軛 ， 但由于可以與 FFT共用一程序 ， 因而使用十分方便 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1