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

1、Discrete Fourier Transform and Fast Algorithm本章習題（ 第三版課本P155）3.4，3.6(2)(4)，3.8，3.103.13，3.14，3.16，3.18，3.20選做：3.28離散傅里葉變換 (Discrete Fourier Transform，DFT)是時間函數(shù)是離散的，而且頻譜函數(shù)也是離散的變換。3. 1 討論周期序列的 傅里葉級數(shù)及其性質(zhì)。3. 2 導出有限長序列的傅里葉表示離散傅里葉變換，并較詳細地 介紹了離散傅里葉變換的基本性質(zhì)，其中包括循環(huán)卷積的重要概念。3. 3 介紹利用循環(huán)卷積 計算線性卷積的方法。3. 4 討論頻率取樣理論

2、。3. 5 以較大篇幅介紹本章的重點內(nèi)容 快速傅里葉變換的時間抽選算法和頻率抽選算法及一些細節(jié)上的考慮。3. 6 介紹變換點數(shù) 為合數(shù)時的快速傅里葉變換算法。3. 7 介紹快速傅里葉變換算法的應用實例。3. 8 介紹線性調(diào)頻Z變換。（參考） 連續(xù)時間、離散頻率的傅里葉變換對于周期為T的連續(xù)時間信號，可以采用傅里葉級數(shù)展開：連續(xù)時間、連續(xù)頻率的傅里葉變換對于非周期的連續(xù)時間信號，可以進行傅里葉變換：它在時域和頻域都是連續(xù)的。離散時間、連續(xù)頻率的傅里葉變換對于非周期的序列，其傅里葉變換在頻域是以2為周期的連續(xù)函數(shù)。3. 1. 1 離散傅里葉級數(shù)離散傅里葉級數(shù)(DFS)定義定義 一個周期為N的周期序

3、列可表示為：這樣的周期序列的Z變換是不收斂的。如果用離散傅里葉級數(shù)表示，則可以討論其收斂性。用傅里葉級數(shù)表示，其基波頻率為：用復指數(shù)表示：第k次諧波為：由于是周期序列，且k次諧波也是周期為N的序列：因此，對于離散傅里葉級數(shù)，只取下標從0到N-1的N個諧波分量就足以表 示原來的信號。這樣可把離散傅里葉級數(shù)表示為 式中，乘以系數(shù)1/N是為了下面計算的方便； 為k次諧波的系數(shù)。將上式兩邊同乘以并從n=0到N-1求和，得到：由復指數(shù)序列的正交性：所以，得到周期序列的離散傅里葉級數(shù)表達式：令則得到周期序列的離散傅里葉級數(shù)(DFS)變換對n和k均為離散變量。如果將n當作時間變量，k當作頻率變量，則第一式表

4、示的是時域到頻域的變換，稱為DFS的正變換。第二式表示的是頻域到時域的變換，稱為DFS的反變換。由于故 是周期為N的離散周期信號。周期序列的信息可以用它在一個周期中的N個值來代表。設周期序列 和 的周期都為N，且若則有設則如果mN，則m=m1+Nm23.1.2 離散傅里葉級數(shù)的性質(zhì)設和都是周期為N的周期序列，它們的DFS系數(shù)分別為令則上式表示的是兩個周期序列的卷積，稱為周期卷積。周期為N的兩個序列的周期卷積的離散傅里葉級數(shù)等于它們各自離散傅里葉級數(shù)的乘積。周期卷積的計算：周期卷積中的序列 和 對m都是周期為N的周期序列，它們的乘積對m也是以N為周期的，周期卷積僅在 一個周期內(nèi)求和。 相乘和相加

5、運 算僅在m=0到N-1的區(qū)間內(nèi)進行。計算出n=0到N-1(一個周期)的結果后，再將其進行周期延拓，就得到周期卷積 。 周期卷積滿足交換律兩個周期序列的乘積 的DFS為：有限長序列的傅里葉變換稱為離散傅里葉變換，簡寫為DFT。DFT可以按3個步驟由 DFS推導出來：將有限長序列延拓成周期序列；求周期序列的DFS；從DFS中取出一個周期便得到有限長 序列的DFT。將x(n)延拓成周期為N的周期序列如上圖所示。顯然有的第一個周期，即n0到N-1的序列稱為主值序列，n=0到N-1的范圍稱為主值區(qū)間。上述兩式可分別表示為 其中RN(n)是矩形序列。符號(n)N表示n對模N的余數(shù)，即 這里k是商。 同理

6、，可以認為周期序列 的DFS系數(shù) 是有限長序列X(k)周期延拓的結果，而 X(k)是 的主值序列。即 由此便可以得出有限長序列的離散傅里葉變換(DFT)的表示式為由此可見，有限長序列x(n)的DFT即X(k)仍是有限長序列。在一般情況下，X(k)是一個復量，可表示為或式中例3. 1 求有限長序列的DFT，其中a=0.8，N=8。 解：因此得 X(0)=4.16114 X(1)=0.71063-j0.92558 X(2)=0.50746-j0.40597 X(3)=0.47017-j0.16987 X(4)=0.46235X(5)= 0.47017+j0.16987X(6)= 0.50746+j

7、0.40597X(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)中的虛線包絡是單位圓(z=ej)上的Z變換，即傅里葉變化X(ej)。序列序列x(n)在時域是有限長的在時域是有限長的(長度為長度為N)，它的離散傅里葉變，它的離散傅里葉變換換X(k)也是離散、有限長的也是離散、有限長的(長度也為長度也為N)。n為時域變量，為時域變量，k為頻域變量。為頻域變量。離散傅里葉變換與離散傅里葉級數(shù)沒有本質(zhì)區(qū)別，

8、離散傅里葉變換與離散傅里葉級數(shù)沒有本質(zhì)區(qū)別，DFT實實際上是離散傅里葉級數(shù)的主值，際上是離散傅里葉級數(shù)的主值，DFT也隱含有周期性。也隱含有周期性。離散傅里葉變換離散傅里葉變換(DFT)具有唯一性。具有唯一性。DFT的物理意義：序列的物理意義：序列x(n)的的Z變換在單位圓上的等角距取變換在單位圓上的等角距取樣。樣。 DFT隱含著周期性，因此在討論DFT的性質(zhì)時，常與DFS的概念聯(lián)系起來，并把有限長序列看作周期序列的一個周期來處理。設x1(n)和x2(n)的長度都為N，且它們對應的DFT分別為X1(k)和X2(k)。 設x3(n)=ax1(n)+bx2(n)，a和b都為常數(shù)，則 若它們長度不等

9、，取長度最大者，將短的序列通過補零加長，注意此時DFT與未補零的DFT不相等。 此性質(zhì)可以直接由DFT的定義進行證明。2對稱性對稱性 最常遇到的是實序列。設x(n)是一個長度為N的實序列，且DFTx(n)=X(k)，則有 這意味著或 這就是說，實序列的DFT系數(shù)X(k)的模是偶對稱序列，輻角是奇對稱序列。 對于復序列也有相應的共軛對稱性。 一個長度為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)NRN(n)。這個過程如下圖所示。 從圖中兩虛線之間的主值序列的移位情

10、況可以看出，當主值序列左移m個樣本時，從右邊會同時移進m個樣本，而且好像是剛向左邊移出的那些樣本又從右邊循環(huán)移了進來。因此取名“循環(huán)移位”。 顯然，循環(huán)移位不同于線性移位 序列循環(huán)移位后的DFT為 證明：由周期序列的移位性質(zhì)得因x(n+m)NRN(n)是 的主值序列，所以它的DFT就是的主值，即根據(jù)時域和頻域的對偶關系，可以得出若則 設Y(k)=Xl(k)X2(k)，則或由上式表示的卷積稱為循環(huán)卷積，常記為利用DFT的隱含周期性，將Y(k)周期延拓計算后再取主值m取值的0N-1范圍是主值區(qū)間，故因此循環(huán)卷積的計算是對序列按循環(huán)移位后求對應項的乘積之和，實際上就是周期卷積取主值。循環(huán)卷積的計算可

11、用圖3.6來說明。 在圖3.6(a)中，x1(n)的N個值按順時針方向均勻分布在內(nèi)圓周上，x2(n)的N個值按反時針方向均勻分布在外圓周上，把內(nèi)外圓周上對應的數(shù)值兩兩相乘，然后把乘積相加就得到y(tǒng)(0)。若將外圓周順時針方向轉動一格(如圖3.6(b)所示)，將內(nèi)外圓周上對應的數(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

12、)周期延拓 (2)折疊 (3)移位和取主值 (4)相乘 (5)相加考慮到DFT關系的對偶性，可以證明，長為N的兩序列之積的DFT等于它們的DFT的循環(huán)卷積除以N，即 3種卷積：線性卷積 線性卷積不受主值區(qū)間限制周期卷積循環(huán)卷積 是周期卷積取主值，在一定條件下與線性卷積相等。兩個長度都為N的因果序列的循環(huán)卷積仍是一個長度為N的序列，而它們的線性卷積卻是一個長度為2N-1的序列。 如果能將線性卷積轉化成循環(huán)卷積，那么根據(jù)DFT的循環(huán)卷積性質(zhì)，就能夠用循環(huán)卷積來計算線性卷積，而循環(huán)卷積可以用FFT 進行快速計算。因此，首先需要討論在什么條件下，循環(huán)卷積與線性 卷積相等的問題。 在許多實際問題中常需要

13、計算線性卷積，例如一個FIR數(shù)字濾波器的輸出等于輸入與濾波器的單位取樣響應的線性卷積。 設x1(n)和x2(n)都是長度為N的有限長因果序列，它們的線性卷積為它是長為2N-1的序列。 現(xiàn)將x1(n)和x2(n)延長至L(LN)，延長部分(從N到L-1)均填充為零值，計算x1(n)和x2(n)的L點循環(huán)卷積，得到 為了下面分析方便，先將x1(n)和x2(n)以L為周期進行延拓，得到兩個周期序列和它們的周期卷積為注意到在區(qū)間0mL-1中，x1(m)L=x1(m)；并交換求和次序得 上式表明，x1(n)和x2(n)的周期卷積是它們的線性卷積的周期延拓。對周期卷積取主值，得到循環(huán)卷積 因此，x1(n)

14、和x2(n)的循環(huán)卷積可被看作是它們的線性卷積的周期延拓的主值。那么，如何確定延拓的周期L呢？因為兩個長度為N的序列的線性卷積是一個長度為2N-1的序列，所以(1)如果L2N-1，則x3(n)的周期延拓必有一部分非零值序列相重疊，從而產(chǎn)生混疊失真，這時L點的循環(huán)卷積不等于N點的線性卷積。(2)如果L2N-1，則x3(n)的周期延拓不會產(chǎn)生混疊失真，這時由此得出結論：兩個長度為N的序列的線性卷積可用長度為L的循環(huán)卷積來代替，但L必須滿足條件 L2N-1。這時N到L之間的值用零填充。如果x1(n)和x2(n)的長度分別為N和M，則L應滿足條件LM+N-1。 這意味著，對于時間有限信號，可以像頻帶有

15、限信號進行時域采樣而不丟失任何信息一樣，可以在頻域上進行采 樣而不丟失任何信息。這正是傅里葉變換中時域和頻域對偶關系的反映，這有著十分重要的意 義。DFT實現(xiàn)了頻域離散化，開辟了在頻域采用數(shù)字技術處理的新領域。 這使我們自然想到，對于任意一個頻率特性，是否均能用頻域采樣的辦法來逼近，這是一個很吸引人的問題，因為用頻率采樣來逼近，可使問題大大簡化。因此我們要討論頻率采樣的可行性以及所帶來的誤差。 頻率取樣是指對序列的傅里葉變換或系統(tǒng)的頻率特性進行取樣 。本節(jié)討論在什么條件下能夠用得到的頻譜取樣值無失真地恢復原信號或系統(tǒng)。 設任意長序列x(n)絕對可和，其Z變換表示為如果在單位圓上對X(z)進行等

16、角距取樣，取樣點數(shù)為M，則得 根據(jù)DFT的定義，對X(k)求反變換得 根據(jù)上面兩式可得：因為所以 上式表明，在z平面的單位圓上對序列的Z變換進行等角距取樣，將導致時間序列的周期延拓。這一結果與對連續(xù)時間信號取樣導致頻譜周期延拓類似。 現(xiàn)在我們來考察xp(n)與原序列x(n)的關系，看它如何才能代表原序列x(n)。 xp(n)是原非周期信號x(n)的周期延拓序列，因此xp(n)是一個周期序列，其主值為 在x(n)為有限長度N的情況下，如果取樣點MN，那么x(n)周期延拓的結果不會產(chǎn)生混疊。這時，xp(n)的主值xN(n)與原序列x(n)一樣，因此xN(n)完全能代表原序列x(n)。 如果MN，即延拓的周期M小余有限序列的長度N，則x(n)周期延拓后一定產(chǎn)生混疊，因而xN(n)不能無失真地代表原信號x(n)。在x(n)為無限長的情況下，對Z變換取樣必然導致混疊失真，因此xN(n)不能代表原序列x(n)。（見下圖） 因此，對于長度為N的有限長序列，對Z變換取樣即頻率取樣不失真的條件，是取樣點數(shù) M應等于或大于原序列的長度N，即MN。在MN時，Z變換的取樣即DFT X(k)，利用IDFT公式可由X(k)恢復原序列x(n