第3章1-4 離散傅里葉變換及其快速算法

第三章離散傅里葉變換及其快速算法DiscreteFourierTransformandFastAlgorithm本章習(xí)題（第三版課本P155）3.4，3.6(2)(4)，3.8，3.10

3.13，3.14，3.16，3.18，3.20選做：3.28內(nèi)容提要離散傅里葉變換(DiscreteFourierTransform，DFT)是時間函數(shù)是離散的，而且頻譜函數(shù)也是離散的變換。3.1討論周期序列的傅里葉級數(shù)及其性質(zhì)。3.2導(dǎo)出有限長序列的傅里葉表示——離散傅里葉變換，并較詳細地介紹了離散傅里葉變換的基本性質(zhì)，其中包括循環(huán)卷積的重要概念。3.3介紹利用循環(huán)卷積計算線性卷積的方法。3.4討論頻率取樣理論。3.5以較大篇幅介紹本章的重點內(nèi)容——快速傅里葉變換的時間抽選算法和頻率抽選算法及一些細節(jié)上的考慮。3.6介紹變換點數(shù)為合數(shù)時的快速傅里葉變換算法。3.7介紹快速傅里葉變換算法的應(yīng)用實例。3.8介紹線性調(diào)頻Z變換。（參考）傅里葉變換的各種形式連續(xù)時間、離散頻率的傅里葉變換 對于周期為T的連續(xù)時間信號，可以采用傅里葉級數(shù)展開：連續(xù)時間、連續(xù)頻率的傅里葉變換 對于非周期的連續(xù)時間信號，可以進行傅里葉變換：它在時域和頻域都是連續(xù)的。離散時間、連續(xù)頻率的傅里葉變換 對于非周期的序列，其傅里葉變換在頻域是以2π為周期的連續(xù)函數(shù)。3.1.1

離散傅里葉級數(shù)(DFS)定義

一個周期為N的周期序列可表示為：這樣的周期序列的Z變換是不收斂的。如果用離散傅里葉級數(shù)表示，則可以討論其收斂性。用傅里葉級數(shù)表示，其基波頻率為：用復(fù)指數(shù)表示：第k次諧波為：由于是周期序列，且k次諧波也是周期為N的序列：3.1離散傅里葉級數(shù)及其性質(zhì)因此，對于離散傅里葉級數(shù)，只取下標(biāo)從0到N-1的N個諧波分量就足以表示原來的信號。這樣可把離散傅里葉級數(shù)表示為式中，乘以系數(shù)1/N是為了下面計算的方便；為k次諧波的系數(shù)。將上式兩邊同乘以并從n=0到N-1求和，得到：由復(fù)指數(shù)序列的正交性：所以，得到周期序列的離散傅里葉級數(shù)表達式：令則得到周期序列的離散傅里葉級數(shù)(DFS)變換對n和k均為離散變量。如果將n當(dāng)作時間變量，k當(dāng)作頻率變量，則第一式表示的是時域到頻域的變換，稱為DFS的正變換。第二式表示的是頻域到時域的變換，稱為DFS的反變換。由于故是周期為N的離散周期信號。周期序列的信息可以用它在一個周期中的N個值來代表。1.線性設(shè)周期序列和的周期都為N，且若則有2．周期序列的移位設(shè)則如果m>N，則m=m1+Nm23.1.2離散傅里葉級數(shù)的性質(zhì)3．周期卷積設(shè)和都是周期為N的周期序列，它們的DFS系數(shù)分別為令則上式表示的是兩個周期序列的卷積，稱為周期卷積。周期為N的兩個序列的周期卷積的離散傅里葉級數(shù)等于它們各自離散傅里葉級數(shù)的乘積。周期卷積的計算：周期卷積中的序列和對m都是周期為N的周期序列，它們的乘積對m也是以N為周期的，周期卷積僅在一個周期內(nèi)求和。相乘和相加運算僅在m=0到N-1的區(qū)間內(nèi)進行。計算出n=0到N-1(一個周期)的結(jié)果后，再將其進行周期延拓，就得到周期卷積。周期卷積滿足交換律兩個周期序列的乘積的DFS為：離散傅里葉級數(shù)性質(zhì)匯總3.2離散傅里葉變換及其性質(zhì)3.2.1離散傅里葉變換(DFT)有限長序列的傅里葉變換稱為離散傅里葉變換，簡寫為DFT。DFT可以按3個步驟由DFS推導(dǎo)出來：①將有限長序列延拓成周期序列；②求周期序列的DFS；③從DFS中取出一個周期便得到有限長序列的DFT。將x(n)延拓成周期為N的周期序列如上圖所示。顯然有的第一個周期，即n＝0到N-1的序列稱為主值序列，n=0到N-1的范圍稱為主值區(qū)間。上述兩式可分別表示為其中RN(n)是矩形序列。符號((n))N表示n對模N的余數(shù)，即這里k是商。同理，可以認為周期序列的DFS系數(shù)是有限長序列X(k)周期延拓的結(jié)果，而X(k)是的主值序列。即由此便可以得出有限長序列的離散傅里葉變換(DFT)的表示式為由此可見，有限長序列x(n)的DFT即X(k)仍是有限長序列。在一般情況下，X(k)是一個復(fù)量，可表示為或式中例3.1

求有限長序列的DFT，其中a=0.8，N=8。解：因此得X(0)=4.16114

X(1)=0.71063-j0.92558X(2)=0.50746-j0.40597

X(3)=0.47017-j0.16987X(4)=0.46235

X(5)=

0.47017+j0.16987

X(6)=

0.50746+j0.40597

X(7)=

0.71063+j0.92558Matlab實現(xiàn)fft1.m將x(n)的Z變換與x(n)的DFT進行對比，可以看出式中，表示z平面單位圓上輻角(k=0,1,…N-1)的N個等間隔點。Z變換在這些點上的取樣值就是X(k)。在圖3.4(b)中的虛線包絡(luò)是單位圓(z=ejω)上的Z變換，即傅里葉變化X(ejω)。關(guān)于離散傅里葉變換(DFT)：序列x(n)在時域是有限長的(長度為N)，它的離散傅里葉變換X(k)也是離散、有限長的(長度也為N)。n為時域變量，k為頻域變量。離散傅里葉變換與離散傅里葉級數(shù)沒有本質(zhì)區(qū)別，DFT實際上是離散傅里葉級數(shù)的主值，DFT也隱含有周期性。離散傅里葉變換(DFT)具有唯一性。DFT的物理意義：序列x(n)的Z變換在單位圓上的等角距取樣。DFT隱含著周期性，因此在討論DFT的性質(zhì)時，常與DFS的概念聯(lián)系起來，并把有限長序列看作周期序列的一個周期來處理。設(shè)x1(n)和x2(n)的長度都為N，且它們對應(yīng)的DFT分別為X1(k)和X2(k)。1．線性

設(shè)x3(n)=ax1(n)+bx2(n)，a和b都為常數(shù)，則若它們長度不等，取長度最大者，將短的序列通過補零加長，注意此時DFT與未補零的DFT不相等。此性質(zhì)可以直接由DFT的定義進行證明。3.2.2離散傅里葉變換的性質(zhì)2．對稱性

最常遇到的是實序列。設(shè)x(n)是一個長度為N的實序列，且DFT[x(n)]=X(k)，則有這意味著或這就是說，實序列的DFT系數(shù)X(k)的模是偶對稱序列，輻角是奇對稱序列。對于復(fù)序列也有相應(yīng)的共軛對稱性。3．序列的循環(huán)移位

一個長度為N的序列x(n)的循環(huán)移位定義為循環(huán)移位分3步計算：(1)將x(n)延拓成周期為N的周期序列；

(2)將移位得或x((n+m))N；(3)對x((n+m))N取主值得x((n+m))N·RN(n)。這個過程如下圖所示。從圖中兩虛線之間的主值序列的移位情況可以看出，當(dāng)主值序列左移m個樣本時，從右邊會同時移進m個樣本，而且好像是剛向左邊移出的那些樣本又從右邊循環(huán)移了進來。因此取名“循環(huán)移位”。顯然，循環(huán)移位不同于線性移位序列循環(huán)移位后的DFT為證明：由周期序列的移位性質(zhì)得因x((n+m))N·RN(n)是的主值序列，所以它的DFT就是的主值，即根據(jù)時域和頻域的對偶關(guān)系，可以得出若則4．循環(huán)卷積

設(shè)Y(k)=Xl(k)·X2(k)，則或由上式表示的卷積稱為循環(huán)卷積，常記為證明：利用DFT的隱含周期性，將Y(k)周期延拓計算后再取主值m取值的0~N-1范圍是主值區(qū)間，故因此循環(huán)卷積的計算是對序列按循環(huán)移位后求對應(yīng)項的乘積之和，實際上就是周期卷積取主值。循環(huán)卷積的計算可用圖3.6來說明。在圖3.6(a)中，x1(n)的N個值按順時針方向均勻分布在內(nèi)圓周上，x2(n)的N個值按反時針方向均勻分布在外圓周上，把內(nèi)外圓周上對應(yīng)的數(shù)值兩兩相乘，然后把乘積相加就得到y(tǒng)(0)。若將外圓周順時針方向轉(zhuǎn)動一格(如圖3.6(b)所示)，將內(nèi)外圓周上對應(yīng)的數(shù)值兩兩相乘并把乘積相加，便得到y(tǒng)(1)。依次類推，可以得出y(n)的其它值。因此循環(huán)卷積也叫做圓卷積。圖3.7表示的是序列x1(n)和x2(n)的4點(即N=4)循環(huán)卷積的計算過程。圖中，x1(n)=δ(n)+δ(n-1)+δ(n-2)，x2(n)＝δ(n)+1.5δ(n-1)+2δ(n-2)+2.5δ(n-3)。這一計算過程分5步：(1)周期延拓(2)折疊(3)移位和取主值(4)相乘(5)相加考慮到DFT關(guān)系的對偶性，可以證明，長為N的兩序列之積的DFT等于它們的DFT的循環(huán)卷積除以N，即3種卷積：線性卷積線性卷積不受主值區(qū)間限制周期卷積循環(huán)卷積是周期卷積取主值，在一定條件下與線性卷積相等。兩個長度都為N的因果序列的循環(huán)卷積仍是一個長度為N的序列，而它們的線性卷積卻是一個長度為2N-1的序列。3.3

利用循環(huán)卷積計算線性卷積如果能將線性卷積．轉(zhuǎn)化成循環(huán)卷積，那么根據(jù)DFT的循環(huán)卷積性質(zhì)，就能夠用循環(huán)卷積來計算線性卷積，而循環(huán)卷積可以用FFT進行快速計算。因此，首先需要討論在什么條件下，循環(huán)卷積與線性卷積相等的問題。在許多實際問題中常需要計算線性卷積，例如一個FIR數(shù)字濾波器的輸出等于輸入與濾波器的單位取樣響應(yīng)的線性卷積。設(shè)x1(n)和x2(n)都是長度為N的有限長因果序列，它們的線性卷積為它是長為2N-1的序列。現(xiàn)將x1(n)和x2(n)延長至L(L>N)，延長部分(從N到L-1)均填充為零值，計算x1(n)和x2(n)的L點循環(huán)卷積，得到為了下面分析方便，先將x1(n)和x2(n)以L為周期進行延拓，得到兩個周期序列和它們的周期卷積為注意到在區(qū)間0≤m≤L-1中，x1((m))L=x1(m)；并交換求和次序得上式表明，x1(n)和x2(n)的周期卷積是它們的線性卷積的周期延拓。對周期卷積取主值，得到循環(huán)卷積因此，x1(n)和x2(n)的循環(huán)卷積可被看作是它們的線性卷積的周期延拓的主值。那么，如何確定延拓的周期L呢？因為兩個長度為N的序列的線性卷積是一個長度為2N-1的序列，所以(1)如果L<2N-1，則x3(n)的周期延拓必有一部分非零值序列相重疊，從而產(chǎn)生混疊失真，這時L點的循環(huán)卷積不等于N點的線性卷積。(2)如果L≥2N-1，則x3(n)的周期延拓不會產(chǎn)生混疊失真，這時由此得出結(jié)論：兩個長度為N的序列的線性卷積可用長度為L的循環(huán)卷積來代替，但L必須滿足條件L≥2N-1。這時N到L之間的值用零填充。如果x1(n)和x2(n)的長度分別為N和M，則L應(yīng)滿足條件L≥M+N-1。這意味著，對于時間有限信號，可以像頻帶有限信號進行時域采樣而不丟失任何信息一樣，可以在頻域上進行采樣而不丟失任何信息。這正是傅里葉變換中時域和頻域?qū)ε缄P(guān)系的反映，這有著十分重要的意義。DFT實現(xiàn)了頻域離散化，開辟了在頻域采用數(shù)字技術(shù)處理的新領(lǐng)域。這使我們自然想到，對于任意一個頻率特性，是否均能用頻域采樣的辦法來逼近，這是一個很吸引人的問題，因為用頻率采樣來逼近，可使問題大大簡化。因此我們要討論頻率采樣的可行性以及所帶來的誤差。3.4頻率取樣頻率取樣是指對序列的傅里葉變換或系統(tǒng)的頻率特性進行取樣。本節(jié)討論在什么條件下能夠用得到的頻譜取樣值無失真地恢復(fù)原信號或系統(tǒng)。設(shè)任意長序列x(n)絕對可和，其Z變換表示為如果在單位圓上對X(z)進行等角距取樣，取樣點數(shù)為M，則得根據(jù)DFT的定義，對X(k)求反變換得根據(jù)上面兩式可得：因為所以上式表明，在z平面的單位圓上對序列的Z變換進行等角距取樣，將導(dǎo)致時間序列的周期延拓。這一結(jié)果與對連續(xù)時間信號取樣導(dǎo)致頻譜周期延拓類似?，F(xiàn)在我們來考察xp(n)與原序列x(n)的關(guān)系，看它如何才能代表原序列x(n)。xp(n)是原非周期信號x(n)的周期延拓序列，因此xp(n)是一個周期序列，其主值為在x(n)為有限長度N的情況下，如