快速傅里葉變換FFT

1、第四章快速傅里葉變換FFT所謂的快速算法，就是根據(jù)原始變換定義算法的運(yùn)算規(guī)律及其中的某些算子的特殊性質(zhì)，找出減少乘法和加法運(yùn)算次數(shù)的有效途徑，實(shí)現(xiàn)原始變換的各種高效算法。一種好的快速算法可使變換速度提高幾個(gè)數(shù)量級(jí)。由于快速算法很多，而且還在不斷研究和發(fā)展。較成熟的算法都有現(xiàn)成的程序。所以，通過(guò)教材中介紹的四種快速算法，主要學(xué)習(xí)研究快速算法的基本思想和減少運(yùn)算量的途徑，熟悉各種快速算法的特點(diǎn)、運(yùn)算效率和適用情況。為今后研究新的快速算法和合理選用快速算法打好基礎(chǔ)。4.1 學(xué) 習(xí) 要 點(diǎn) 直接計(jì)算N點(diǎn)DFT的運(yùn)算量對(duì)于 復(fù)數(shù)乘法次數(shù)： 復(fù)數(shù)加法次數(shù)： 當(dāng)時(shí)，復(fù)數(shù)乘法和加法次數(shù)都接近為次，隨著增大非線

2、性增大。 減少運(yùn)算量的基本途徑DFT定義式中只有兩種運(yùn)算：與的乘法相加。所以，的特性對(duì)乘法運(yùn)算量必有影響。（1）根據(jù)的對(duì)稱性、周期性和特殊值減少乘法運(yùn)算次數(shù)。對(duì)稱性：，周期性：。的特殊值(無(wú)關(guān)緊要旋轉(zhuǎn)因子)：。對(duì)這些因子不能進(jìn)行乘法運(yùn)算。（2）將較大數(shù)點(diǎn)DFT分解為若干個(gè)小數(shù)點(diǎn)DFT的組合，減少運(yùn)算量。這正是FFT能大量節(jié)省運(yùn)算量的關(guān)鍵。 四種快速算法的基本思想及特點(diǎn)根據(jù)上述減少運(yùn)算量的途徑，巧妙地在時(shí)域或頻域進(jìn)行不同的抽取分解與組合，得到不同的快速算法。下面簡(jiǎn)要?dú)w納四種快速算法的基本思想和特點(diǎn)。1. 基2 DFT-FFT算法（1）算法思想：時(shí)域級(jí)奇偶抽取，并利用，將點(diǎn)DFT變成級(jí)蝶形運(yùn)算。（

3、2）運(yùn)算量：復(fù)數(shù)乘法次數(shù)： 復(fù)數(shù)加法次數(shù)： （3）特點(diǎn)：運(yùn)算流圖結(jié)構(gòu)規(guī)則，可原位計(jì)算，程序簡(jiǎn)短，應(yīng)用廣泛。2. 基2 DIF-FFT算法（1）算法思想：頻域?qū)M(jìn)行級(jí)奇偶抽取，并利用，將點(diǎn)DFT變成級(jí)DIF-FFT蝶形運(yùn)算。（2）運(yùn)算量及特點(diǎn)與基2 DIF-FFT相同3. 分裂基快速算法（1）算法思想：基2 FFT算法簡(jiǎn)單，基4FFT算法效率較高。分裂基是將基2分解和基4分解糅合在一起形成的高效新算法。具體是對(duì)每次的頻域奇偶抽取的偶數(shù)輸出使用基2算法（按二進(jìn)制抽?。鏀?shù)輸出使用基4算法（按四進(jìn)制抽?。?。（2）運(yùn)算量：復(fù)數(shù)乘法次數(shù)： 復(fù)數(shù)加法次數(shù)： （3）特點(diǎn)：在的快速算法中，分裂基算法的乘法

4、次數(shù)最少，接近理論最小值。比基2 FFT減少33%，比基4減少11%。運(yùn)算流圖結(jié)構(gòu)規(guī)則，可同址計(jì)算，程序簡(jiǎn)短，便于DSP實(shí)現(xiàn)。4.2 教材第四章習(xí)題解答1. 如果通用計(jì)算機(jī)的速度為平均每次復(fù)數(shù)乘需要5，每次復(fù)數(shù)加需要1，用來(lái)計(jì)算N=1024點(diǎn)DFT，問(wèn)直接計(jì)算需要多少時(shí)間。用FFT計(jì)算呢？照這樣計(jì)算，用FFT進(jìn)行快速卷積對(duì)信號(hào)進(jìn)行處理時(shí)，估算可實(shí)現(xiàn)時(shí)處理的信號(hào)最高頻率。解：當(dāng)N=1024=210時(shí)，直接計(jì)算DFT的復(fù)數(shù)運(yùn)算次數(shù)為N2=10242次復(fù)數(shù)加法計(jì)算次數(shù)為次直接計(jì)算所用計(jì)算時(shí)間TD為用FFT計(jì)算1024點(diǎn)DFT所需計(jì)算時(shí)間為快速卷積時(shí)，要計(jì)算一次N點(diǎn)FFT（考慮到已計(jì)算好存入內(nèi)存），一

5、次N點(diǎn)IFFT和N次頻率復(fù)數(shù)乘法。所以，計(jì)算1024點(diǎn)快速卷積的計(jì)算時(shí)間約為所以，每秒鐘處理的采樣點(diǎn)數(shù)（即采樣頻率）/秒。由采樣定理知，可實(shí)時(shí)處理的信號(hào)最高頻率為應(yīng)當(dāng)說(shuō)明，實(shí)際實(shí)現(xiàn)時(shí)，還要你小一些。這是由于采樣頻率高于奈奎斯特速率，而且在采用重疊相加法時(shí)，重疊部分還要計(jì)算兩次。重疊部分長(zhǎng)度與長(zhǎng)度有關(guān)，而且還有存取數(shù)據(jù)指令周期等。3. 已知和是兩個(gè)N點(diǎn)實(shí)序列和的DFT，若要從和求和，為提高運(yùn)算效率，試設(shè)計(jì)用一次N點(diǎn)IFFT來(lái)完成。解：因?yàn)楹途鶠閷?shí)序列，所以，和為共軛對(duì)稱序列，j為共軛反對(duì)稱序列?？闪詈蚸分別作為復(fù)序列的共軛對(duì)稱分量和共軛反對(duì)稱分量，即計(jì)算一次N點(diǎn)IFFT得到由DFT的共軛對(duì)稱性可

6、知，故4. 設(shè)是長(zhǎng)度為2N的有限長(zhǎng)實(shí)序列，為的確N點(diǎn)DFT。（1）試設(shè)計(jì)用一次N點(diǎn)FFT完成計(jì)算的高效算法。（2）若已知，試設(shè)計(jì)用一次N點(diǎn)IFFT實(shí)現(xiàn)求的2N點(diǎn)IDFT運(yùn)算。解：（1）在時(shí)域分別抽取偶書(shū)點(diǎn)和奇數(shù)點(diǎn)得到兩個(gè)N點(diǎn)實(shí)序列和：根據(jù)DIT-FFT的思想，只要求得和的N點(diǎn)DFT,再經(jīng)過(guò)簡(jiǎn)單的一級(jí)蝶形運(yùn)算就得到的2N點(diǎn)DFT。因?yàn)楹途鶠閷?shí)序列，所以根據(jù)DFT的共軛對(duì)稱性，可用一次N點(diǎn)FFT求得和。具體方法如下：令 則 2N點(diǎn)可由和得到這樣，通過(guò)一次N點(diǎn)IFFT計(jì)算就完成了計(jì)算2N點(diǎn)DFT。當(dāng)然還要進(jìn)行運(yùn)算量相對(duì)很少的，由求，和的運(yùn)算。（2）和（1）相同，設(shè)則應(yīng)滿足關(guān)系式由上式可解出由以上分析

7、可得到運(yùn)算過(guò)程如下： 由計(jì)算出和 由和構(gòu)成N點(diǎn)頻域序列其中，進(jìn)行N點(diǎn)IFFT得到由DFT的共軛對(duì)稱性知 由和合成在便成實(shí)現(xiàn)時(shí)，只要將存放和的兩個(gè)數(shù)組的元素分別依次存放的數(shù)組的偶數(shù)和奇數(shù)數(shù)組元素中即可。5. 按照下面的IDFT算法：編寫(xiě)IFFT程序，其中的FFT部分不用寫(xiě)出清單，可調(diào)用FFT子程序。解：通過(guò)調(diào)用FFT子程序?qū)崿F(xiàn)題中所給IFFT算法程序框圖如題5圖解所示。數(shù)組XN用于存放輸入X（k）、中間結(jié)果及最終結(jié)果x(n)。用matlab語(yǔ)言編寫(xiě)的IFFT程序清單如下：題4.6計(jì)算IFFT的程序Xk:被變換數(shù)據(jù)X（k）XN:IFFTX(k)結(jié)果x(n)%N:x(n),X(k)長(zhǎng)度XkX(0) X(1) X(N-1);n=size(Xk);N=n(2); %取得X（k）的長(zhǎng)度Xkconj(Xk); %取復(fù)共軛XN=fft(X