第四章快速傅里葉變換

第四章快速傅里葉變換1.引言2.直接計(jì)算DFT的問題及改進(jìn)的途徑3.按時(shí)間抽選（DIT）的基－2FFT算法4.按頻率抽選（DIF）的基－2FFT算法5.離散傅里葉反變換IDFT的快速計(jì)算方法1.引言FFT不是一種新算法,只是DFT的一種快速算法。

Cooley和Tukey在1965年發(fā)表的“機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法”

桑德和圖基的快速算法的出現(xiàn)。

2.直接計(jì)算DFT的問題及改進(jìn)的途徑DFT和IDFT的變換公式

二者的差別就在于WN的指數(shù)符號(hào)不同，以及相差一個(gè)常數(shù)乘因子1/N。每計(jì)算一個(gè)X(k)值，需要N次復(fù)數(shù)乘法，以及（N-1）次復(fù)數(shù)加法，而X(k)一共有N個(gè)值點(diǎn)，因此完成整個(gè)DFT運(yùn)算總共需要N2次復(fù)數(shù)乘法，N（N-1）次復(fù)數(shù)加法。(4.1)

(4.2)復(fù)數(shù)運(yùn)算實(shí)際上是由實(shí)數(shù)運(yùn)算來完成的，因此(4.1)式可寫成可以看出，一次復(fù)數(shù)乘法需要4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法，一次復(fù)數(shù)加法需要2次實(shí)數(shù)加法。因此，每計(jì)算一個(gè)X(k)值，需要4N次實(shí)數(shù)乘法，以及2N＋2（N-1）＝2（2N－1）次實(shí)數(shù)加法，整個(gè)DFT運(yùn)算總共需要4N2次實(shí)數(shù)乘法，2N（2N-1）次實(shí)數(shù)加法。

(4.3)存在問題：直接計(jì)算DFT，乘法次數(shù)和加法次數(shù)都是和N2成正比。當(dāng)N很大時(shí)，運(yùn)算量很大，例如，N=8時(shí)，需要64次復(fù)乘，N＝1024時(shí)，需要1048576次復(fù)乘。減少DFT運(yùn)算工作量的途徑：利用WNnk的固有特性。（1）WNnk的對(duì)稱性：（2）WNnk的周期性：（3）WNnk的可約性：可以得出實(shí)際辦法：（1）用上述特性對(duì)項(xiàng)合并（2）將長(zhǎng)序列的DFT分解為短序列的DFT，減小N值。對(duì)稱性與周期性四點(diǎn)的DFT進(jìn)行化簡(jiǎn)，得將該矩陣的第二列和第三列交換，得由此得出快速傅里葉變換正是基于這樣的思想發(fā)展進(jìn)來的，主要分為兩大類：DIT：按時(shí)間抽選DIF：按頻率抽選3.按時(shí)間抽選的基－2FFT算法

3.1算法原理先設(shè)序列點(diǎn)數(shù)為，按n的奇偶進(jìn)行分解將DFT化為利用系數(shù)的可約性，即得

(4.5)(4.6)(4.7)應(yīng)用系數(shù)的周期性,可得

再考慮性質(zhì)把(4.8),(4.9),(4.10)代入(4.5)式，將X(k)表達(dá)成前后兩部分，前部分為

后部分為

(4.8)(4.9)(4.10)(4.11)(4.12)這樣，4.11、12式只要0-(N/2-1)區(qū)間的所有X1(k)和X2(k)的值，即可求0到(N-1)區(qū)間所有X(k)值。4.11和4.12式用蝶形圖表示。N＝8的情況如圖所示:

分析：每個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法及兩次復(fù)數(shù)加（減）法。通過分解后運(yùn)算工作量差不多減少到一半。進(jìn)一步把N/2點(diǎn)子序列再按奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列且其中圖4－3，給出N＝8時(shí)，在分解為兩個(gè)N/4點(diǎn)DFT，由兩個(gè)N/4點(diǎn)DFT組合成N/2點(diǎn)DFT的流圖。X2(k)也可進(jìn)行同樣分解：其中一個(gè)N＝8點(diǎn)DFT就可分解為四個(gè)N/4＝2點(diǎn)DFT如圖序列按奇偶分解標(biāo)號(hào)變化討論（N＝8）1、第一次分解：兩個(gè)N/2點(diǎn)序列：2、第二次分解，每個(gè)N/2點(diǎn)子序列按其奇偶分解為兩個(gè)N/4點(diǎn)子序列3、最后是2點(diǎn)的DFT

對(duì)于例子N＝8，就是4個(gè)N/4＝2點(diǎn)的DFT。如：其中這種方法的每一步分解都是按輸入序列在時(shí)間上的次序是屬于偶數(shù)還是屬于奇數(shù)來分解為兩個(gè)更短的子序列，所以稱為“按時(shí)間抽選法”。3.2運(yùn)算量分析（1）直接DFT復(fù)數(shù)算法次數(shù)是N2

（2）FFT復(fù)數(shù)乘法次數(shù)是（N/2）*L

當(dāng)N=2L時(shí)，一共有L級(jí)蝶形，每級(jí)有N/2個(gè)蝶形運(yùn)算組成，一個(gè)蝶形運(yùn)算有1次復(fù)乘，2次復(fù)加運(yùn)算。DFT和FFT算法的計(jì)算量之比為結(jié)論：FFT比DFT更優(yōu)越，當(dāng)N越大時(shí)，優(yōu)點(diǎn)更明顯。3.3按時(shí)間抽選的FFT算法特點(diǎn)1.原位運(yùn)算每個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算：

4.21的蝶形運(yùn)算如圖4－7所示。蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸入值所在的存儲(chǔ)器中，中間不需要其他的存儲(chǔ)器。每列的N/2個(gè)蝶形運(yùn)算完成后，再開始下一列的蝶形運(yùn)算，這樣存儲(chǔ)數(shù)據(jù)就只要N個(gè)存儲(chǔ)單元。下一級(jí)的蝶形運(yùn)算仍采取這樣的原位運(yùn)算，只不過進(jìn)入蝶形的組合關(guān)系有所不同。2.倒位序規(guī)律3.倒位序的實(shí)現(xiàn)：通過變址運(yùn)算完成4.存儲(chǔ)單元輸入序列N個(gè)單元系數(shù)N/2個(gè)單元3.4按時(shí)間抽選的FFT算法的其它形式流程圖對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連的支路和傳輸系數(shù)不變，則不論節(jié)點(diǎn)怎么排列所得的流圖總是等效的，只是數(shù)據(jù)的提取和存放的次序不同而已。因此就可以有按之間抽取的FFT算法的若干形式。4.按頻率抽選（DIF）的基－2FFT算法

（桑德－圖基算法）DIF算法是將輸出序列X（K）按其順序的奇偶分解為越來越短的序列。仍設(shè)序列的點(diǎn)數(shù)為N＝2L,L為整數(shù)。先將輸入序列按n的順序分為前后兩半。當(dāng)k為偶數(shù)時(shí)，(-1)k=1;當(dāng)k為偶數(shù)時(shí)，(-1)k=-1。因此按k的奇偶可將X(k)分為兩部分。令則令則可以用蝶形運(yùn)算來表示N＝8時(shí)，按k分解結(jié)果如圖5.離散傅里葉反變換IDFT的快速計(jì)算方法DFT和IDFT的變換公式比較可知，只要把DFT運(yùn)算中的每一個(gè)系數(shù)WNnk變成WN-nk

，最后再乘常數(shù)1/N，則以上所有按時(shí)間抽選或按頻率抽選的FFT都可以拿來運(yùn)算IDFT。上面的方法比較簡(jiǎn)單，但是要稍微改動(dòng)FFT的程序和參數(shù)才能實(shí)現(xiàn)，下面的方法不改變FFT的程序計(jì)算IFFT：對(duì)DFT的反變換公式取共軛只要先將X(k)取共軛，然后直接利用FFT子程序，最后將結(jié)果取共軛，并乘以1/N，就可以得到x(n)的值。例：假設(shè)一次復(fù)乘的時(shí)間為1μs，而且假定一個(gè)DFT總共需要的時(shí)間由計(jì)算所有乘法所需的時(shí)間確定。1）直接計(jì)算一個(gè)1024點(diǎn)的DFT需要多少時(shí)間？2）計(jì)算基2－FFT需要多少時(shí)間？解：1）t＝N2·10－6s≈1.05s2)基2－FFT復(fù)乘的次數(shù)為(N/2)log2N=5120t＝5120·10－6s≈5.12ms例：對(duì)一個(gè)連續(xù)時(shí)間信號(hào)xa(t)進(jìn)行采樣，在1s內(nèi)采集了4096個(gè)數(shù)據(jù)，1）若采樣后沒有產(chǎn)生頻譜混疊，則信號(hào)xa(t)的最高頻率時(shí)多少？2）若計(jì)算采樣信號(hào)的4096點(diǎn)的DFT，頻譜之間的頻率間隔是多少Hz？解：1）因?yàn)樵?s內(nèi)采集了4096個(gè)數(shù)據(jù)，所以fs