1本章主要內(nèi)容直接計(jì)算DFT的問(wèn)題及改進(jìn)的途徑按時(shí)間抽取的基2-FFT算法

按頻率抽取的基2-FFT算法

快速傅里葉逆變換(IFFT)算法

24.1引言

DFT在實(shí)際應(yīng)用中很重要:可以計(jì)算信號(hào)的頻譜、功率譜和線性卷積等。直接按DFT變換進(jìn)行計(jì)算，當(dāng)序列長(zhǎng)度N很大時(shí)，計(jì)算量非常大，所需時(shí)間會(huì)很長(zhǎng)。FFT并不是一種與DFT不同的變換，而是DFT的一種快速計(jì)算的算法。

34.2.1直接計(jì)算DFT的問(wèn)題及改進(jìn)的途徑

DFT的運(yùn)算量

設(shè)復(fù)序列x(n)長(zhǎng)度為N點(diǎn)，其DFT為k=0，，…，N-1（1）計(jì)算一個(gè)X(k)值的運(yùn)算量復(fù)數(shù)乘法次數(shù)：N復(fù)數(shù)加法次數(shù)：N－14DFT的運(yùn)算量（2）計(jì)算全部N個(gè)X(k)值的運(yùn)算量復(fù)數(shù)乘法次數(shù)：N2復(fù)數(shù)加法次數(shù)：N(N－1)（3）對(duì)應(yīng)的實(shí)數(shù)運(yùn)算量5DFT的運(yùn)算量一次復(fù)數(shù)乘法：4次實(shí)數(shù)乘法2次實(shí)數(shù)加法＋一個(gè)X(k)

：4N次實(shí)數(shù)乘法＋2N+2(N-1)=2(2N-1)次實(shí)數(shù)加法所以整個(gè)N點(diǎn)DFT運(yùn)算共需要：N×2(2N-1)=2N(2N-1)實(shí)數(shù)乘法次數(shù)：4N2實(shí)數(shù)加法次數(shù)：6DFT運(yùn)算量的結(jié)論N點(diǎn)DFT的復(fù)數(shù)乘法次數(shù)舉例NN2NN22464404941612816384864256655361625651226214432102810241048576結(jié)論：當(dāng)N很大時(shí)，其運(yùn)算量很大，對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來(lái)說(shuō)，要求計(jì)算速度快，因此需要改進(jìn)DFT的計(jì)算方法，以大大減少運(yùn)算次數(shù)。7

減少運(yùn)算工作量的途徑

主要原理是利用系數(shù)的以下特性對(duì)DFT進(jìn)行分解：（1）對(duì)稱性（2）周期性（3）可約性另外，84.2.2按時(shí)間抽取的基2-FFT算法

算法原理按時(shí)間抽取基-2FFT算法與直接計(jì)算DFT運(yùn)算量的比較按時(shí)間抽取的FFT算法的特點(diǎn)按時(shí)間抽取FFT算法的其它形式流程圖9算法原理

設(shè)N＝2L，將x(n)按n的奇偶分為兩組：

r=0，1，…，則10算法原理

式中，X1(k)和X2(k)分別是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范圍是：0，1，…，N/2－1。11算法原理

因此，只能計(jì)算出X(k)的前一半值。后一半X(k)值，N/2，N/2＋1，…，N

？利用可得到同理可得12算法原理

考慮到因此可得后半部分X(k)及前半部分X(k)k=0，1，…，N/2－1k=0，1，…，N/2－113蝶形運(yùn)算蝶形運(yùn)算式蝶形運(yùn)算信號(hào)流圖符號(hào)

因此，只要求出2個(gè)N/2點(diǎn)的DFT，即X1(k)和X2(k)，再經(jīng)過(guò)蝶形運(yùn)算就可求出全部X(k)的值，運(yùn)算量大大減少。蝶形運(yùn)算符號(hào)14圖4.2.28點(diǎn)DFT一次時(shí)域抽取分解運(yùn)算流圖以N=8為例，分解為2個(gè)4點(diǎn)的DFT，然后做8/2=4次蝶形運(yùn)算即可求出所有8點(diǎn)X(k)的值。以8點(diǎn)為例第一次按奇偶分解15蝶形運(yùn)算量比較復(fù)數(shù)乘法次數(shù)：N2復(fù)數(shù)加法次數(shù)：N(N－1)復(fù)數(shù)乘法次數(shù)：2*(N/2)2+N/2=N2/2+N/2復(fù)數(shù)加法次數(shù)：2*(N/2)(N/2－1)+2*N/2=N2/2N點(diǎn)DFT的運(yùn)算量

分解一次后所需的運(yùn)算量＝2個(gè)N/2的DFT＋N/2蝶形：因此通過(guò)一次分解后，運(yùn)算工作量減少了差不多一半。

16進(jìn)一步按奇偶分解

由于N＝2L，因而N/2仍是偶數(shù)，可以進(jìn)一步把每個(gè)N/2點(diǎn)子序列再按其奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列。以N/2點(diǎn)序列x1(r)為例則有k=0,1,…,

17進(jìn)一步按奇偶分解且k=0,1,…,由此可見(jiàn)，一個(gè)N/2點(diǎn)DFT可分解成兩個(gè)N/4點(diǎn)DFT。同理，也可對(duì)x2(n)進(jìn)行同樣的分解，求出X2(k)。18圖4.2.38點(diǎn)DFT二次時(shí)域抽取分解運(yùn)算流圖19算法原理

對(duì)此例N=8，最后剩下的是4個(gè)N/4=2點(diǎn)的DFT，2點(diǎn)DFT也可以由蝶形運(yùn)算來(lái)完成。以X3(k)為例。k=0,1即這說(shuō)明，N=2M的DFT可全部由蝶形運(yùn)算來(lái)完成。/4/420圖4.2.48點(diǎn)DIT-FFT運(yùn)算流圖以8點(diǎn)為例第三次按奇偶分解214.2.3DTF-FFT算法與直接計(jì)算DFT運(yùn)算量的比較

由按時(shí)間抽取法FFT的信號(hào)流圖可知，當(dāng)N=2L時(shí)，共有

級(jí)蝶形運(yùn)算；每級(jí)都由

個(gè)蝶形運(yùn)算組成，而每個(gè)蝶形有

次復(fù)乘、

次復(fù)加，因此每級(jí)運(yùn)算都需

次復(fù)乘和

次復(fù)加。LN/2

N/2

12N22DTF-FFT算法與直接計(jì)算DFT運(yùn)算量的比較

這樣

級(jí)運(yùn)算總共需要：L復(fù)數(shù)乘法：

復(fù)數(shù)加法：

直接DFT算法運(yùn)算量復(fù)數(shù)乘法：

復(fù)數(shù)加法：

N2N(N－1)直接計(jì)算DFT與FFT算法的計(jì)算量之比為M23DIT-FFT算法與直接DFT算法運(yùn)算量的比較NN2計(jì)算量之比MNN2計(jì)算量之比M2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.4244.2.5按頻率抽取的基2-FFT算法

算法原理再把輸出X(k)按k的奇偶分組先把輸入按n的順序分成前后兩半設(shè)序列長(zhǎng)度為N=2L，L為整數(shù)前半子序列x(n)后半子序列

0≤n≤0≤n≤25算法原理由DFT定義得k=0，1，…，N26算法原理由于所以則k=0，1，…，N27算法原理然后按k的奇偶可將X(k)分為兩部分r=0，1，…，則式可轉(zhuǎn)化為28算法原理令n=0，1，…，代入r=0，1，…，可得為2個(gè)N/2點(diǎn)的DFT，合起來(lái)正好是N點(diǎn)X(k)的值。29蝶形運(yùn)算將稱為蝶形運(yùn)算與時(shí)間抽選基2FFT算法中的蝶形運(yùn)算符號(hào)略有不同。30例按頻率抽取(N=8)

例按頻率抽取，將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT的組合(N=8)31例按頻率抽取(N=8)

與時(shí)間抽取法的推導(dǎo)過(guò)程一樣，由于N=2L，N/2仍然是一個(gè)偶數(shù)，因而可以將每個(gè)N/2點(diǎn)DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點(diǎn)DFT進(jìn)一步分解為兩個(gè)N/4點(diǎn)DFT。N=832例頻率抽取IFFT流圖(N=8)

334.2.6IDFT的高效算法4.3進(jìn)一步減少運(yùn)算量的措施-實(shí)序列的FFT算法在實(shí)際工作中，數(shù)據(jù)x(n)常常是實(shí)數(shù)序列。如果直接按FFT運(yùn)算流圖計(jì)算，就是把x(n)看成一個(gè)虛部為零的復(fù)序列進(jìn)行計(jì)算，這就增加了存儲(chǔ)量和運(yùn)算時(shí)間。

處理該問(wèn)題的