1、第3章 傅里葉分析傅里葉分析是利用傅里葉變換來分析信號的一種通用工具，其實質(zhì)是將信號分解成若干個不同頻率的正弦波之和。它在信號處理的理論和應(yīng)用中具有重要意義。3.1 傅里葉變換概述我們知道，傅里葉變換定義了以時間為自變量的“信號”與以頻率為自變量的“頻譜函數(shù)”之間的某種變換關(guān)系，也就是說，傅里葉變換建立了時域和頻域之間的聯(lián)系。所以當自變量“時間”或“頻率”取連續(xù)值或離散值時，就形成了各種不同形式的傅里葉變換對。一、 時間連續(xù)、頻率連續(xù)的傅里葉變換（FT）其傅里葉變換公式為：正變換 反變換 連續(xù)時間非周期信號x(t)的傅里葉變換結(jié)果是連續(xù)的非周期的頻譜密度函數(shù)X(j)，如圖所示?？梢姡瑫r域函數(shù)的

2、連續(xù)性造成頻域函數(shù)的非周期性，而時域的非周期性造成頻譜的連續(xù)性。二、 時間連續(xù)、頻率離散的傅里葉變換傅里葉級數(shù)（FS）周期為T的周期性連續(xù)時間函數(shù)x(t)可展開成傅里葉級數(shù)，其系數(shù)為X(jk0)，X(jk0)是離散頻率的非周期函數(shù)。x(t)和X(jk0)組成變換對，其變換公式為：正變換 反變換 式中，k諧波序號； 0=2/T兩條相鄰的離散譜線之間角頻率的間隔；x(t)和X(jk0)之間的變換關(guān)系如圖所示。可見，時域函數(shù)的連續(xù)性造成頻域函數(shù)的非周期性，而時域函數(shù)的周期性造成頻域函數(shù)的離散化。三、 時間離散、頻率連續(xù)的傅里葉變換序列的傅里葉變換（DTFT）1. DTFT的定義序列的傅里葉變換公式為

3、：正變換 反變換 注意：序列x(n)只有當n為整數(shù)時才有意義，否則沒有定義。由于存在關(guān)系因此，序列的傅里葉變換也就是單位圓上的Z變換。x(n)和X(ej)之間的變換關(guān)系如圖所示。可見，時域的離散化造成頻譜函數(shù)的周期性延拓，而時域的非周期性造成頻域的連續(xù)性。2. DTFT的性質(zhì)（1） 線性定理（2） 時移定理（3） 頻移定理（4） 對稱性定理對于復數(shù)序列x(n)，則當它滿足： x(n)=x*(-n)時，該序列稱為共軛對稱序列xe(n)；對于實序列而言，此條件變?yōu)閤(n)=x(-n)，即xe(n)又稱為偶對稱序列。 x(n)=-x*(-n)時，該序列稱為共軛反對稱序列xo(n)；對于實序列而言，此

4、條件變?yōu)閤(n)=-x(-n)，即xo(n)又稱為奇對稱序列。任意一個序列總能表示成一個共軛對稱序列與一個共軛反對稱序列之和，即x(n)= xe(n)+ xo(n)證：欲證明這一點，只需找到xe(n)和xo(n)即可，則令不難看出，這里的xe(n)與xo(n)分別滿足共軛對稱與共軛反對稱的條件，且二者之和為x(n)，由此得證。類似地，序列x(n)的傅里葉變換X(ej)也可分解成共軛對稱與共軛反對稱分量之和，即X(ej)= Xe(ej)+ Xo(ej)其中，有關(guān)序列的傅里葉變換的對稱性定理，參見P59 表3.1.1所示。其中，性質(zhì)4表明：序列實部的傅里葉變換等于序列傅里葉變換的共軛對稱分量；性質(zhì)

5、5表明：序列虛部乘j后的傅里葉變換等于序列傅里葉變換的共軛反對稱分量；反過來，性質(zhì)6、性質(zhì)7則表明：序列的共軛對稱和共軛反對稱分量的傅里葉變換分別等于序列傅里葉變換的實部和j乘虛部；性質(zhì)10表明：對于任意實序列x(n)，其傅里葉變換X(ej)滿足共軛對稱性，且可以得出，實序列傅里葉變換的實部是的偶函數(shù)，而虛部是的奇函數(shù)；性質(zhì)11、性質(zhì)12表明：實序列x(n)的偶對稱序列分量xe(n)和奇對稱序列分量xo(n)的傅里葉變換分別為序列x(n)的傅里葉變換的實部和j乘虛部。（5） 卷積定理注意：此處的卷積又稱為線性卷積。I. 時域卷積定理若，則證：已知則復習：序列的運算 序列的運算包括翻褶、移位、和

6、、積等。（a） 翻褶 如果序列為x(n)，則x(-n)是以n=0的縱軸為對稱軸將序列x(n)加以翻褶。（b） 移位 如果序列為x(n)，當m為正時，則序列x(n+m)是指將序列x(n)依次逐項左移m位；當m為負時，則右移m位。（c） 和 兩序列的和是指同序號（n）的序列值逐項對應(yīng)相加。（d） 積兩序列的積是指同序號（n）的序列值逐項對應(yīng)相乘。線性卷積的幾何意義：若兩序列x(n)和h(n)的卷積和定義為則卷積的運算過程包含以下四步：翻褶：先在坐標系上作出h(m)，將h(m)以m=0的縱軸為對稱軸翻褶成h(-m)；移位：將h(-m)移位n，即得h(n-m)；注意： h(-m) 與h(m)的移位規(guī)律

7、恰好相反，當n為正時，則右移n位；當n為負時，則左移n位。相乘：再將相同m值所對應(yīng)的h(n-m)和x(m)值相乘；相加：將上述所有對應(yīng)點的乘積疊加，即得y(n)值；依次取n=，-2，-1，0，1，2，即可得到全部的y(n)值。II. 頻域卷積定理若，則上述兩個卷積定理表明：離散時間序列的時域卷積對應(yīng)頻域相乘，而時域相乘則對應(yīng)其頻域卷積。（6） Parseval（帕塞瓦）定理證：Parseval（帕塞瓦）定理表明：信號在時域的總能量就等于其頻域的總能量。四、 時間離散、頻率離散的傅里葉變換離散傅里葉變換（DFT）除了三種傅里葉變換的形式以外，其實還有一種情況時間離散、頻率離散的傅里葉變換（即：我

8、們在后續(xù)章節(jié)中將要介紹的離散傅里葉變換DFT）。由上述討論的四種傅里葉變換的形式，我們不難得出這樣的結(jié)論：一個域（時域或頻域）的離散化必然造成另一個域的周期延拓。習題：3.1, 3.2, 3.3思考題：P102 3.1, 3.3, 3.43.2 周期序列的離散傅里葉級數(shù)（DFS）既然一個域的離散化會造成另一個域的周期延拓，我們不妨從周期序列的離散傅里葉級數(shù)開始討論，然后再討論可視為是周期序列的一個周期的有限長序列的離散傅里葉變換。一、 DFS的定義1. 周期序列的概念設(shè)是周期為N的一個周期序列，即， r為任意整數(shù)因為在任何z值下，周期序列z變換的和式都不收斂，即也就是說，周期序列不是絕對可和的

9、，所以不能用z變換表示。 但是，和連續(xù)時間周期信號一樣，周期序列可以用離散傅里葉級數(shù)來表示，也就是用周期為N的復指數(shù)序列來表示。2. 周期序列的離散傅里葉級數(shù)變換對（1） 數(shù)學推導（可略，參見教材P6162）I. 的推導周期為N的復指數(shù)序列為其k次諧波序列由于，r為任意整數(shù)則因而，離散傅里葉級數(shù)的所有諧波分量中只有N個是獨立的。這里，我們?nèi)=0 (N-1)的N個獨立諧波分量來構(gòu)成的離散傅里葉級數(shù)，即 （3.2.1）式中，為k次諧波的系數(shù)。II. 的推導欲求解系數(shù)，就要利用等比級數(shù)的求和性質(zhì) （3.2.2）將（3.2.1）式兩端同乘以，然后從n=0 (N-1)的一個周期內(nèi)求和，則 將上式中的r

10、換成k，可得 通過推導，我們可以看出，周期序列與其離散傅里葉級數(shù)的系數(shù)組成一個變換對，且也是一個周期為N的周期序列。（2） 結(jié)論一般，我們習慣采用符號，則周期序列的離散傅里葉級數(shù)變換公式為：正變換 反變換 上述表達式求和時，都只取N個序列值，這表明：雖然周期序列是無限長序列，但只要研究其一個周期（有限長）的性質(zhì)，則其他周期的性質(zhì)也就不難得知了，因而周期序列和有限長序列有著本質(zhì)的聯(lián)系。3. 的性質(zhì)（簡單介紹，參見教材P63）（1） 周期性（2） 對稱性（3） 正交性（重點強調(diào)）二、 DFS的性質(zhì)設(shè)和均是周期為N的周期序列，且有，1. 線性性質(zhì)2. 移位性質(zhì) （時移） （頻移，又稱調(diào)制特性）3.

11、周期卷積（1） 時域卷積若，則證：（可略，參見教材P63）由于則注意：此處的卷積為周期卷積。它和前面所介紹的非周期序列的線性卷積的區(qū)別在于：參與周期卷積運算的兩個序列都是周期為N的周期序列，則其卷積結(jié)果仍是一個以N為周期的周期序列；求和運算只在一個周期（m=0N-1）的范圍內(nèi)進行。周期卷積的運算過程（參見P64圖3.2.2）：運算在m=0N-1區(qū)間內(nèi)進行，先計算出n=0，1，N-1的卷積結(jié)果，然后將所得的結(jié)果進行周期延拓，即可得到所求的整個周期序列。注意：計算過程中，一個周期的某一序列值移出計算區(qū)間時，相鄰的一個周期的同一位置的序列值就移入計算區(qū)間。（2） 頻域卷積由于DFS和IDFS的對稱性

12、，同樣可以證明：時域周期序列的乘積對應(yīng)頻域周期序列的周期卷積，即：若，則 習題：3.4思考題：P102 3.5, 3.63.3 離散傅里葉變換（DFT）一、 DFT的定義由前述討論可知，周期序列實際上只有有限個序列值有意義，因而其離散傅里葉級數(shù)表達式同樣也適用于有限長序列，這就得到了我們將要介紹的有限長序列的離散傅里葉變換。1. 有限長序列和周期序列的關(guān)系設(shè)x(n)是長度為N的有限長序列。我們可以把它看成是周期為N的周期序列的一個周期，而把看成是以N為周期對x(n)進行周期延拓的結(jié)果，則有限長序列x(n)和周期序列之間的關(guān)系可表示為通常，我們將周期序列的第一個周期（n=0N-1）定義為“主值區(qū)

13、間”，故x(n)是的“主值序列”，且上述關(guān)系式可簡寫為 （3.3.1）式中，(n)N表示“n對N求余數(shù)”，或稱“n對N取模值”；令 則n1為n對N的余數(shù)，無論n1加上多少倍的N，其余數(shù)均為n1，也就是說，周期性重復出現(xiàn)的x(n)N數(shù)值是相等的。例如，是周期N=9的序列，則n=25、-5的余數(shù)分別為n = 25 = 2×9 + 7，即 (25)9 = 7n = -5 = -1×9 + 4，即 (-5)9 = 4利用長度為N的矩形序列符號RN(n)，即則（3.3.1）式又可寫成 同理，頻域周期序列也可看成是對有限長序列X(k)的周期延拓，而有限長序列X(k)則可看成是周期序列的

14、主值序列，即2. 有限長序列的離散傅里葉變換對由DFS和IDFS的公式表達式可以看出，其求和運算分別只限定在n =0N-1和k = 0N-1的主值區(qū)間內(nèi)進行，則它們完全適用于主值序列x(n)和X(k)。因此，我們可以類推得到有限長序列的離散傅里葉變換公式為：正變換 反變換 習題：3.5, 3.6, 3.7思考題：P102 3.7, 3.8二、 DFT的性質(zhì)由于DFT與DFS之間的密切關(guān)系，應(yīng)注意其性質(zhì)的異同之處以及與DFT所隱含的周期性之間的關(guān)系。1. 線性性質(zhì)設(shè)x1(n)和x2(n)均是長度為N的有限長序列，且有，則 說明：（1） 若x1(n)和x2(n)的長度均為N，則ax1(n)+bx2

15、(n)的長度也為N；（2） 若x1(n)和x2(n)的長度不等，設(shè)分別為N1和N2，則ax1(n)+bx2(n)的長度應(yīng)為二者中的最大值，即N = maxN1, N2； 例如，當N1<N2，則應(yīng)取N = N2，且需要在x1(n)的尾部補上N2 - N1個零值點，使其變?yōu)殚L度為N2的序列，再作N2點的DFT。2. 對稱性與前面介紹的序列的傅里葉變換DTFT相似，有限長序列的離散傅里葉變換DFT也具有對稱性（又稱圓周共軛對稱），且這種對稱性與周期序列的共軛對稱性密切相關(guān)。（1） 時域?qū)ΨQ性不難證明（參見教材P7172的數(shù)學推導）：任意一個長度為N的有限長序列x(n)總可以分解成兩個長度相等的

16、圓周共軛對稱分量xep(n)和圓周共軛反對稱分量xop(n)之和，即x(n)= xep(n) + xop(n) （3.3.2）其中，式中，和分別是以N為周期對有限長序列x(n)進行周期延拓后，所得到的周期序列的共軛對稱分量和共軛反對稱分量。（2） 頻域?qū)ΨQ性 利用（3.3.2）式、（3.3.3）式及（3.3.4）式，并考慮到DFT和DFS的關(guān)系，就可以推導出下列DFT的頻域?qū)ΨQ性質(zhì)（證明從略，參見教材P7273）。設(shè)，則有 這表明：共軛復序列的DFT等于序列DFT的逆象共軛。 這表明：復序列逆象共軛的DFT等于序列DFT的共軛。 這表明：復序列實部的DFT等于序列DFT的圓周共軛對稱分量；而復

17、序列虛部乘以j的DFT等于序列DFT的圓周共軛反對稱分量。 這表明：序列圓周共軛對稱分量的DFT等于序列DFT的實部；而序列圓周共軛反對稱分量的DFT等于序列DFT的虛部乘以j。 若序列x(n)是實序列，則序列的DFT只有圓周共軛對稱分量，即滿足 若序列x(n)是純虛序列，則序列的DFT只有圓周共軛反對稱分量，即滿足根據(jù)該性質(zhì)，不論屬于哪一種情況，只要知道一半數(shù)目的就可以了，另一半可利用對稱性求得，這樣在計算DFT時可以節(jié)約計算時間，提高效率。3. 循環(huán)移位（又稱圓周移位）（1） 循環(huán)移位的定義有限長序列x(n)左移m（m為正整數(shù)）位的循環(huán)移位定義為可見，上式的循環(huán)移位表示將序列x(n)周期延

18、拓成周期序列后，再左移m位并取其主值序列而得到的。注意：序列的循環(huán)移位始終限定在主值區(qū)間內(nèi)進行。如圖所示（P75圖3.3.1），有限長序列循環(huán)移位的過程中，在主值區(qū)間（n=0N-1）內(nèi)，當某序列值從區(qū)間的一端移出時，與它同值的序列值又從區(qū)間的另一端移入，因而，此過程可以看成是將序列x(n)按逆時針方向排列在一個N等分的圓周上，則序列循環(huán)左移m位就相當于將該序列在圓周上順時針旋轉(zhuǎn)m位。（2） 時域移位特性 利用DFT與DFS的關(guān)系以及DFS的時移性質(zhì)，不難證明：（3） 頻域移位特性 由時域與頻域的對偶關(guān)系，可得4. 循環(huán)卷積（又稱圓周卷積）（1） 循環(huán)卷積的定義 長度均為N的有限長序列x(n)和

19、h(n)的循環(huán)卷積定義為 （3.3.5）可見，循環(huán)卷積就是周期卷積在主值區(qū)間（n=0N-1）內(nèi)的值（2） 循環(huán)卷積的運算方法利用求和定義式（3.3.5）直接求解；利用與周期卷積的關(guān)系求解；根據(jù)循環(huán)卷積的特點，利用圖解法求解，其步驟如下：I. 將序列x(n)按逆時針方向均勻地（N等分）分布在一個圓周（內(nèi)圓）上，而將序列h(n)按順時針方向均勻地（N等分）分布在另一個圓周（外圓）上，如圖（a）所示；II. 求兩個圓上相應(yīng)序列的乘積，并疊加N項乘積作為n=0時循環(huán)卷積值y(0)；III. 若求n=1時循環(huán)卷積值y(1)，則將外圓h(n)固定，把內(nèi)圓上的序列x(n)順時針旋轉(zhuǎn)一個單位（或?qū)?nèi)圓x(n)

20、固定，把外圓上的序列h(n)逆時針旋轉(zhuǎn)一個單位，即內(nèi)、外圓相對旋轉(zhuǎn)一個單位），并將對應(yīng)項的乘積疊加，即為所求的y(1) 值，如圖（b）所示；IV. 類似地，依次取n=2N-1，重復步驟，直到將內(nèi)圓序列循環(huán)移位一周，便可以求得所有的y(n)值；（3） 時域和頻域循環(huán)卷積定理I. 時域循環(huán)卷積定理 利用DFT與DFS的關(guān)系以及DFS的時域周期卷積性質(zhì)，可以證明：若，則 這表明：兩序列循環(huán)卷積的離散傅里葉變換等于其傅里葉變換的乘積。II. 頻域循環(huán)卷積定理 由時域與頻域的對偶關(guān)系，可得若，則 這表明：兩序列乘積的離散傅里葉變換等于其傅里葉變換的循環(huán)卷積乘以1/N。（4） 循環(huán)卷積、周期卷積和線性卷積

21、的關(guān)系 利用周期卷積計算循環(huán)卷積 先計算兩序列的周期卷積（列表法，參見例3.2.3），再對卷積結(jié)果取其主值區(qū)間（n=0N-1）內(nèi)的值即可。利用循環(huán)卷積計算線性卷積I. 用循環(huán)卷積代替線性卷積的條件 設(shè)兩個有限長序列x(n)、h(n)的點數(shù)分別為N和M，其循環(huán)卷積的長度為L，則要用循環(huán)卷積代替線性卷積的條件是：循環(huán)卷積的長度L必須不小于線性卷積的長度N+M-1，即LN+M-1否則，在循環(huán)卷積周期延拓時會產(chǎn)生混疊。II. 用循環(huán)卷積實現(xiàn)線性卷積的具體步驟i) 根據(jù)上述條件，取L=N+M-1，分別將序列x(n)、h(n)補零擴展為L點序列，即，ii) 分別計算序列x(n)、h(n)的L點離散傅里葉變

22、換，即，iii) 利用時域循環(huán)卷積定理計算序列x(n)、h(n)的L點循環(huán)卷積，且它就等于其線性卷積，即 用循環(huán)卷積實現(xiàn)線性卷積的過程如圖所示。L點DFTx(n)L點L點DFTh(n)L點相乘X(k)H(k)X(k)H(k)L點IDFTy(n)x(n)N點h(n)M點補零擴展補零擴展（5） 長序列卷積的計算（可略，參見教材P8184）在長序列x(n)通過數(shù)字系統(tǒng)h(n)得到輸出y(n)=x(n)*h(n)的過程中，盡管數(shù)字系統(tǒng)的單位采樣響應(yīng)h(n)一般較短（如FIR數(shù)字濾波器），但是由于輸入序列x(n)較長而造成無法對信號進行實時處理，因此，我們必須將長序列劃分為若干個短序列來進行卷積。其方法

23、一般有兩種：重疊相加法和重疊保留法。重疊相加法將長序列x(n)劃分成長度為N的相互連接但互不重疊的若干個小段，并將每一段分別與長度為M的h(n)作L點循環(huán)卷積（取L=N+M-1），然后將各段的卷積結(jié)果相加，即可得到輸出序列y(n)（參見P82圖3.3.6所示）。注意：相鄰兩端的卷積結(jié)果中必有M-1個點發(fā)生重疊，因此應(yīng)將這些重疊部分疊加才能得到正確的輸出結(jié)果。重疊保留法將長序列x(n)劃分成長度為L的若干個小段，且相鄰兩段重疊M-1個點（即每段開始的M-1個點是前一段最后的M-1個點，但第一個分段的前M-1個點為零），再將每一段分別與長度為M的h(n)作L點循環(huán)卷積，并將各段的卷積結(jié)果的前M-1

24、個點舍去，然后將各段的卷積結(jié)果的后N個點依次連接，即可得到輸出序列y(n)（參見P83圖3.3.7所示）。注意：若每段作L+M-1點循環(huán)卷積，則其結(jié)果與線性卷積結(jié)果一致。但這里每段作L點循環(huán)卷積，則其結(jié)果中前M-1個點必然發(fā)生混疊現(xiàn)象，與線性卷積結(jié)果不一致，因此應(yīng)將這些點舍去，才能得到正確的輸出結(jié)果。5. Parseval（帕塞瓦）定理證： 由DFT的逆變換和正變換的定義，可得如果令y(n) = x(n)，則上式變?yōu)榧催@表明：序列在時域的能量與在頻域的能量是相等的。習題：3.8, 3.9, 3.10思考題：P103 3.17, 3.18三、 DFT與DTFT及Z變換的關(guān)系離散傅里葉變換DFT、

25、序列的傅里葉變換DTFT以及Z變換可以從不同角度對有限長序列進行分析，因而它們之間必然有一定的聯(lián)系。1. Z變換與DTFT的關(guān)系我們在前面介紹DTFT時曾經(jīng)提到：它與Z變換之間存在關(guān)系即：若Z變換的收斂域包含單位圓，則序列的DTFT也就是單位圓上的Z變換。因此，在計算序列的DTFT時，我們可以先求序列的Z變換，再將其結(jié)果中的變量z用ej代替即可。2. Z變換與DFT的關(guān)系有限長序列x(n)的DFT為其Z變換為對照上述公式，可知這表明：序列的DFT也就是其Z變換在單位圓上的等間隔采樣，其角度間隔為=2/N，即將單位圓N等分，各序列的DFT值均勻分布在單位圓上。因此，在計算序列的DFT時，我們也可

26、以先求序列的Z變換，再令即可。3. DTFT與DFT的關(guān)系由于Z變換在單位圓上的取值就等于序列的傅里葉變換 X(ej)，則這表明：序列的DFT也就是其DTFT的等間距采樣，其采樣間距為=2/N。序列的Z變換、DFT以及DTFT 的關(guān)系如圖所示（P68圖3.2.5）。四、 頻域采樣1. 頻域采樣定理由上述討論可知，有限長序列x(n)的離散傅里葉變換（DFT）X(k)，實際上就是其傅里葉變換（DTFT）X(ej)在主值區(qū)間內(nèi)的等間距采樣值。那么，如何采樣才能確保由頻域采樣值X(k)不失真地恢復其連續(xù)頻譜X(ej)呢？其依據(jù)也就是頻域采樣定理。頻域采樣定理：對于長度為M的有限長序列，頻域采樣不失真的

27、條件是：頻域采樣點數(shù)N不小于序列長度M，即2. 數(shù)學推導（見教材P6970，可略）利用X(k)表示X(z)的內(nèi)插公式來證明，即五、 DFT在實際應(yīng)用中的問題由于DFT實現(xiàn)了頻域采樣，且存在快速算法，所以在實際應(yīng)用中，可以利用DFT來分析時域連續(xù)信號。在此過程中，可能遇到的問題有：混疊失真、柵欄效應(yīng)、頻譜泄漏等。1. 混疊失真現(xiàn)象前面曾經(jīng)討論過，假設(shè)信號最高頻率為fh，根據(jù)采樣定理，采樣頻率fs應(yīng)滿足fs2fh即時域采樣間隔T應(yīng)滿足 （3.3.6）如果不滿足上述要求，就會產(chǎn)生頻率響應(yīng)的周期延拓分量互相重疊的現(xiàn)象，即混疊失真現(xiàn)象。設(shè)有限長序列的記錄長度為T0=NT（N為采樣點數(shù)）。對DFT來說，頻

28、率函數(shù)也要經(jīng)采樣成為離散的序列，其頻域采樣間隔（即頻率分辨率）為F0，則 （3.3.7）由公式（3.3.6）和（3.3.7）可見， 信號最高頻率fh與頻率分辨率F0存在矛盾。要使fh增加，則時域采樣間隔T就必須減小，而采樣頻率fs就增加，由于采樣點數(shù)N滿足則當N給定時，F(xiàn)0必然增加，即頻率分辨力下降。反之，若要提高頻率分辨力（減小F0），就要增加T0，當N給定時，必然導致T增加（fs減?。虼艘划a(chǎn)生混疊失真，則必然應(yīng)減小信號最高頻率fh。通過上述分析可知，要想兼顧信號最高頻率fh與頻率分辨率F0，即保持其中一個不變，而提高另一個性能的唯一方法就是增加采樣點數(shù)N，使其滿足上述公式是在未采用任

29、何特殊數(shù)據(jù)處理（比如加窗處理）的情況下，實現(xiàn)基本DFT算法所必須滿足的最低條件。2. 柵欄效應(yīng)因為DFT計算信號頻譜，只給出了基頻整數(shù)倍處的離散譜，而不是連續(xù)頻譜，這就象通過一個“柵欄”觀看景象一樣，只能在離散點上看到真實景象，這種現(xiàn)象稱為“柵欄效應(yīng)”。減小柵欄效應(yīng)的一個方法就是要使頻域采樣更密，即增加頻域采樣點數(shù)，這樣必然使各譜線間的距離更近，從而使原來被“柵欄”擋住的頻譜分量顯露出來，為此，我們可以在不改變原有數(shù)據(jù)記錄的基礎(chǔ)上，采用在時域數(shù)據(jù)的末尾補零的方法來實現(xiàn)。補零的好處在于：使頻域采樣更密，減小柵欄效應(yīng)；使采樣點數(shù)N變?yōu)?的整數(shù)次冪，便于利用計算機實現(xiàn)快速傅里葉變換（FFT）。習題：

30、3.11, 3.12, 3.13思考題：P102 3.203.4 快速傅里葉變換（FFT）由于離散傅里葉變換（DFT）實現(xiàn)了有限長序列的頻域離散化，因而可應(yīng)用于信號的頻譜分析、數(shù)字濾波器的設(shè)計以及系統(tǒng)的分析、設(shè)計和實現(xiàn)等方面。但是在相當長的時間里，由于DFT的計算量太大，即使采用計算機也很難對問題進行實時處理，所以沒有得到真正的運用。直到1965年，庫利（J.W.Cooley）和圖基（J.W.Tukey）在計算數(shù)學雜志上發(fā)表了著名的“機器計算傅里葉級數(shù)的一種算法”的文章，提出了DFT的一種快速算法，后來又相繼出現(xiàn)了桑德（G.Sande）和圖基快速算法等一系列高速有效的運算方法，使DFT的計算大

31、大簡化，運算時間縮短了一、二個數(shù)量級，從而DFT在實際中真正得到廣泛的應(yīng)用。一、 直接計算DFT的問題及改進途徑N點有限長序列x(n)的離散傅里葉變換公式為：正變換 反變換 二者的差別只在于WN的指數(shù)符號不同，以及相差一個常數(shù)因子1/N，因而它們的運算量完全相同。這里，我們只討論DFT正變換的運算問題。一般來說，x(n)、 和X(k)均為復數(shù)，則每計算一個X(k)值，都需要進行N次復數(shù)乘法（x(n)與 相乘）以及N-1次復數(shù)加法。而X(k)共有N個點（k=0N-1），所以實現(xiàn)整個DFT運算需要進行N 2次復數(shù)乘法和N(N-1)次復數(shù)加法。由此可見，直接計算DFT時，其乘法次數(shù)和加法次數(shù)都與N

32、2成正比，當N很大時，其運算量是很可觀的，例如當N=1024時，DFT所需的復數(shù)乘法為1048576次，即一百多萬次，這對于實時性很強的信號處理來說，對計算速度的要求是太高了。因而我們需要改進DFT的計算方法，以便減少其運算量。通過觀察，我們發(fā)現(xiàn)通過利用系數(shù)所固有的周期性、對稱性等特性，可以將長序列的DFT分解為短序列的DFT，這樣就可以大大減少DFT的運算量。正是基于這種基本思路而形成了快速傅里葉變換算法（Fast Fourier Transform，縮寫為FFT），這種算法基本上可分為兩大類：按時間抽取法（Decimation-In-Time，縮寫為DIT）和按頻率抽取法（Decimati

33、on-In-Frequency，縮寫為DIF）。注意：快速傅里葉變換（FFT）并不是一種新的變換，而是離散傅里葉變換（DFT）的一種快速算法。二、 按時間抽?。―IT）的基-2FFT算法（庫利-圖基算法）1. 算法的原理先假設(shè)序列x(n)的長度N=2M（M為整數(shù)）。如果不滿足這個條件，可以人為地在序列末尾補上若干個零值點，使其達到這一要求。這種N為2的整數(shù)冪的FFT也稱基-2FFT。將長度為N=2M的序列按n的奇偶分為兩組，即令n=2r和n=2r+1（r =0, 1, , N/2-1），則x(n)的DFT可表示為 式中，X1(k)、X2(k)分別是x1(r)、x2(r)（r, k =0, 1,

34、 , N/2-1）的N/2點DFT，即 由于x1(r)、x2(r)、X1(k)、X2(k)均為N/2點的序列，而x(n)、X(k)為N點的序列，則由（3.4.1）式可見，一個N點DFT可分解成兩個N/2點的DFT，且這只是X(k)前半部分的結(jié)果（k =0, 1, , N/2-1），所以我們還應(yīng)計算X(k)后半部分的結(jié)果（k = N/2, , N-1），即 （3.4.3）由（3.4.2）式和系數(shù)的周期性，即，可得 （3.4.4）同理，可得 （3.4.5）又由于系數(shù)，則 （3.4.6）將（3.4.4）、（3.4.5）、（3.4.6）式代入（3.4.3）式中，可得 （3.4.7）綜上所述，（3.4.

35、1）式和（3.4.7）式分別是X(k)前半部分和后半部分的運算表達式。顯然，只要求出k =0 N/2-1范圍內(nèi)的X1(k)和X2(k)值，就可以求出k =0 N范圍內(nèi)的所有X(k)值，這就大大節(jié)省了運算。（3.4.1）式和（3.4.7）式的運算可用如圖所示的蝶形信號流圖來表示。注意：當支路上沒有標出系數(shù)時，則該支路的傳輸系數(shù)為1。 如果采用這種蝶形圖來表示上述分解過程，如圖所示，對于N=23=8的情形，其中輸出值X(0) X(3)是由（3.4.1）式給出的，而X(4) X(7)是由（3.4.7）式給出的。（將一個N點DFT分解為兩個N/2點DFT）由于N=2M，則N/2仍是偶數(shù)。因此，我們可以

36、仿照上面的做法，進一步將每個N/2點子序列再按奇偶部分分解成兩個N/4點的子序列。類似地有，X1(k)前半、后半部分的運算式分別為其中同理，X2(k)前半、后半部分的運算式分別為其中我們將系數(shù)統(tǒng)一為，則一個N=8點DFT就可以分解為四個N/4=2點DFT（無需再分解），如圖所示。（將一個N點DFT分解為四個N/4點DFT）由此可見，這種方法的每一步分解都是按輸入序列在時間上的奇偶次序來分解為兩個更短的子序列，所以稱為“時間抽取算法”。上述N=8點時間抽取法FFT的流圖如下所示。2. 運算量由上圖可見，當N=2M時，共有M級（列）蝶形，每級都由N/2個蝶形運算組成，而每個蝶形運算都需要一次復數(shù)乘

37、法和兩次復數(shù)加法，因此每級運算都需N/2次復乘和N次復加，這樣M級運算總共需要 復乘次數(shù) 復加次數(shù) 由于計算機上乘法運算所需時間比加法運算所需時間要多得多，所以以乘法為例來比較FFT算法與直接DFT算法的運算量。由FFT算法、直接DFT算法的運算量與點數(shù)N的關(guān)系曲線圖（P90圖3.4.5）可以直觀地看出FFT算法的優(yōu)越性，尤其是當點數(shù)N越大時，F(xiàn)FT的優(yōu)點更突出，如圖所示。3. 算法的特點 由上面介紹的N=8點時間抽取法FFT流圖（P89圖3.4.4），我們可以總結(jié)出N=2M點的時間抽取法的運算規(guī)律和特點。（1） 蝶形運算由8點FFT流圖可見，F(xiàn)FT運算中的每一級（列）計算都是由N/2個蝶形運

38、算組成，而N=2M時，共有M級（列）蝶形，因此N點FFT運算共需要N/2·M個蝶形運算來完成。其中，每個蝶形結(jié)構(gòu)完成如下基本的迭代運算： （3.4.8）式中，m表示第m級（列）迭代，k，j為數(shù)據(jù)所在行數(shù)。其一般形式如圖所示，它包括一次復乘和兩次復加。 在8點FFT流圖中，第一級（列）每個蝶形的兩節(jié)點間距為1=20，第二級每個蝶形的兩節(jié)點間距為2=21，第三級每個蝶形的兩節(jié)點間距為4=22，由此類推得，對于N=2M點FFT運算，其第m級每個蝶形的兩節(jié)點間距為2m-1。由于對第m級運算，每個蝶形的兩節(jié)點k，j間的距離為2m-1，則（3.4.8）式可改寫為 （3.4.9）現(xiàn)在的問題是如何確

39、定中的r。這里我們只給出結(jié)論，而省略了其數(shù)學推導過程。r的求解方法為（可省略）：將（3.4.9）式中，蝶形運算兩節(jié)點中的第一個節(jié)點標號值k，表示成M位（注意：N=2M）二進制數(shù)；將此M位二進制數(shù)左移M-m位（注意：m是第m級的運算），右邊空出的位置補零，即將此二進制數(shù)乘以2M-m=N/2m，其結(jié)果即為所求r對應(yīng)的二進制數(shù)。另外，由推導過程可知，每一級（列）不同的因子分布情況為：因此我們不難總結(jié)出因子分布的一般規(guī)律為：（2） 同址運算 由8點FFT流圖可以看出，某一級的任何兩節(jié)點k，j的節(jié)點變量在完成蝶形運算后，得到的結(jié)果為下一級k，j兩節(jié)點的節(jié)點變量，而與其他節(jié)點變量無關(guān)。因而，我們在計算機編

40、程時，可以利用這一特點，將蝶形的兩個輸出值仍放回到兩個輸入所在的存儲器中，這種運算就稱為“同址運算”。FFT的這種同址運算結(jié)構(gòu)可以節(jié)省存儲單元，降低設(shè)備成本，具有很大的實際意義。（3） 倒位序規(guī)律及實現(xiàn)I. 倒位序的規(guī)律由8點FFT流圖可見，按同址運算時，F(xiàn)FT的輸出X(k)是按自然順序X(0), X(1), , X(7)排列在存儲單元中，但是其輸入x(n)卻不是按自然順序存儲的，而是按x(0), x(4), x(2), x(6) , x(1), x(5) , x(3), x(7)的順序排列的，這種順序看似混亂無序，但實際上是有規(guī)律的，我們將其稱為“倒位序”。以N=8為例，如果將輸入x(n)

41、中變量n用二進制數(shù)表示為(n2, n1, n0)2（當N=8=23時，二進制為三位）。第一次分組時，n為偶數(shù)出現(xiàn)在上半部分，n為奇數(shù)出現(xiàn)在下半部分，通過觀察n的二進制數(shù)的最低位n0可知，n0=0則序列值對應(yīng)于偶數(shù)采樣值（n為偶） x(0), x(2), x(4), x(6) ，n0=1則序列值對應(yīng)于奇數(shù)采樣值（n為奇） x(1), x(3), x(5), x(7)。下一次分組時，不論原來的子序列是奇序列還是偶序列，則根據(jù)次低位n1的0, 1來分奇偶。這種不斷分成奇、偶子序列的過程可用如圖所示的二進制樹狀圖來描述。由此可見，倒位序的原因是輸入x(n)按時域變量n的奇偶不斷進行分組而造成的。II.

42、 倒位序的實現(xiàn)一般在實際運算中，我們總是先按自然順序?qū)⑤斎胄蛄写嫒氪鎯卧校偻ㄟ^變址運算來實現(xiàn)倒位序的排列。其具體方法如下：如果輸入序列x(n)的序號n用二進制數(shù)（例如n2 n1 n0）表示，則其倒位序二進制數(shù)就是（n0 n1 n2）。下表所示的是N=8時的自然順序二進制數(shù)以及相應(yīng)的倒位序二進制數(shù)對照表。自然順序n自然順序二進制數(shù)倒位序二進制數(shù)倒位序順序0000000010011004201001023011110641000011510110156110011371111117例如，對n=3而言，在原來存放x(011)的單元中，倒序后應(yīng)存入x(110)。由此可知，只要在原來存放自然順序序

43、列x(n)的單元中，存入倒位序序列x()，即可實現(xiàn)倒位序的排列。這個變址過程如圖所示。由圖可見，當n=時，不必調(diào)換；只有當n時，才需要將原來存放x(n)和x()的存儲單元中的內(nèi)容互換。為了節(jié)省調(diào)換時間，避免重復調(diào)換（保證只調(diào)換一次，否則又回到原狀），我們只需檢查n和的相對大小，若n>，則表明此x(n)在前面已經(jīng)和x()調(diào)換過了，不必再調(diào)換；否則，就必須進行互換。綜上所述，實現(xiàn)倒位序排列的具體方法為：若n時，不必調(diào)換；若n<時，就必須將原來存放x(n)和x()的存儲單元中的內(nèi)容互換。這樣就可以得到按時間抽取的同址運算所需要的倒位序排列。三、 按頻率抽?。―IF）的基-2FFT算法（桑

44、德-圖基算法）前面討論的FFT算法是將輸入序列x(n)按時間變量n的奇偶分解為越來越短的序列。類似地，如果我們將輸出序列X(k)按頻域變量k的奇偶分解為越來越短的序列，這種FFT算法就稱為“頻域抽取法”。1. 算法的原理假設(shè)輸入序列x(n)的長度N=2M（M為整數(shù)）。在把輸出序列X(k)（其長度也為N）按k的奇偶分組之前，先將輸入序列x(n)按n的順序分成前后兩半（注意：這并不是頻率抽?。?，即 再按k的奇偶將X(k)分為兩部分，分別令k=2r和k=2r+1（r =0, 1, , N/2-1），則 （3.4.10） （3.4.11）對于（3.4.10）、（3.4.11）式分別令 （3.4.12）

45、則 （3.4.13）其中，（3.4.12）式可以用如下所示的蝶形運算流圖來表示。則由（3.4.13）式，我們就可將一個N點DFT按k的奇偶分解成兩個點N/2的DFT，如圖所示（N=8）。與時間抽取法類似，由于N=2M，則N/2仍是偶數(shù)。因此，我們可以仿照上面的做法，將每個N/2點DFT的輸出再按k的奇偶進一步分解成兩個N/4點的DFT，其分解過程如圖所示（N=8）。這樣，一直進行到第M次分解（N=2M），此時實際上是做N/2個兩點DFT（注意：這些兩點DFT只是進行加減運算，但為了統(tǒng)一運算結(jié)構(gòu)，我們采用系數(shù)為的蝶形運算來表示），其結(jié)果就是x(n) 的N點DFT結(jié)果X(k)。則N=8點的完整的頻

46、率抽取法FFT流圖如圖所示。2. 算法的特點由8點頻率抽取FFT流圖可見，與時間抽取法類似， FFT運算中的每一級（列）計算都是由N/2個蝶形運算組成，而N=2M時，共有M級（列）蝶形，因此N點FFT運算共需要N/2·M個蝶形運算來完成。其中，每個蝶形結(jié)構(gòu)完成如下基本的迭代運算： （3.4.14）式中，m表示第m級（列）迭代，k，j為數(shù)據(jù)所在行數(shù)。其蝶形運算圖如圖所示，它也是由一次復乘和兩次復加組成，且同樣進行原址運算。 在N=8=23點頻率抽取FFT流圖中，第一級（列）每個蝶形的兩節(jié)點間距為4=N/21，第二級各蝶形的兩節(jié)點間距為2= N/22，第三級各蝶形的兩節(jié)點間距為1= N/

47、23，由此類推得，對于N=2M點FFT運算，其第m級每個蝶形的兩節(jié)點間距為N/2m=2M-m（這里不予證明）。對第m級中各蝶形運算的兩節(jié)點k，j間的距離為N/2m，則（3.4.14）式可改寫為 （3.4.15）現(xiàn)在的問題是如何確定中的r。這里我們只給出結(jié)論，而省略了其數(shù)學推導過程。r的求解方法為（可省略）：將（3.4.15）式中，蝶形運算兩節(jié)點中的第一個節(jié)點標號值k，表示成M位二進制數(shù)；將此M位二進制數(shù)左移m-1位，右邊空出的位置補零，即將此二進制數(shù)乘以2m-1，其結(jié)果即為所求r對應(yīng)的二進制數(shù)。另外，由推導過程可知，每一級（列）不同的因子分布情況為：因此我們不難總結(jié)出因子分布的一般規(guī)律為：3.

48、 DIF（頻率抽取法）與DIT（時間抽取法）的異同及其關(guān)系（1） DIF法與DIT法的異同：注意：盡管DIF輸入是自然順序，輸出是倒位序的，與DIT恰好相反，但實際上DIT、DIF的輸入或輸出都可重排成自然順序或倒位序的，因此這一點并非是二者的本質(zhì)區(qū)別。不同點：DIT與DIF的基本蝶形圖不同，DIF的復數(shù)乘法出現(xiàn)在減法之后，DIT的復數(shù)乘法出現(xiàn)在減法之前（實質(zhì)區(qū)別）；相同點：DIT與DIF的運算量是相同的，即都有M級運算，每級運算都需要由N/2個蝶形運算來完成，因此總共需要 復乘次數(shù) 復加次數(shù) ；DIT與DIF都可以進行同址運算；DIT與DIF都可以按倒位序規(guī)律排列；（2） DIF法與DIT法

49、的關(guān)系它們的基本蝶形是互為轉(zhuǎn)置的。四、 IDFT的快速算法（IFFT）上述的FFT算法同樣可適用于離散傅里葉反變換（IDFT）運算，即求解快速傅里葉反變換（IFFT）。而利用FFT算法來計算IFFT的具體方法有以下兩種：1. 方法一 首先，比較IDFT公式和DFT 公式可見，只要將DFT運算中的每一個系數(shù)換成，最后再乘以常數(shù)1/N，則前面所介紹的按時間或按頻率抽取的FFT算法都可用來計算IDFT。輸入X(k)順序排列輸出x(n)倒序排列例如，我們可直接由8點頻率抽取FFT流圖出發(fā)，把換成，并在每級（列）運算中都乘以1/2（注意：因為乘以1/N就等效于1/N =1/2M=(1/2)M，所以相當于

50、每級都乘以1/2），這樣即可得到相應(yīng)的IFFT流圖，如圖所示。 這種IFFT算法雖然簡單，但需要對FFT程序和參數(shù)稍加改動才能實現(xiàn)。下面介紹一種完全不必改變FFT程序就可以計算IFFT的方法。2. 方法二首先，對IDFT公式取共軛，得然后對上式兩邊再取共軛，得由此可見，只要先將X(k)取共軛，就可以直接利用FFT運算，最后將運算結(jié)果再取共軛，并乘以1/N，即可得到x(n)值。這樣，F(xiàn)FT運算和IFFT運算可以共用一個子程序，便于編程實現(xiàn)。習題：3.14, 3.15, 3.16思考題：P103 3.21, 3.23, 3.35五、 線性調(diào)頻Z變換算法（CZT）（可略，參見教材P99-101）前面

51、曾經(jīng)講過，DFT實質(zhì)上是對有限長序列的Z變換在單位圓上的等間隔采樣，但在實際應(yīng)用中，我們通常只對信號的某一頻段感興趣，即只需要計算單位圓上某一段的頻譜值（例如，窄帶信號的處理）；其次，有時我們也對非單位圓上的采樣感興趣（例如，語音信號的處理）；再次，若序列的長度N是個較大的素數(shù)，無法分解時，該如何有效計算其DFT。從以上三方面考慮，就有必要采用沿螺線對Z變換進行采樣，且同時可用FFT實現(xiàn)快速計算，這種變換稱為線性調(diào)頻Z變換（CZT）。它是適用于更為一般情況下的由x(n)求X(zk)的一種快速變換算法。1. 算法的原理設(shè)有限長序列x(n)（0nN-1）的Z變換為 （3.4.16）現(xiàn)在我們對z平面

52、上的一段螺線作等分角采樣，如圖所示其采樣點zk可表示為 （3.4.17）式中，M采樣點數(shù)（注意： M不一定等于序列的長度N）；A采樣軌跡的起始位置，即（其中A0為半徑，0為幅角）；W復參數(shù)，即其中W0為螺線的伸展率，當W0>1時，隨著的增大，螺線趨向圓內(nèi)（內(nèi)旋）；0為螺線采樣點之間的等分角，由于0可以是任意的，則減小0，就能提高頻率分辨率，這對分析具有任意起始頻率的高分辨率窄帶頻譜具有重要意義；將（3.4.17）式代入（3.4.16）式中，可得給定路徑zk的Z變換為 （3.4.18）可見，該公式與直接計算DFT相似，當N，M很大時，其計算量也很大，因此我們可采用等式 （3.4.19）將（3.4.18）式的運算轉(zhuǎn)換成卷積和形式，以便FFT算法來提高運算速度。將（3.4.19）式代入（3.4.18）式中，得令 則 （3.4.20）顯然，X(zk)是通過兩個有限長序列的線性卷積而得到的，其運算過程如圖所示。2. 算法的實現(xiàn)我們可以通過循