重要復(fù)試各科課件-數(shù)字信號(hào)處理第3章

1第3章

離散傅里葉變換

（DiscreteFourierTransform）2主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用

3主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用

43.1.1傅里葉變換回顧

《信號(hào)與線性系統(tǒng)》：連續(xù)時(shí)間信號(hào)的傅里葉變換（CTFT）和傅里葉級(jí)數(shù)（FS）；本教材第二章：離散時(shí)間信號(hào)的傅里葉變換（DTFT）。3.1

引言（Introduction）50t0一連續(xù)時(shí)間信號(hào)的傅里葉變換1.定義：6時(shí)域信號(hào)頻域信號(hào)連續(xù)的非周期的非周期的連續(xù)的對(duì)稱性:

時(shí)域連續(xù)，則頻域非周期。反之亦然。2.特點(diǎn)： 連續(xù)時(shí)間、連續(xù)頻率70t------0二連續(xù)時(shí)間信號(hào)的傅里葉級(jí)數(shù)1.定義：其中：為基波角頻率，為基頻，

是次諧波（離散非周期性頻譜）周期信號(hào)8時(shí)域信號(hào)頻域信號(hào)連續(xù)的周期的非周期的離散的時(shí)域：連續(xù)、周期為T0,頻域：離散、非周期，譜線間隔為2π/T02.特點(diǎn)：9x(nT)T-T0T2Tt0------三離散時(shí)間信號(hào)的傅里葉變換1.定義：10時(shí)域信號(hào)頻域信號(hào)離散的非周期的周期的連續(xù)的2.特點(diǎn)：11時(shí)頻離散？NN周期？NN時(shí)頻離散？NY周期？YN時(shí)頻離散？YN周期？NYCTFTDTFTCTFS幾種傅里葉變換特點(diǎn)小結(jié)特點(diǎn)2：總有一個(gè)域不是離散的，計(jì)算機(jī)不能直接計(jì)算特點(diǎn)1：對(duì)稱性目標(biāo)：時(shí)域離散的，頻域也離散DFT123.1.2第四種傅里葉變換DFT13時(shí)頻離散？YY周期？YYDFT3.1.2第四種傅里葉變換14時(shí)頻離散？NY周期？YN時(shí)頻離散？YN周期？NYDTFTCTFS如何引入DFT定義時(shí)頻離散？YY周期？YYDFT一.周期序列DFS的引入？已有一個(gè)域?yàn)殡x散15主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用

163.2離散傅立葉級(jí)數(shù)及其性質(zhì)

（DiscreteFourierSeries）考慮周期序列：3.2.1離散傅里葉級(jí)數(shù)（DFS）

其中：k－任意整數(shù)，N－周期；問題：

周期序列的FT是不收斂，這是因?yàn)樾蛄性趎=-到+整個(gè)范圍內(nèi)周而復(fù)始永不衰減17一.周期序列DFS的引入對(duì)上式進(jìn)行抽樣，得：連續(xù)的周期信號(hào)的傅氏級(jí)數(shù)：

因是離散的，所以應(yīng)是周期的。而且，其周期為，因此應(yīng)是N點(diǎn)的周期序列。0t------018x(nT)=x(n)t0Ts2Ts12Nn00123kNTs19由于其中：——基波——K次諧波即周期也為N說明：這些諧波成分中只有N個(gè)是獨(dú)立的，這是與連續(xù)傅氏級(jí)數(shù)的不同之處20在k=0,1,...,N-1求和與在k=N,...,2N-1求和所得的結(jié)果是一致的。所以，求和可以在一個(gè)周期內(nèi)進(jìn)行，即IDFS：21上式兩邊并從n=0～N-1求和得：二.的求取式中：交換右邊求和次序IDFS：22用k置換r得：②注：①23設(shè)（旋轉(zhuǎn)因子），可得周期序列的傅里葉級(jí)數(shù)變對(duì)：正變換：反變換：三離散傅氏級(jí)數(shù)的習(xí)慣表示法24注：

①，都是離散和周期性的，且周期相同，均為N；

②DFS只取k次諧波分量中N個(gè)諧波分量；③DFS、IDFS具有唯一性。25注：

①n為離散時(shí)間變量，理解為nT；k是離散頻率變量，理解為；

上式為：頻域<->時(shí)域之間的變換。②從上兩式可知：離散周期序列既可用表示，也可用表示。③周期性時(shí)間信號(hào)的頻譜是離散的（FS）離散時(shí)間信號(hào)的頻譜是周期性的（DTFT）周期、離散時(shí)間信號(hào)的頻譜為離散周期性（DFS）263.2.2離散傅里葉級(jí)數(shù)的性質(zhì)

（ThePropertiesoftheDiscreteFourierSeries）1.線性：設(shè)周期序列和的周期均為N，且：，；如果：（a，b均為常數(shù)）則有：272.周期序列的移位：設(shè)，則：，，（m，l為常數(shù)）備注：上面性質(zhì)的推導(dǎo)請(qǐng)同學(xué)參考教材自己推導(dǎo)。由于 與 對(duì)稱的特點(diǎn)，同樣可證明283.周期卷積（PeriodicConvolution）：設(shè)和都為周期序列，周期都為N，且：，，則：（注意上下限）

這是一個(gè)卷積公式，但與前面討論的線性卷積的差別在于，這里的卷積過程只限于一個(gè)周期內(nèi)（即m=0~N-1），稱為周期卷積。29證明：DFS代入因?yàn)?0結(jié)論：周期卷積的操作步驟與非周期序列的線性卷積相同，不同的是周期卷積僅在一個(gè)周期內(nèi)求和；周期卷積中要求對(duì)m是周期性的，周期要相同,為N；卷積結(jié)果也是周期的，周期為N；周期卷積滿足交換律。例：、，周期為N=7,寬度分別為4和3，求周期卷積。3132（1）畫出和的圖形；周期卷積過程（2）將翻摺,得到

可計(jì)算出：33m計(jì)算區(qū)mm0123（1）（2）34（3）將右移一位、得到可計(jì)算出：m35計(jì)算區(qū)mm0123m36（4）將再右移一位、得到可計(jì)算出：37（5）以此類推，38n1344計(jì)算區(qū)3139另外，由于DFS與IDFS的對(duì)稱性，對(duì)周期序列乘積，存在著頻域的周期卷積公式若則：僅多一個(gè)系數(shù)4.頻域卷積性質(zhì)40主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用

411.余數(shù)運(yùn)算2.有限長(zhǎng)x(n)和周期3.有限長(zhǎng)X(k)和周期3.3離散傅立葉變換及其性質(zhì)

（DFTandit’sProperties）3.2.1離散Fourier變換一.預(yù)備知識(shí)二.從DFS到DFT42如果，m為整數(shù)；則有：

一.預(yù)備知識(shí)1.余數(shù)運(yùn)算

是的解,或稱作取余數(shù),或說作n對(duì)N取模值,或簡(jiǎn)稱為取模值,n模N。此運(yùn)算符表示n被N除，商為m，余數(shù)為。43例如：

(1)(2)44=,0nN-10,其他n周期序列是有限長(zhǎng)序列x(n)的周期延拓。有限長(zhǎng)序列x(n)是周期序列的主值序列。

2.有限長(zhǎng)序列x(n)和周期序列的關(guān)系45如：N-1nx(n)0......n0N-1定義從n=0到（N-1）的第一個(gè)周期為主值序列或區(qū)間。46同樣，周期序列是有限長(zhǎng)序列X(k)的周期延拓。而有限長(zhǎng)序列X(k)是周期序列的主值序列。3.有限長(zhǎng)序列X(k)和周期序列的關(guān)系47二.從DFS到DFT

從上式可知，DFS,IDFS的求和只限定在n=0到n=N-1,及k=0到N-1的主值區(qū)間進(jìn)行。DFS：48,0kN-1,0nN-1或者：離散Fourier變換——DFT1.由DFS導(dǎo)出DFT。49

有限長(zhǎng)序列的Fourier變換稱為離散Fourier變換（DFT）。定義方法：由DFS導(dǎo)出DFT。

1.將有限長(zhǎng)序列延拓成周期序列；

2.求周期序列的DFS得；

3.取出的一個(gè)周期作為的DFT。2.DFT定義：50因此，由DFS可得出有限長(zhǎng)序列的DFT為：51注：①均為有限長(zhǎng)，長(zhǎng)度一樣，取值范圍均為0，1，…，N-1（有限長(zhǎng)序列的DFT仍為有限長(zhǎng)序列）②n為離散時(shí)間變量，理解為nT，k為離散頻率變量，理解為；均可進(jìn)行計(jì)算機(jī)處理。③DFT與DFS無本質(zhì)區(qū)別，DFT是DFS的主值，DFT隱含周期性；④DFT具有唯一性；52⑤一般情況下，是一個(gè)復(fù)變量，可表示為：或其中：⑥旋轉(zhuǎn)因子的性質(zhì)：

a．對(duì)稱性：；

b．周期性：；53c．換底：，為整數(shù)；d．幾個(gè)特殊值：，，，。⑦點(diǎn)的DFT為：54

結(jié)論：是Z變換在單位圓上抽樣，抽樣點(diǎn)在單位圓上的N個(gè)等分點(diǎn)上，且第一個(gè)抽樣點(diǎn)為k=0。如果，代入有1234567(N-1)k=0⑧DFT與ZT的關(guān)系：55有限長(zhǎng)序列x（n）的DFT系數(shù)X（k）可看作其ZT在單位圓上等角距取樣的樣本值，即：

DFT與FT的關(guān)系：有限長(zhǎng)序列x（n）的DFT系數(shù)X（k）可看作其FT在一個(gè)周期（）中等間距取樣的樣本值，取樣間隔，即：

56例3.3.1：已知序列：；求其9點(diǎn)DFT？解：由DFT的定義，有：57例3.3.2：已知，求的9點(diǎn)DFT逆變換。解：由IDFT的定義，有：注：58例3.3.3：已知序列：；求其4點(diǎn)DFT，8點(diǎn)DFT，16點(diǎn)DFT？并畫出的曲線圖。解：的FT為：4點(diǎn)DFT：

4點(diǎn)序列及DFT圖形如下：598點(diǎn)DFT：8點(diǎn)序列及DFT圖形如下：16點(diǎn)DFT：16點(diǎn)序列及DFT圖形如下：60例3.3.4已知x(n)是長(zhǎng)為N的有限長(zhǎng)序列，X(k)=DFT[x(n)]，現(xiàn)將x(n)的每二點(diǎn)之間補(bǔ)進(jìn)r-1個(gè)零值，得到一個(gè)長(zhǎng)為rN的有限長(zhǎng)序列y(n)求DFT[y(n)]與X(k)的關(guān)系。)(ny)(nxnn0061解：已知？62考慮N點(diǎn)DFT：rN點(diǎn)DFT：思考：為什么會(huì)這樣？63p2p2pp)(wX)(wYww)(ny)(nxnn00時(shí)域：連續(xù)譜：一周期643.3.2離散傅立葉變換的性質(zhì)A.和的長(zhǎng)度均為N，且它們對(duì)應(yīng)的DFT為：設(shè)1.線性：a，b均為常數(shù)，則：65B.和的長(zhǎng)度N1和N2不等時(shí)，選擇為變換長(zhǎng)度,短者進(jìn)行補(bǔ)零達(dá)到N點(diǎn)。662.復(fù)共軛序列的DFT設(shè)是的復(fù)共軛序列，長(zhǎng)度為N，其DFT變換為：67證明：

又由于隱含周期性，有： 當(dāng)為實(shí)序列時(shí)，則有：683.對(duì)稱性Ａ.定義有限長(zhǎng)共軛對(duì)稱序列，也可稱為圓周共軛對(duì)稱序列。有限長(zhǎng)共軛反對(duì)稱序列注：①變換區(qū)間：②以為對(duì)稱點(diǎn)③頻域定義：共軛對(duì)稱序列共軛反對(duì)稱序列69B.序列分解①（長(zhǎng)度均為N）其中：②其中：③頻域：70C.DFT的共軛對(duì)稱性①其中：②其中：例：71③當(dāng)為實(shí)序列（長(zhǎng)度為N），且則有：a.共軛對(duì)稱，即：b.如為實(shí)偶對(duì)稱序列，則為實(shí)偶對(duì)稱序列，即：c.如為實(shí)奇對(duì)稱序列，則為純虛奇對(duì)稱序列，即：

72d．如為實(shí)序列，則的計(jì)算量減半，則：推導(dǎo)這些結(jié)論時(shí)注意：實(shí)序列：實(shí)偶序列：實(shí)奇序列：因果序列：73附：序列及其DFT的奇偶虛實(shí)關(guān)系對(duì)應(yīng)表如下：

時(shí)域或頻域

頻域或時(shí)域偶偶奇奇實(shí)實(shí)部為偶，虛部為奇（即圓周共軛對(duì)稱序列）虛實(shí)部為奇，虛部為偶（即圓周共軛反對(duì)稱序列）實(shí)、偶實(shí)、偶實(shí)、奇虛、奇虛、偶虛、偶虛、奇實(shí)、奇74

4.序列的循環(huán)移位： 一個(gè)長(zhǎng)度為N的序列的循環(huán)移位定義為：A.這里包括三層意思：先進(jìn)行周期延拓再進(jìn)行移位最后取主值序列：75n0N-176n0周期延拓n0左移277n0取主值N-178B.圓周位移的含義

由于我們?nèi)≈髦敌蛄?，即只觀察n=0到N-1這一主值區(qū)間，當(dāng)某一抽樣從此區(qū)間一端移出時(shí)，與它相同值的抽樣又從此區(qū)間的另一端進(jìn)來。如果把

排列一個(gè)N等分的圓周上，序列的移位就相當(dāng)于

在圓上旋轉(zhuǎn)，故稱作圓周移位。當(dāng)圍著圓周觀察幾圈時(shí)，看到就是周期序列7912345n=0N=680例3.3.4：一個(gè)N＝6點(diǎn)序列，其循環(huán)移位如下：81序列循環(huán)移位后DFT為：82證明：由周期序列的周期移位性質(zhì)得：是的主值序列，其DFT是的DFS的主值。即：由時(shí)域和頻域的對(duì)偶關(guān)系，作循環(huán)移位時(shí)有：設(shè)則：83附：幾種變換的時(shí)移性質(zhì)匯總：①②③④845.循環(huán)卷積（CircularConvolution）：對(duì)于兩個(gè)長(zhǎng)度均為N的序列和，設(shè)，則：N相當(dāng)于將作周期卷積和后，再取主值序列。85證明：將周期延拓：則有：DFS的性質(zhì)頻域相乘時(shí)域周期卷積86在主值區(qū)間，所以：N同樣可證：N頻域相乘時(shí)域卷積87特點(diǎn)：①循環(huán)卷積的過程與周期卷積一樣，只取周期卷積的主值；②循環(huán)卷積隱含周期性；③循環(huán)卷積在主值區(qū)間內(nèi)進(jìn)行，參與卷積的兩個(gè)序列的長(zhǎng)度和結(jié)果序列的長(zhǎng)度均相等；④線性卷積與循環(huán)卷積計(jì)算步驟比較：線性卷積：反折、平移、相乘、積分（或相加）；循環(huán)卷積：反折、周期化、平移、相乘、相加。

88時(shí)域循環(huán)卷積過程N(yùn)-10nN-10n周期化890m0m0m0m反折移位90910233211N-1nN最后結(jié)果：92例3.3.5：已知兩個(gè)4點(diǎn)序列：，求：

④。解：由循環(huán)卷積的公式：④卷積過程如下：

(和的圖形如下)

9394④95循環(huán)卷積又稱“圓卷積”課本：73頁圖3.696主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用

973.4利用循環(huán)卷積計(jì)算線性卷積

(ToComputeLinearConvolutionUsingCircularConvolution）3.4.1卷積比較線性卷積周期卷積循環(huán)卷積有區(qū)別有聯(lián)系主值和延拓?zé)o本質(zhì)區(qū)別1、計(jì)算區(qū)間不同：循環(huán)卷積：主值區(qū)間線性卷積：無限制2、卷積結(jié)果長(zhǎng)度不同：循環(huán)卷積：長(zhǎng)度為N線性卷積：2N-175頁圖98循環(huán)卷積與線性卷積99設(shè)：兩有限長(zhǎng)序列:3.4.2由循環(huán)卷積求線性卷積L1.線性卷積2.循環(huán)卷積長(zhǎng)度為M長(zhǎng)度為N其中100因?yàn)長(zhǎng)分析循環(huán)卷積：因?yàn)?01結(jié)論：①等于以L為周期的周期延拓序列的主值序列；②兩個(gè)長(zhǎng)度為M，N的序列的線性卷積可用長(zhǎng)度均為L(zhǎng)的循環(huán)卷積來代替。其中L應(yīng)：。③當(dāng)時(shí)，其循環(huán)卷積的結(jié)果與線性卷積不相等，但滿足一定關(guān)系；102例3.4.1：已知序列：1.求和的15點(diǎn)循環(huán)卷積，畫出其略圖；2.求和的19點(diǎn)循環(huán)卷積，畫出其略圖。解：1.2.注：本題中103例3.4.2：已知：請(qǐng)問序列中的那些值與序列的值相同？比較的結(jié)果得：當(dāng)時(shí)，104主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用

105

1.ZT與FT：?jiǎn)挝粓A上的ZT等于序列的FT；

2.LT與ZT：

S平面到Z平面的映射關(guān)系：S平面上寬度為的水平帶映射成整個(gè)Z平面，左半帶映射成單位圓內(nèi)，右半帶映射成單位圓外，長(zhǎng)為的虛軸映射成單位圓；3.5頻率取樣（FrequencySampling

）3.5.1序列的幾種變換的關(guān)系106

3.DFT與ZT：

DFT是ZT在單位圓上等角距（）取樣的樣本值；

4.DFT與FT：

DFT是FT在一個(gè)周期（）內(nèi)等間距取樣值，取樣間隔為。107時(shí)域抽樣:

對(duì)象：一個(gè)頻帶有限的信號(hào)原則：根據(jù)抽樣定理對(duì)其進(jìn)行抽樣結(jié)果：所得抽樣信號(hào)的頻譜，是原帶限信號(hào)頻譜的周期延拓。不混疊時(shí)，完全可以由抽樣信號(hào)恢復(fù)原信號(hào)。3.5.2兩種抽樣108頻域抽樣:

對(duì)象：一有限序列(時(shí)間有限序列)

方法：進(jìn)行DFT所得x(k)就是序列傅氏變換的采樣.所以DFT就是頻域抽樣。109

頻域取樣： 指對(duì)時(shí)域已是離散，頻域仍是連續(xù)的信號(hào)，在頻域上進(jìn)行抽樣處理，使其頻域也離散化110設(shè)任意長(zhǎng)序列對(duì)求IDFT得：在單位圓上對(duì)其等角距取樣，取樣點(diǎn)數(shù)為M，則：其ZT為：絕對(duì)可和3.5.3從N個(gè)頻域取樣值恢復(fù)時(shí)間序列恢復(fù)的時(shí)域序列111代入，得：Z平面單位圓上對(duì)ZT進(jìn)行等角距取樣，將導(dǎo)致時(shí)間序列的周期延拓。是一個(gè)周期序列，其主值為：注：r為整數(shù)，且112分析：①對(duì)于長(zhǎng)度為N的有限長(zhǎng)序列，ZT取樣即頻率取樣不失真的條件是取樣點(diǎn)數(shù)M應(yīng)等于或大于原序列的長(zhǎng)度N，即：。當(dāng)x(n)不是有限長(zhǎng)時(shí)，一定失真；113②當(dāng)N=5，M=8時(shí)，時(shí)域延拓?zé)o混疊現(xiàn)象，此時(shí)原序列可以完全恢復(fù)，如下圖所示；注：時(shí)域中原信號(hào)為紅色，延拓取主值的恢復(fù)信號(hào)為藍(lán)色。時(shí)域頻域114③當(dāng)N=5，M=5時(shí)，時(shí)域延拓恰好無混疊現(xiàn)象，此時(shí)原序列可以完全恢復(fù)，如下圖所示；115④當(dāng)N=5，M=4時(shí)，時(shí)域延拓存在混疊現(xiàn)象，此時(shí)原序列不能完全恢復(fù)，如下圖所示。116例3.5.1：已知因果序列，設(shè)：試寫出與之間的關(guān)系式，并畫出的波形圖。解：117例3.5.2：已知序列：，若為的ZT，如果對(duì)在處采樣后得到：，畫出由的IDFT所得到的序列的略圖。解：由頻率取樣理論可知：1183.5.4從N個(gè)取樣值恢復(fù)或設(shè)原序列長(zhǎng)度為N，其ZT為：由IDFT得：代入得：內(nèi)插函數(shù)119說明： 長(zhǎng)度為N的序列的ZT可用其單位圓上的N個(gè)取樣值來恢復(fù)。注：其中：令，得FT的內(nèi)插公式：120長(zhǎng)度為N的序列的FT可通過Z平面單位圓上的N個(gè)取樣值，即N個(gè)頻域取樣值來恢復(fù)?！瓋?nèi)插函數(shù)說明：121結(jié)論：1.對(duì)于長(zhǎng)度為N的序列，其N個(gè)頻域取樣值就可以不失真地代表它；2.這N個(gè)取樣值也能完全表示整個(gè)和。頻率取樣理論是用頻率取樣法設(shè)計(jì)FIR數(shù)字濾波器（DF）的理論基礎(chǔ)。122主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用

1233.6快速傅立葉變換

（FastFourierTransform－FFT）3.6.1引言（Introduction）DFT變換對(duì)：將DFT計(jì)算寫成矩陣形式：124其中：

通常x(n)和 都是復(fù)數(shù),所以計(jì)算一個(gè)X(k)的值需要N次復(fù)數(shù)乘法運(yùn)算,和 次復(fù)數(shù)加法運(yùn)算.一、分析DFT運(yùn)算量：1.計(jì)算一個(gè)X(k)的值,如X(1)2.計(jì)算所有的X(k)的值要N2次復(fù)數(shù)乘法運(yùn)算,N(N-1)次復(fù)數(shù)加法運(yùn)算.125結(jié)論：當(dāng)N很大時(shí),DFT運(yùn)算量將是驚人的如N=1024,則要完成1048576次(一百多萬次)復(fù)數(shù)乘法運(yùn)算.這樣,難以做到實(shí)時(shí)處理.直接計(jì)算N點(diǎn)DFT的運(yùn)算量：復(fù)數(shù)乘法：N2次復(fù)數(shù)加法：N(N-1)次復(fù)數(shù)計(jì)算：實(shí)數(shù)乘法：4N2次實(shí)數(shù)加法：2N2＋2N(N-1)次1.復(fù)數(shù)乘法：即：含兩次實(shí)數(shù)加法和四次實(shí)數(shù)乘法2.復(fù)數(shù)加法：兩次實(shí)數(shù)加法126二、IDFT的計(jì)算量

兩者的差別僅在指數(shù)的符號(hào)和因子1/N.

比較DFT和IDFT變換對(duì)：127觀察DFT公式三、減少計(jì)算量的途徑

提高DFT運(yùn)算速度，唯一可以利用的是：稱為旋轉(zhuǎn)因子，表示為：1281.旋轉(zhuǎn)因子的性質(zhì)：

a．對(duì)稱性：

b．周期性：

c．換底： 要求：為整；

d．幾個(gè)特殊值：1292.點(diǎn)的DFT分別為：130改進(jìn)思路： 利用旋轉(zhuǎn)因子特性,可將有些項(xiàng)合并,并將DFT分解為短序列,從而降低運(yùn)算次數(shù),提高運(yùn)算速度.1965年,庫利(cooley)和圖基(Tukey)首先提出FFT算法.計(jì)算量：對(duì)于N點(diǎn)DFT,僅需(N/2)log2N次復(fù)數(shù)乘法運(yùn)算.如：N=1024=210時(shí)，復(fù)數(shù)乘法：(1024/2)log2210=512*10=5120次。改變：5120/1048576=4.88%,速度提高20倍131

FFT算法有很多種，這里僅介紹兩種最基本的算法：1.時(shí)間抽選FFT算法

——Decimation-in-TimeFFT；2.頻率抽選FFT算法

——Decimation-in-FrequencyFFT；

說明： 上述兩種算法均假設(shè)N是2的整數(shù)冪，即以2為基的FFT算法。1323.6.2時(shí)間抽取FFT算法

（Decimation-In-TimeFFT－DITFFT）

基本出發(fā)點(diǎn)： 利用的周期性和對(duì)稱性，將DFT的計(jì)算分解成一些逐次減小的DFT計(jì)算；假設(shè)（M：正整數(shù)），則：1.分解規(guī)則：（1）對(duì)時(shí)間進(jìn)行偶奇分，（2）對(duì)頻率進(jìn)行前后分。不足時(shí),可補(bǔ)些零(一)分解成N/2點(diǎn)DFT133時(shí)間信號(hào)序列表示為：由規(guī)則（1），將按序號(hào)偶奇分，得：分解1：即：按n的奇偶分為兩N/2的短序列偶序列：奇序列：134N點(diǎn)DFT表示為：說明：N點(diǎn)的DFT可由兩個(gè)N/2點(diǎn)的DFT來計(jì)算135注意兩點(diǎn):

(1)G(k),H(k)均為N/2點(diǎn)的DFT。其中,

只能確定出前一半的結(jié)果，即：(2)后一半怎么辦呢？136由規(guī)則（2），將分為前后兩組：

分解2——X(k)的后一半的確定A.前一半（頻域前序列）可表示為：前序列：后序列：即：按k的前后分為兩N/2的短序列分解一的結(jié)論137B.后一半（頻域后序列）的表示：觀察有：

說明：

X(k)的后一半，也完全由G(k),H(k)

所確定。138說明：N點(diǎn)的DFT可由兩個(gè)N/2點(diǎn)的DFT來計(jì)算。C.合在一起：

即：頻域前、后序列可分別由時(shí)域偶、奇序列的N/2點(diǎn)DFT的組合來表示139實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算2.蝶形運(yùn)算（N/2個(gè)蝶形)(前一半)(后一半)1111-11403.計(jì)算量分析復(fù)乘:復(fù)加:總共運(yùn)算量:按奇、偶分組后的計(jì)算量：(1)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):

復(fù)加次數(shù):(2)兩個(gè)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):

復(fù)加次數(shù):

(3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù):

復(fù)加次數(shù):

141計(jì)算量比較

結(jié)論：

N點(diǎn)DFT分解成由兩N/2點(diǎn)DFT計(jì)算，計(jì)算量比直接計(jì)算，差不多減少一半。復(fù)乘復(fù)加直接計(jì)算分解計(jì)算142N點(diǎn)的DFT計(jì)算分解成兩個(gè)點(diǎn)的DFT計(jì)算。4.信號(hào)流圖如下（8點(diǎn)為例）偶奇后前143例:N=8

時(shí)的DFT,可以分解為兩個(gè)N/2=4點(diǎn)的DFT.

步驟如下:(1)n為偶數(shù)時(shí),即

分別記作: 144

(2)n為奇數(shù)時(shí),分別記作:(3)對(duì)G(k)和H(k)進(jìn)行蝶形運(yùn)算,分前序列

X(0)～X(3),后序列X(4)～X(7)145

x1(0)=x(0)

x1(1)=x(2)N/2點(diǎn)

x1(2)=x(4)DFT

x1(3)=x(6)

x2(0)=x(1)

x2(1)=x(3)

N/2點(diǎn)

x2(2)=x(5)

DFT

x2(3)=x(7)

~~X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)對(duì)G(k)和H(k)進(jìn)行蝶形運(yùn)算,前半部為

X(0)X(3),后半部分為X(4)X(7)

整個(gè)過程如下圖所示:146，N為偶數(shù)，N/2也為偶數(shù)(二)分解成N/4點(diǎn)DFT原序號(hào)變?yōu)椋合喈?dāng)于x(n)經(jīng)兩次分組偶中偶偶中奇奇中偶奇中奇N點(diǎn)DFTX(k)N/2點(diǎn)DFTG(k)N/2點(diǎn)DFTH(k)N/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFT1.以G(k)分解為例：時(shí)域g(n)偶奇分頻域G(k)前后分147偶中偶偶中奇兩N/4長(zhǎng)的序列：對(duì)應(yīng)的兩N/4點(diǎn)DFT：N/2點(diǎn)DFT分解為兩N/4點(diǎn)DFT：前后148計(jì)算的信號(hào)流圖如下：1492.類似地，H(k)可得：其中：均是點(diǎn)的DFT；1503.將8點(diǎn)DFT轉(zhuǎn)化為4個(gè)2點(diǎn)DFT的流圖：N/2點(diǎn)DFTN/2點(diǎn)DFT151

這樣,經(jīng)第二次分解,得到四個(gè)N/4點(diǎn)DFT,

兩級(jí)蝶形運(yùn)算,其運(yùn)算量有大約減少一半即為N點(diǎn)DFT的1/4。4.轉(zhuǎn)化為4個(gè)N/4點(diǎn)DFT的計(jì)算量：152對(duì)于N=8時(shí)DFT,N/4點(diǎn)即為兩點(diǎn)DFT,因此(三)分解的終點(diǎn)153以M(k)為例分析1548點(diǎn)DFT的完整FFT流圖如下：(四)完整的FFT155

具有三個(gè)特點(diǎn)：①基本計(jì)算單元為一碟形；②輸入為“混序”排列；輸出為正序排列；③具有“同址計(jì)算”特性。

3.6.3時(shí)間抽選FFT特點(diǎn)

這種FFT算法,是在時(shí)間上對(duì)輸入序列的次序是屬于偶數(shù)還是屬于奇數(shù)來進(jìn)行分解的,所以稱作按時(shí)間抽選基2FFT算法156 1.蝶形計(jì)算：由流圖可知：一共有N個(gè)輸入/出行,

一共有l(wèi)og2N=M列(級(jí))蝶形運(yùn)算.

設(shè):m(m=1,2,…,L)表示第m列;p,q表蝶形輸入數(shù)據(jù)所在的(上/下)行數(shù)(0,1,…,N-1)則，任一個(gè)蝶形運(yùn)算可用下面通用式表示：157B.完成點(diǎn)的DFT計(jì)算需級(jí)迭代計(jì)算，每級(jí)N/2個(gè)蝶形；蝶形數(shù)FFT計(jì)算量統(tǒng)計(jì)C.完成N點(diǎn)的時(shí)間抽選FFT的總計(jì)算量為：A.一個(gè)蝶形運(yùn)算需2次復(fù)加法和1次復(fù)乘法。158計(jì)算量比較說明：由于計(jì)算機(jī)的乘法運(yùn)算比加法運(yùn)算所需的時(shí)間多得多，故以乘法作為比較基準(zhǔn).復(fù)乘次數(shù)FFT直接計(jì)算比值159例：當(dāng)時(shí)，可以算得：即：DFT需205小時(shí)，F(xiàn)FT需1小時(shí)。1602.同址計(jì)算：蝶形計(jì)算的好處：同址計(jì)算已知：完成N點(diǎn)時(shí)間抽選FFT計(jì)算需級(jí)迭代運(yùn)算，每級(jí)運(yùn)算均由N/2個(gè)蝶形計(jì)算構(gòu)成。已知：p,q表蝶形輸入數(shù)據(jù)所在的行數(shù)觀察蝶形計(jì)算：161

發(fā)現(xiàn)：

某列(級(jí))進(jìn)行蝶形運(yùn)算過程中， 任意兩個(gè)節(jié)點(diǎn)(行)p和q的節(jié)點(diǎn)變量：可完全可以確定此蝶形運(yùn)算的結(jié)果：

與其它行(節(jié)點(diǎn))無關(guān)。

這樣,蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中,即實(shí)現(xiàn)所謂同址(原位)運(yùn)算。每一組(列)有N/2個(gè)蝶形運(yùn)算,只需N個(gè)存儲(chǔ)單元，可以節(jié)省存儲(chǔ)單元。162說明：A.上圖中Q(0)～Q(7)表示存儲(chǔ)單元B.完成最后一級(jí)運(yùn)算，中間不需其它存貯器同址運(yùn)算：節(jié)省存貯單元。當(dāng)N越大，好處越明顯。163

3.變址計(jì)算：從流圖可知:輸出X(k)按正常順序排列在存儲(chǔ)單元：是“混序”排列；而輸入是按順序:方法：在實(shí)際計(jì)算中，輸入的“混序”是通過輸入正序排列按“碼位倒置”的變址處理得到的164

00

0

00

0

00

10

0

11

0

04

20

1

00

1

02

30

1

11

1

06

41

0

00

0

11

51

0

11

0

15

61

1

00

1

13

71

1

11

1

17自然順序n二進(jìn)制nnn倒位序二進(jìn)制nnn倒位順序n^210012165A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)變址處理方法存儲(chǔ)單元自然順序變址倒位序166n=00n=10n=01n=11n=01n=1101010101

(n2)x(000)0x(100)4x(010)2x(110)6x(001)1x(101)5x(011)3x(111)7（偶）（奇）

原因：由偶奇分組造成的,以N=8為例說明如下:1673.6.4頻率抽選FFT算法

（Decimation-In-FrequencyFFT－DIFFFT）推導(dǎo)規(guī)則：（1）對(duì)時(shí)間前后分；（2）對(duì)頻率偶奇分。推導(dǎo)過程與時(shí)間抽選FFT算法類似，請(qǐng)同學(xué)們可參考教材自己推導(dǎo)。168稍微變動(dòng)FFT程序和參數(shù)可實(shí)現(xiàn)IFFT3.6.5

IFFT算法比較兩式可知:只要DFT的每個(gè)系數(shù)

換成

,最后再乘以常數(shù)1/N就可以得到IDFT的快速算法--IFFT。另外,可將1/N分到每級(jí)運(yùn)算中,∵,也就是每級(jí)蝶形運(yùn)算均乘以1/2。1693.6.4N為合數(shù)的FFT算法如果序列的長(zhǎng)度，通常有兩種處理方法：

1.用補(bǔ)零的辦法將延長(zhǎng)為，再使用基2FFT算法。由于有限長(zhǎng)序列補(bǔ)零以后，只是頻譜的取樣點(diǎn)有所增加。

2.采用以任意數(shù)為基數(shù)的FFT算法。設(shè)N等于兩個(gè)整數(shù)p和q的乘積，即，則可將N點(diǎn)DFT分解成p個(gè)q點(diǎn)DFT或q個(gè)p點(diǎn)DFT來計(jì)算。先將分為p組，每組長(zhǎng)為q，即：p組170例：當(dāng)時(shí)，可以將分成3組，每組2點(diǎn)。解：可將分為以下3組： 第1組： ； 第2組： ； 第3組： 。可以將6點(diǎn)的DFT分解為：即將6點(diǎn)的DFT分解成3個(gè)2點(diǎn)的DFT運(yùn)算。171然后將N點(diǎn)DFT也分解為p組來計(jì)算，每組計(jì)算q點(diǎn)的DFT，即：

由于，因此，

是一個(gè)q點(diǎn)DFT，這樣N點(diǎn)DFT可寫成：

172一個(gè)的DFT流程圖如下圖所示。例：當(dāng)時(shí)，為：如上圖中紅線所示。173主要內(nèi)容：3.1引言3.2離散傅里葉級(jí)數(shù)及其性質(zhì)3.3離散傅里葉變換及其性質(zhì)3.4利用循環(huán)卷積計(jì)算線性卷積3.5頻率取樣3.6快速傅里葉變換3.7

FFT應(yīng)用1743.7

FFT應(yīng)用（TheApplicationsofFFT

）3.7.1