第5章DFT與FFT5.1

DFT的定義及物理意義5.2離散傅里葉級數(shù)（DFS）與DFT5.3

DFT的性質(zhì)與定理5.4頻域采樣5.5基2時間抽取FFT算法5.6基2頻率抽取FFT算法5.7

IDFT的快速實現(xiàn)——IFFT算法5.8

MATLAB實現(xiàn)習(xí)題5.1DFT的定義及物理意義

5.1.1DFT的定義

設(shè)序列x(n)長度為M，則它的N點離散傅里葉正變換（DFT）和N點離散傅里葉逆變換（IDFT）分別定義為(5.1-1)0≤k≤N－1(5.1-2)0≤n≤N－1式中，，N為DFT變換區(qū)間長度，N≥M。通常稱式(5.1-1)和式(5.1-2)為離散傅里葉變換對。由DFT的定義可見，DFT使有限長時域離散序列與有限長頻域離散序列之間建立起了對應(yīng)關(guān)系，故可利用計算機完成兩者間的變換，這是DFT的最大優(yōu)點之一。5.1.2DFT的物理意義

設(shè)X(ejω)=DTFT［x(n)］,X(z)=Z［x(n)］,X(k)=DFT

［x(n)］N,則(5.1-3)(5.1-4)0≤k≤N－1(5.1-5)0≤k≤N－1

式(5.1-3)就是序列的Z變換與序列的傅里葉變換之間的關(guān)系，即單位圓上的Z變換就是序列的傅里葉變換。式(5.1-4)和式(5.1-5)指出了離散傅里葉變換(DFT)與離散時間序列的傅里葉變換(DTFT)以及序列的Z變換之間的關(guān)系，即序列x(n)的

N點DFT是對x(n)的頻譜X(ejω)在［0,2π］上的N點等間隔采樣，采樣間隔為2π/N，也就是對序列頻譜的離散化。這就是DFT的物理意義。既然離散傅里葉變換(DFT)就是對序列頻譜的N點等間隔采樣，那么當變換區(qū)間長度N變化時，所得的變換結(jié)果即DFT也是不同的。類似采樣定理，當N越大時采樣的譜線越密，

X(k)的包絡(luò)線就越逼近X(ejω)的幅頻特性曲線。5.2離散傅里葉級數(shù)（DFS）與DFT

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

我們知道，對于周期信號，通常都可以用傅里葉級數(shù)來描述。若連續(xù)時間周期信號為f(t)=f(t+mT)，

m為任意整數(shù)，則根據(jù)第1章的周期信號傅里葉級數(shù)展開公式，信號f(t)的指數(shù)形式傅里葉級數(shù)表示為(5.2-1)上式可以看成是信號f(t)被分解成不同頻率的各次諧波的疊加，每個諧波都有一個幅值|F(jnΩ)|，表示該諧波分量所占的比重。其中ejΩt為基波，基頻Ω=2π/T（T為信號周期）。同樣，現(xiàn)設(shè)是周期為N的周期序列，即r為任意整數(shù)因為周期序列不滿足絕對可和的條件，所以它的傅里葉變換和Z變換不存在。但是周期序列同連續(xù)時間周期信號一樣，可以用離散傅里葉級數(shù)表示。對于周期序列，用指數(shù)形式的傅里葉級數(shù)表示應(yīng)該為(5.2-2)式中，ω0=2π/N是基頻，ejω0n為基頻序列，ejkω0n

為k次諧波序列。雖然在表現(xiàn)形式上和連續(xù)周期函數(shù)是相同的，但是離散周期序列的傅里葉級數(shù)的諧波成分只有N個獨立成分，這與連續(xù)傅里葉級數(shù)的無窮多個諧波成分相比是不同的。為了說明這一點，下面來分析一下第k+rN（r為任意整數(shù)）次諧波ej(k+rN)ω0n

和第k次諧波ejkω0n之間的關(guān)系。因為r為任意整數(shù)這說明第k+rN次諧波能夠被第k次諧波代表，即復(fù)指數(shù)序列是k的周期函數(shù)。因此，在所有的諧波成分中，只有從k=0到

N－1的N個諧波成分是獨立的，用這N個諧波就可完全地表示出。另外，為了計算方便，引入一個系數(shù)1/N，這就形成了周期序列的離散傅里葉級數(shù)，即(5.2-3)下面來討論如何根據(jù)來求解系數(shù)。將式(5.2-3)兩端同時乘以e－j(2π/N)rn，并對n在從0到N－1的一個周期內(nèi)求和，得到利用復(fù)指數(shù)的正交性，即因此將r換成k，可得(5.2-4)式(5.2-4)就是計算k=0到N－1的N個諧波系數(shù)的公式，通常把稱為的離散傅里葉級數(shù)。從式(5.2-4)中也可以看出，也是周期為N的周期序列，即有習(xí)慣上，我們常采用以下符號因此，將上式代入式(5.2-4)和式(5.2-3)，并重寫如下(5.2-5)(5.2-6)式(5.2-5)和式(5.2-6)稱為離散傅里葉級數(shù)變換對，式中的n和k都為離散變量。通常把n和k分別看做時間和頻率變量，用DFS［·］表示時域到頻域的變換，稱為離散傅里葉級數(shù)正變換，用IDFS［·］表示由頻域到時域的變換，稱為離散傅里葉級數(shù)反變換。觀察離散傅里葉級數(shù)的正反變換式，我們有以下結(jié)論：

（1）不論是還是，都是周期為N的無限長序列，因此，離散傅里葉級數(shù)是兩個同周期的無限長序列之間的映射，即時域周期序列的離散傅里葉級數(shù)在頻域也是一個周期序列。

（2）對于周期序列，我們只要知道其中一個周期的內(nèi)容，則整個周期序列的信息也都知道了。因而周期序列的信息可以用N個序列值（一個周期）來代表。所以，不論是DFS還是IDFS，雖然是從無限長序列到無限長序列之間的變換，由于其周期特征，其計算中也僅需對序列的一個周期進行求和。從這一點來看，離散傅里葉級數(shù)也可以看做是建立起了從有限長序列到無限長序列的變換關(guān)系。實際上，任意一個長度為N的有限長序列x(n)都可以看做是一個周期為N的周期序列的一個周期；反過來說，任意一個周期為N的周期序列，都可以看做是它的一個周期所形成的N點序列進行以N為周期的周期延拓的結(jié)果。通常，我們將周期序列（假設(shè)周期為N）的第一個周期所處的區(qū)間［0,N－1］定義為“主值區(qū)間”，而處于主值區(qū)間的部分稱為“主值序列”。

（3）對于周期是N的序列，因為不是絕對可和的，其Z變換不收斂，所以不能用Z變換表示。但若只取

的一個周期則其Z變換存在，即(5.2-7)對比式(5.2-5)與式(5.2-7)，可知(5.2-8)式(5.2-8)表明，是的一個周期形成的有限長序列x(n)的Z變換在z平面的單位圓上以等間隔角進行采樣得到的。

同樣，x(n)的傅里葉變換為(5.2-9)對比式(5.2-5)與式(5.2-9)，可知(5.2-10)式(5.2-10)表明，是的一個周期形成的有限長序列x(n)的傅里葉變換以為間隔進行等間隔采樣得到的。因而，離散傅里葉級數(shù)實質(zhì)上是建立了周期序列與有限長序列之間的映射關(guān)系。

例5-1設(shè)為周期沖激串,即求的DFS。解當0≤n≤N－1時，=δ(n)，因而利用式(5.2-5)可得到即對于所有的k值，均為1。因此，利用式(5.2-6)，表示成級數(shù)形式為例5-2設(shè)的周期N=10，在主值區(qū)間內(nèi)，當0≤n≤4時，=1，當5≤n≤9時，=0。假設(shè)的主值序列為x(n)，其傅里葉變換為X(ejω)。試求和X(ejω)，并分別畫出它們的幅度特性圖。

解按照式(5.2-5)，有

按照式(5.2-9)，有圖5-1例5-2的DTFT與DFS幅度圖X(ejω)的幅度特性圖（一個周期）和的幅度特性圖（一個周期）如圖5-1所示。從圖5-1可以看出，相當于在ω=0到ω=2π的范圍內(nèi)，以2π/10的頻率間隔在10個等間隔的頻率上對x(n)的傅里葉變換進行采樣。這里也說明了DFS實際上代表了序列各個頻率分量的幅度。

注意，若x(n)不是取主值周期的序列，而是隨便取

的一個周期序列，比如n取5~14，則再次計算離散傅里葉級數(shù)，得到的結(jié)果和取主值周期的序列計算得到的結(jié)果是一樣的。5.2.2DFT與DFS

上面已經(jīng)提過，對于有限長序列與周期序列x(n)可看做是的一個周期（主值序列），而可看做是x(n)的以N為周期的周期延拓。所以，不論n的取值如何，我們都有(5.2-11)通過引入求余符號((n))N來表示式(5.2-11)中的(n模N)，同時利用矩形序列的符號RN(n)，就可以將周期序列與其主值序列x(n)之間的關(guān)系表示為(5.2-12)同理，頻域的周期序列也可看做是對頻域的有限長序列X(k)的周期延拓，而有限長序列X(k)可看成是周期序列主值序列，即(5.2-13)我們回頭再來看式(5.2-5)與式(5.2-6)的DFS及IDFS的表達式，其中的求和都只限定在主值區(qū)間內(nèi)進行，故完全適用于主值序列。假設(shè)時域和頻域的主值序列分別為x(n)與X(k)，則有(5.2-14)與(5.2-15)可以看出，式（5.2-15）恰為N點DFT的表達式，這說明DFT與DFS之間有著緊密的關(guān)系：有限長序列x(n)的N點離散傅里葉變換X(k)，就是以N為周期將x(n)進行周期延拓后的周期序列x((n))N的離散傅里葉級數(shù)的主值序列。式（5.2-14）說明，周期序列的離散傅里葉數(shù)，就是的主值序列（假設(shè)為N點）x(n)的N點離散傅里葉變換X(k)以N為周期的周期延拓序列。所以，既然是x(n)的傅里葉變換以2π／N為間隔的等間隔采樣，那么X(k)作為

的主值序列，就是x(n)的傅里葉變換以2π／N為間隔在［0,2π］區(qū)間的等間隔采樣。

因此，離散傅里葉變換(DFT)與周期序列的離散傅里葉級數(shù)(DFS)之間存在本質(zhì)的聯(lián)系。雖然DFT是針對有限長序列的，但根據(jù)傅里葉變換的時域、頻域的對偶關(guān)系，頻域的離散化必然對應(yīng)著時域序列本身的周期性。因此，進行離散傅里葉變換的原始序列必然是周期的，即DFT隱含著序列的周期性，有限長序列都是作為周期序列的一個周期來表示的，都隱含有周期性意義。

5.3DFT的性質(zhì)與定理

由于DFT與DTFT和Z變換之間以及DFS之間的本質(zhì)聯(lián)系，因此它們的許多性質(zhì)具有相似性。但是，由于在DFT變換中x(n)和X(k)均為有限長序列，因此它們之間的性質(zhì)還有一些重要差別。DFT的許多性質(zhì)在數(shù)字信號處理中有廣泛的應(yīng)用。本節(jié)討論DFT的一些主要性質(zhì)。以下討論中，假設(shè)序列x1(n)和x2(n)都是有限長序列，且設(shè)

X1(k)=DFT［x1(n)］,X2(k)=DFT［x2(n)］5.3.1DFT的隱含周期性

DFT的正反變換式定義了一對N點離散傅里葉變換，其中n和k的取值范圍均定義為0~N－1，如果式（5.1-1）中k的取值域為［－∞,+∞］，就會發(fā)現(xiàn)X(k)是以N為周期的，即

X(k)=X(k+mN),m為任意整數(shù)(5.3-1)

我們把X(k)的這一性質(zhì)稱為DFT的隱含周期性。證明

DFT的隱含周期性可以從兩種不同的角度得出：

（1）如前綜述，X(k)是對X(ejω)的采樣，由于X(ejω)是以2π為周期的周期函數(shù)，即X(k)是對X(ejω)在主值區(qū)［0,2π］上的N點等間隔采樣。顯然，當自變量k超出DFT變換區(qū)間時，必然得到［0,2π］之外區(qū)間上X(ejω)的采樣，且以N為周期重復(fù)出現(xiàn)，得到=X((k))N。

（2）利用X(k)與x(n)的周期延拓序列x((n))N的離散傅里葉級數(shù)之間的關(guān)系，也可以得出DFT的隱含周期性。5.3.2線性性質(zhì)

設(shè)有限長序列x1(n)和x2(n)的長度分別為N1和N2，若

x(n)=ax1(n)+bx2(n),a和b為常數(shù)

則有

X(k)=aX1(k)+bX2(k),k=0,1,…,N－1(5.3-2)

式中，N≥max［N1,N2］，X(k)、X1(k)、X2(k)分別是x(n)、x1(n)、x2(n)的N點DFT。注意，這里以N為變換長度，相對較短的序列需通過尾部補零使其長度增加為N。

該性質(zhì)可以直接用DFT的定義式證明，請讀者自己練習(xí)。5.3.3循環(huán)移位性質(zhì)

1.有限長序列的循環(huán)移位

設(shè)序列x(n)的長度為M，對x(n)以N為周期進行周期延拓，得到則定義x(n)的循環(huán)移位序列為(5.3-3)式(5.3-3)表示，將序列x(n)以N為周期進行周期延拓得到的周期序列，再移位m個單位之后，得到的周期序列仍舊是一個周期為N的序列，并取的主值序列，就得到x(n)的循環(huán)移位序列y(n)。當m<0時，表示向右循環(huán)移位。x(n)及其循環(huán)移位的過程如圖5-2所示，圖(a)、(b)、(c)、(d)分別對應(yīng)序x(n)、、和y(n)的波形，其中M=6,N=8,m=2。

2.循環(huán)移位性質(zhì)

設(shè)序列x(n)的長度為M，x(n)的循環(huán)移位序列y(n)為

y(n)=x((n+m))NRN(n),N≥M

令X(k)=DFT［(x(n)］，則

Y(k)=DFT［y(n)］=WkmNX(k),0≤k≤N－1

(5.3-4)

圖5-2序列的循環(huán)移位過程證明令n+m=l，得到上式中的x((l))N和WklN都是以N為周期的，對其在任意一個周期的求和結(jié)果相等。將上式的求和區(qū)間設(shè)在主值區(qū)間，就有因此5.3.4DFT的共軛對稱性

我們知道，序列傅里葉變換的對稱性是關(guān)于坐標原點的縱坐標的對稱性。DFT也有類似的對稱性，但在DFT中涉及的序列x(n)和X(k)均為有限長序列，且取值區(qū)間均為主值區(qū)間［0,N－1］，所以討論對稱性時，不能再以坐標原點作為對稱點，而是以n=N/2點作為對稱點。為了區(qū)別于無限長共軛對稱序列，我們用xep(n)和xop(n)分別表示有限長（或圓周）共軛對稱序列和共軛反對稱序列，其定義分別為(5.3-5)(5.3-6)如同任何實數(shù)都可以分解為偶對稱分量和奇對稱分量一樣，任何有限長序列x(n)都可以用它的共軛對稱分量和共軛反對稱分量之和來表示，即(5.3-7)其中(5.3-8)(5.3-9)同理可得(5.3-10)(5.3-11)式(5.3-10)和式(5.3-11)中的Xep(k)和Xop(k)分別表示有限長序列X(k)的共軛對稱分量和共軛反對稱分量。利用上述公式，可得出DFT的共軛對稱性質(zhì)：

（1）DFT［x*(n)］=X*(－k)=X*(N－k)(5.3-12)式中,x*(n)表示x(n)的共軛序列。

證明因為所以

（2）DFT［x*(－n)］=X*(k)(5.3-13)證明因為DFT的周期性，取x(n)的主值序列求和就有（3）如果序列x(n)可以表示為

x(n)=xr(n)+jxi(n),0≤n≤N－1其中則有(5.3-14)(5.3-15)式(5.3-14)和式(5.3-15)表明，如果序列x(n)的DFT為X(k)，則x(n)實部的DFT對應(yīng)于X(k)的共軛對稱分量Xep(k)，x(n)虛部的DFT對應(yīng)于X(k)的共軛反對稱分量Xop(k)。

證明利用式(5.3-8)和式(5.3-9)，可分別得到因此式(5.3-16)表明，序列x(n)的共軛對稱分量的DFT為X(k)的實部；式(5.3-17)表明，序列x(n)的共軛反對稱分量的DFT為X(k)的虛部乘以j。

上述公式(5.3-12)到公式(5.3-17)是序列DFT共軛對稱的基本公式，下面給出x(n)為實序列時的DFT共軛對稱公式，這些公式可以利用上述基本公式進行證明。

（5）實信號DFT的共軛對稱性。設(shè)x(n)為長度為N的實序列，且X(k)=DFT［x(n)］。

①X(k)共軛對稱，即

X(k)=X*(N－k),0≤k≤N－1(5.3-18)②如果x(n)實偶對稱，即

x(n)=x(N－n)

則X(k)也實偶對稱，即

X(k)=X(N－k)(5.3-19)

③如果x(n)實奇對稱，即

x(n)=－x(N－n)

則X(k)純虛奇對稱，即

X(k)=－X(N－k)

(5.3-20)

實際中實序列的DFT應(yīng)用非常廣泛。利用上述性質(zhì)可知，只要x(n)是實序列，則其離散傅里葉變換X(k)必然共軛對稱。所以只要計算出X(k)的前一半N/2個值，后一半的X(k)值即可利用對稱性求得。這樣可以減少近一半的運算量，提高運算

效率。5.3.5循環(huán)卷積定理

對應(yīng)于傅里葉變換中的線性卷積定理，DFT有循環(huán)卷積定理。下面首先介紹循環(huán)卷積的概念，然后介紹循環(huán)卷積定理和計算循環(huán)卷積的方法。

1.兩個有限長序列的循環(huán)卷積

設(shè)序列h(n)和x(n)的長度分別為N和M。h(n)和x(n)的L點循環(huán)卷積定義為(5.3-21)式中，

L稱為循環(huán)卷積的長度，且L≥max［M,N］。為了區(qū)別于第3章和第4章介紹的線性卷積，這里用來表示循環(huán)卷積，即yc(n)=x(n)

h(n)。

循環(huán)卷積可以采用圖解法、列表法等多種方法來計算，在計算機中常采用矩陣相乘的方法來計算。下面介紹如何用矩陣計算來表示循環(huán)卷積的公式。在式(5.3-21)中，令n=0，則在求和區(qū)間內(nèi)由x((n－m))L形成的關(guān)于x(n)的循環(huán)倒相序列為

{x(0),x(L－1),…,x(1)}

與由x((n))L的主值區(qū)間x(n)取值形成的序列{x(0),x(1),…,

x(L－1)}相比，該循環(huán)倒相序列相當于第一個序列值x(0)不動，將后面的序列反轉(zhuǎn)180°再放在x(0)后面。在式(5.3-21)中，令n=1，則在求和區(qū)間內(nèi)由x((n－m))L形成的x(n)循環(huán)倒相序列為

{x(1),x(0),x(L－1),…,x(2)}

觀察可以發(fā)現(xiàn)，它相當于將上述n=0時形成的關(guān)于x(n)的循環(huán)倒相序列向右循環(huán)移一位而成。

繼續(xù)增加n的取值，可以發(fā)現(xiàn)，所得到的序列都是在前一次移位的基礎(chǔ)上再向右移一位形成的。因此，當m和n均從0變化到L－1時，我們就得到式(5.3-21)中關(guān)于

x((n－m))L

取值的矩陣為我們把上面的矩陣稱為序列x(n)的L點循環(huán)卷積矩陣。其特點是：

（1）矩陣的第1行是x(n)的循環(huán)倒相序列，即由x((n))L的主值區(qū)間的x(n)取值形成的序列。注意，此時如果x(n)的長度M<L，則在x(n)后面補L－M個零。

（2）矩陣第1行以后的各行均由前一行向右循環(huán)移動一位所形成。

（3）矩陣各主對角線上的值均相等。

利用序列x(n)的L點循環(huán)卷積矩陣，式(5.3-21)可以寫成矩陣形式(5.3-22)例5-3已知x(n)=R4(n)，h(n)={1,2,0,1}，試分別求x(n)和h(n)的4點與8點循環(huán)卷積。

解利用式(5.3-22)，計算x(n)和h(n)的4點循環(huán)卷積yc(n)=x(n)

h(n)如下同理，計算x(n)和h(n)的8點循環(huán)卷積yc(n)=x(n)h(n)如下

2.DFT的時域循環(huán)卷積定理

設(shè)有限長序列h(n)和x(n)，長度分別為N和M，L=max

［N,M］。h(n)和x(n)的L點DFT分別為

H(k)=DFT［h(n)］

X(k)=DFT［x(n)］

如果Y(k)=H(k)·X(k)

則(5.3-23)或證明假設(shè)式(5.3-23)成立，對式(5.3-23)的兩邊進行DFT，可得利用循環(huán)卷積公式(5.3-21)，有上式中，令n1=n－m，則有因為上式中x((n1))LWkn1L是以L為周期的，所以對其在任何一個周期上求和的結(jié)果都是相等的。因此，對x((n1))L的主值區(qū)間0~L－1進行求和，則有時域循環(huán)卷積定理表明，兩序列時域的循環(huán)卷積，相當于兩序列的DFT相乘。因此，利用該定理可以使兩序列時域的循環(huán)卷積計算得到大大簡化，計算過程如圖5-3所示。圖5-3用時域循環(huán)卷積定理計算兩序列時域的循環(huán)卷積

3.DFT的頻域循環(huán)卷積定理

利用時域與頻域的對稱性，可以得到DFT的頻域循環(huán)卷積定理。

設(shè)有限長序列h(n)和x(n)，長度分別為N和M，L=max

［N,M］。h(n)和x(n)的L點DFT分別為

H(k)=DFT［h(n)］

X(k)=DFT［x(n)］

如果

y(n)=h(n)x(n)

則或關(guān)于DFT頻域循環(huán)卷積定理的證明留作習(xí)題，請讀者證明。

4.線性卷積與循環(huán)卷積的關(guān)系設(shè)x1(n)和x2(n)分別是N點和M點的有限長序列，對x1(n)和x2(n)作線性卷積(5.3-25)則yl(n)是長度為M+N－1點的有限長序列，其長度等于參與卷積的兩個序列的長度和減1。再對x1(n)和x2(n)作循環(huán)卷積。首先對x1(n)和x2(n)分別補零，使之長度均為L，

L≥max［N,M］，然后進行L點循環(huán)卷積

(5.3-26)由于x2((n－m))L是周期延拓序列，因此有代入式(5.3-26)，得到(5.3-27)式(5.3-27)說明，有限長序列x1(n)和x2(n)的線性卷積yl(n)以L為周期的周期延拓序列的主值序列即為這兩個有限長序列的循環(huán)卷積。yl(n)的長度為M+N－1，要想在周期延拓時不發(fā)生混疊，則要求延拓的周期L不小于M+N－1，如果滿足了這個條件，延拓序列的主值序列就是yl(n)本身。此時，循環(huán)卷積和線性卷積相同。延拓周期L若小于M+N－1，則各延拓周期發(fā)生混疊，其循環(huán)卷積和線性卷積不相同。

一般在實際情況中常常要求線性卷積，但線性卷積計算復(fù)雜，計算量大，因而在滿足一定條件下可以利用循環(huán)卷積代替線性卷積，簡化計算，提高運算效率。5.3.6DFT形式下的帕斯維爾(Parseval)定理

設(shè)有限長序列h(n)和x(n)，長度分別為N和M，L=max

［N,M］。h(n)和x(n)的L點DFT分別為

H(k)=DFT［h(n)］

X(k)=DFT［x(n)］

則有

(5.3-28)證明式(5.3-28)中，令h(n)=x(n)，則有上式表明：一個序列在時域計算的能量與在頻域計算的能量相等。

5.4頻域采樣

我們知道，對模擬信號進行時域等間隔采樣，則時域采樣信號的頻譜是原模擬信號頻譜的周期延拓。根據(jù)時域采樣定理，針對帶限信號，當采樣頻率大于等于奈奎斯特采樣頻率時，可以由時域離散采樣信號恢復(fù)原來的連續(xù)信號，而不丟失任何信息。那么，根據(jù)時域和頻域的對偶性質(zhì)，對離散時間序列x(n)的連續(xù)頻譜在頻域等間隔采樣，也應(yīng)該有類似的情況出現(xiàn)。下面就對序列的頻域采樣加以討論。

1.頻域采樣和頻域采樣定理

在5.2節(jié)中已經(jīng)提到，周期為N的周期序列的離散傅里葉級數(shù)的系數(shù)與的一個周期x(n)的Z變換在z平面單位圓的N個均分點上的采樣值相等。由于可以看做是x(n)的以N為周期的延拓序列，因此也可以這樣認為：對長度為N的有限長序列x(n)的Z變換在單位圓上進行N點等間隔采樣，則該頻域采樣序列的離散傅里葉級數(shù)的反變換就是周期延拓序列。那么，當x(n)的長度與采樣點數(shù)不一樣的時候又是什么情況呢？因此，需要一般性地討論任意一個絕對可和的非周期序列x(n)的情況。對于絕對可和的非周期序列x(n)，它的Z變換為由于x(n)絕對可和，因此其傅里葉變換存在且連續(xù)，故Z變換的收斂域包括單位圓。如果在z平面的單位圓上，對X(z)以等間隔角2π／N進行采樣，就可得到周期為N的頻域周期序列(5.4-1)顯然，這就是對x(n)的頻譜函數(shù)X(ejω)在間隔為2π／N的N個均分頻率點上的等間隔采樣。對周期序列，令其離散傅里葉級數(shù)的反變換為，則將式(5.4-1)代入上式，得到由于所以(5.4-2)這說明頻域采樣序列所對應(yīng)的時域周期序列是原序列x(n)的以N為周期的周期延拓，也就是說，頻域采樣會造成時域的周期延拓。根據(jù)DFT與DFS之間的關(guān)系知道，若分別截取和的主值序列xN(n)與

X(k)，則xN(n)和X(k)構(gòu)成一對DFT，即由于X(k)是的主值序列，因而其頻域的采樣就是對X(ejω)在頻率區(qū)間［0,2π］上的N點等間隔采樣。而xN(n)是的主值序列，也就是原序列x(n)的以N為周期的周期延拓序列的主值序列。顯然，只有在延拓周期大于等于x(n)的長度時，其周期延拓才不會發(fā)生混疊，才能使xN(n)=x(n)。綜上所述，可以總結(jié)出頻域采樣定理:

如果原序列x(n)的長度為M，且對其頻譜X(ejω)在頻率區(qū)間［0,2π］上等間隔采樣N點，得到的序列為X(k)，則僅當采樣點數(shù)

N≥M

時，才能由頻域采樣X(k)不失真地恢復(fù)出x(n)=IDFT［X(k)］，否則將產(chǎn)生時域混疊失真，不能利用x(n)=IDFT［X(k)］恢復(fù)原序列x(n)。

頻域采樣定理告訴我們，如果時域序列x(n)是無限長的，則其頻域采樣必然會造成時域混疊，從而不可能無失真地恢復(fù)原序列；只有對有限長序列，才能以適當?shù)牟蓸娱g隔進行頻域采樣而不丟失信息。

2.z域內(nèi)插公式與頻域內(nèi)插公式

我們已經(jīng)知道，對于時域采樣，其時域恢復(fù)過程可以用時域內(nèi)插公式來表示。同樣地，對于頻域采樣，也可由z域內(nèi)插公式恢復(fù)出原序列的Z變換，由頻域內(nèi)插公式恢復(fù)出原序列的傅里葉變換。

設(shè)序列x(n)的長度為M，在z平面的單位圓上對X(z)進行N點等間隔采樣，且滿足頻域采樣定理（即N≥M），則有(5.4-3)(5.4-4)(5.4-5)將式(5.4-5)代入式(5.4-3)，得到由于，因此(5.4-6)令(5.4-7)則(5.4-8)式(5.4-8)就稱為用X(k)即N個頻率抽樣來恢復(fù)X(z)的z域內(nèi)插公式，其中φk(z)稱為z域內(nèi)插函數(shù)。

將z=ejω

代入式(5.4-6)，經(jīng)化簡求得其頻率響應(yīng)為(5.4-9)其中(5.4-10)利用時域和頻域的對稱特性，同樣可以分析由式(5.4-9)如何得到序列x(n)的頻率響應(yīng)，請讀者將其與時域采樣信號的恢復(fù)重建相對比，采用類似的方法自行分析其恢復(fù)過程。5.5基2時間抽取FFT算法

快速傅里葉變換（FFT）并不是一種新的變換，而是計算離散傅里葉變換（DFT）的一種快速算法。

我們知道，有限長序列可以通過離散傅里葉變換(DFT)將其頻域也離散化成有限長序列，這在數(shù)字信號處理中非常有用。但由于計算量太大，直接利用DFT計算很難實時地處理問題，因此引出了快速傅里葉變換(FFT)。FFT最初是在1965年，由Cooley和Tukey提出的計算離散傅里葉變換（DFT）的快速算法引出的，它將DFT的運算量減少了幾個數(shù)量級。從此，對快速傅里葉變換（FFT）算法的研究便不斷深入，形成了一套高效的運算方法，使DFT的計算大大簡化。數(shù)字信號處理這門新興學(xué)科也隨FFT的出現(xiàn)和發(fā)展而迅速發(fā)展。到目前為止，根據(jù)對序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法，基本上可以分為兩大類：按時間抽選法（用DIT表示）和按頻率抽選法（用DIF表示）。這里我們主要討論兩種基本算法：基2DITFFT（時間抽選FFT）和基2DIFFFT（頻率抽選FFT）算法。

根據(jù)DFT的定義式在將所有WknN的值計算好的情況下，計算每一個X(k)值需要N次復(fù)數(shù)乘法和N－1次復(fù)數(shù)加法。因此計算出全部N點的X(k)即整個DFT運算共需N2次復(fù)數(shù)乘法和N(N－1)次復(fù)數(shù)加法?？梢?，直接計算DFT的計算量與N2成正比，當N很大時，運算量是很可觀的。例如，當N=8時，DFT需64次復(fù)乘，而當N=1024時，DFT所需復(fù)乘為1048576次，即一百多萬次復(fù)乘運算，這對實時性要求很高的信號處理來說，對計算速度的要求就太高了。因而需要對DFT的計算方法進行改進，以大大減少運算量。觀察DFT的計算公式就可以發(fā)現(xiàn)，利用WknN因子的下列固有性質(zhì)，可使DFT運算量減少：

（1）周期性：（2）對稱性：利用這兩個性質(zhì)，可以使DFT運算中的有些項合并，以減少乘法次數(shù)。例如，當N=4時，求X(2)的值。通過合并，可以使上式的乘法運算次數(shù)由4次減少到1次。由于DFT運算中的運算量直接與N2成正比，因此N越小,運算量就越小。因而利用上述特性把長序列的DFT分解為短序列的DFT，可以大大減少運算量。FFT正是基于這種思路而發(fā)展起來的。5.5.1基2DITFFT算法原理

為了將大點數(shù)的DFT分解為小點數(shù)的DFT運算，要求序列的長度N為復(fù)合數(shù)，最常用的是N=2L的情況（L為正整數(shù)）。如果不滿足這個條件，可以人為地加上若干零值點，使其滿足這個條件。我們把這種N為2的整數(shù)冪的FFT稱為基2FFT。下面我們首先討論N/2點DFT的計算，在此基礎(chǔ)上說明基

2DITFFT算法的計算原理和過程。

1.N/2點DFT

（1）將序列x(n)按n的奇偶分為兩組子序列，這樣有n為偶數(shù)時：n為奇數(shù)時:則序列x(n)的DFT就變?yōu)?5.5-1)由于因此，式(5.5-1)可表示為(5.5-2)其中,X1(k)和X2(k)分別為x1(r)和x2(r)的N/2點DFT，即(5.5-3)(5.5-4)式(5.5-2)表明，一個N點的DFT可以分解為兩個N/2點的DFT。但由于x1(r)、x2(r)以及X1(k)、X2(k)都是N/2點的序列，因此利用式(5.5-2)只能得到X(k)的k=0,1,…,(N/２)－1個值，即X(k)的前半部分。要得到全部的X(k)值，就必須應(yīng)用DFT中WmN因子的性質(zhì)。（2）X(k)的后半部分的確定。利用WmN因子的周期性，有得到(5.5-5)(5.5-6)又由于所以根據(jù)式(5.5-2)，有(5.5-7)這樣，只要求出0~(N/2－1)區(qū)間的所有X1(k)和X2(k)值，就可根據(jù)式(5.5-7)求出N/2到(N－1)區(qū)間內(nèi)的所有X(k)值，也就是說后半部分的X(k)完全可由X1(k)和X2(k)確定。綜上所述，X(k)的前后兩部分均可由X1(k)和X2(k)表示，而X1(k)和X2(k)即為x1(r)和x2(r)的N/2點DFT。這樣，一個N點的DFT完全可由兩個N/2點的DFT來計算。為方便起見，以下的X1(k)和X2(k)均指x1(r)和x2(r)的N/2點DFT。（3）蝶形運算。由X1(k)、X2(k)表示X(k)的運算是一種特殊的運算，我們定義為蝶形運算:(5.5-8)式(5.5-8)的蝶形運算可用圖5-4所示的蝶形信號流圖符號表示。流圖的表示方法將在第6章討論。圖5-4按時間抽取的蝶形運算流圖符號（4）計算工作量分析。

通過將序列x(n)按奇、偶分組后，可將其N點DFT分解為兩個N/2點DFT，然后經(jīng)過N/2個蝶形運算來完成。從圖5-4可以看出，每個蝶形運算需要一次復(fù)數(shù)乘法及兩次復(fù)數(shù)加法。這樣，一個N點DFT分解為兩個N/2點DFT后，如果直接計算N/2點DFT，則每一個N/2點DFT只需要(N/2)2次復(fù)數(shù)乘法和(N/2)(N/2－1)次復(fù)數(shù)加法，因此兩個N/2點DFT共需N2/2次復(fù)數(shù)乘法和N(N/2－1)次復(fù)數(shù)加法。再加上利用蝶形運算把兩個N/2點DFT合成為N點DFT時的N/2個蝶形運算的計算量，通過這種分解方法計算N點DFT，總共需要復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)都近似為N2/2，因此通過這種分解后，運算工作量差不多減少到原來的一半。

現(xiàn)以N=23=8點DFT為例，詳細分析這一分解過程。

①n為偶數(shù)時的序列為x(0)，x(2),x(4),x(6),分別記作:

x1(0)=x(0),x1(1)=x（2）

x1(2)=x(4),x1(3)=x(6)對這組序列進行N/2=4點的DFT，得②n為奇數(shù)時的序列為x(1),x(3),x(5),x(7)，分別記作:

x2(0)=x(1),x2(1)=x(3),x2(2)=x(5),x2(3)=x(7)對這組序列進行N/2=4點的DFT，得因此③對X1（k)和X2(k)進行蝶形運算,這里前半部分項數(shù)為X(0)~X(3),后半部分項數(shù)為X(4)~X(7)。整個過程如圖5-5所示。圖5-5按時間抽取，將一個N點DFT分解為兩個N/2點DFT（N=8）

2.繼續(xù)分解

既然如此，由于N=2L，則N/2仍是偶數(shù)，可以采用同樣的方法進一步將每個N/2點DFT的輸入再按奇偶分組，進而將每個N/2點DFT分解為兩個N/4點DFT。

首先，將原來n為偶數(shù)時的N/2點序列x1(r)分解為(偶中偶）(偶中奇）對這兩個N/4點的序列進行DFT，得到從而可得到X1(k)前N/4項為(5.5-9)則X1(k)的后N/4項為(5.5-10)同理，對序列中原來n為奇數(shù)的N／2點序列x2(r)再按奇偶分為兩個N／4點序列：(奇中偶）(奇中奇）則得到(5.5-11)(5.5-12)其中，X5(k)與X6(k)分別為序列x5(l)和x6(l)的點DFT。下面，我們以將N=8時的DFT繼續(xù)分解為四個N/4點DFT的計算過程為例進行說明，具體如下。

(1)將原序列x(n)的“偶中偶”部分，即x3(l)=x1(r)=x(n)取出如下

x3(0)=x1(0)=x(0),x3(1)=x1(2)=x(4)

計算所構(gòu)成序列的N/4點DFT，從而得到X3(0)和X3(1)。

(2)將原序列x(n)的“偶中奇”部分，即x4(l)=x1(r)=x(n)取出如下

x4(0)=x1(1)=x（2），x4(1)=x1(3)=x(6)

計算所構(gòu)成序列的N/4點DFT，從而得到X4(0)和X4（1)。

(3)將原序列x(n)的“奇中偶”部分，即x5(l)=x2(r)=x(n)取出如下

x5(0)=x2(0)=x(1),x5(1)=x2(2)=x(5)

計算所構(gòu)成序列的N/4點DFT，從而得到X5(0)和X5(1)。

(4)將原序列x(n)的“奇中奇”部分，即x6(l)=x2(r)=x(n)取出如下

x6(0)=x2(1)=x(3)

x6(1)=x2(3)=x(7)

計算所構(gòu)成序列的N/4點DFT，從而得到X6(0)和X6(1)。

(5)由X3(0)、X3(1)、X4(0)、X4(1)進行蝶形運算,得到X1(0)~X1(3)。

(6)由X5(0)、X5(1)、X6(0)、X6(1)進行蝶形運算,得到X2(0)~X2(3)。

(7)由X1(0)~X1(3)和X2(0)~X2(3)進行蝶形運算,得到X(0)~X(7)。

整個過程如圖5-6所示。圖5-6按時間抽取，將一個N點DFT分解為四個N/4點DFT的組合（N=8）這樣，經(jīng)過又一次分解(得到四個N/4點DFT)和兩級蝶形運算，其運算量又大約減少一半，即為N點DFT的1/4。

這樣的分解可以一直進行到最后，也就是最后剩下的是兩點DFT，它只有加減運算，但為了統(tǒng)一運算結(jié)構(gòu)，我們?nèi)匀徊捎孟禂?shù)為W0N的蝶形運算來表示。比如，對于N=8時的DFT，N/4點即為兩點DFT，因此亦即

因此，8點DFT的FFT的蝶形運算流圖如圖5-7所示。圖5-78點FFT的時間抽選算法信號流圖這種方法按照輸入序列在時間上的次序是屬于偶數(shù)還是奇數(shù)，將序列進一步分解為兩個更短的子序列，所以稱做“按時間抽取法”。5.5.2DITFFT運算量分析

由上述分析可知,當N=2L時共需L級蝶形運算，而且每級都由N/2個蝶形運算組成，每個蝶形運算都有一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法。因此，最終計算一個序列的N點FFT，所需的總的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

復(fù)數(shù)乘復(fù)數(shù)加由于計算機的乘法運算比加法運算所需的時間多得多，故通常以乘法作為比較基準。

根據(jù)前面的分析我們知道，如果直接用DFT的計算公式計算N點DFT，所需的復(fù)數(shù)乘法次數(shù)是mF=N2。相比之下，在計算大點數(shù)的DFT時，F(xiàn)FT的優(yōu)勢體現(xiàn)得更為明顯，如N=1024時，直接用定義式計算所需的復(fù)數(shù)乘法次數(shù)為N2=10242=126976，而FFT所需的復(fù)數(shù)乘法次數(shù)為，計算次數(shù)不到原來的1/20，因而計算時間大大減少。在N的數(shù)值繼續(xù)增大時，與直接計算DFT相比，F(xiàn)FT的運算效率還將更加突出。5.5.3DITFFT算法的特點

針對任意的N=2L點的DITFFT算法，我們來討論一下它的運算特點。

1.原位運算

由上述運算流圖可知，一共有N個輸入/輸出行，log2N=L級蝶形運算(基本迭代運算)。設(shè)用m(m=1,2,…,L)表示第m級迭代，用k、j表示蝶形輸入數(shù)據(jù)所在的（上/下）行數(shù)(k,j=0,1,…,N－1)，則任何一個蝶形運算都可用下面的通用式來

表示(5.5-13)令當m=1時，則有（只表示前兩個蝶形）當m=2時，則有（只表示前兩個蝶形）當m=3時，則有（只表示前兩個蝶形）可見，通過在某級進行蝶形運算的兩個節(jié)點變量k和j就完全可以確定該蝶形運算的結(jié)果，而與其他節(jié)點變量無關(guān)。這樣，蝶形運算的兩個輸出值仍可放回蝶形運算的兩個輸入所在的存儲器中，最終實現(xiàn)輸入數(shù)據(jù)、中間運算結(jié)果和最后輸出均使用同一組存儲器的原位運算。因此，雖然DIFFFT算法共有L級且每級均有N/2個蝶形運算，但實際上只需

N個存儲單元。可見，這種原位運算結(jié)構(gòu)可以節(jié)省存儲單元，降低設(shè)備成本。

2.倒位序規(guī)律

由圖5-8可知,輸出X(k)按正常順序排列在存儲單元,而輸入則是按以下順序排列的

x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)這種順序看起來好像“混亂無序”，但實際上也是有規(guī)律的，我們將這種順序稱做倒位序,即二進制數(shù)倒位。

這種倒位序是由奇偶分組造成的，以N=8為例示于圖5-8。圖5-8倒位序的樹狀圖

3.倒位序?qū)崿F(xiàn)

一般實際運算中，總是先將輸入序列按自然序存入存儲單元，為了得到倒位序的排列，可以通過變址運算來完成。假設(shè)輸入序列的序號為n，用二進制表示為(n2n1n0)2，則其倒位序的二進制數(shù)即為(n0n1n2)2。例如，N=8時的自然序與倒位序的關(guān)系如表5-1所示。

有了自然序號n與倒位序號，就可以通過變址處理將按自然順序存放在存儲單元中的數(shù)據(jù)換成所要求的倒位序。具體的變址功能如圖5-9所示。圖5-9碼位倒置的變址處理當n=時，不必調(diào)換；當n≠時，必須將數(shù)據(jù)x()調(diào)入原來存放數(shù)據(jù)x(n)的存儲單元內(nèi)，而將數(shù)據(jù)x(n)調(diào)入存放x(

)的存儲單元內(nèi)。注意，在具體實現(xiàn)時必須避免把已調(diào)換過的數(shù)據(jù)再次調(diào)換（否則又回到原狀），這可通過比較n

和的大小來實現(xiàn)：若比n小，則意味著此x(n)已經(jīng)和

x()調(diào)換過，不必再調(diào)換了；只有當>n時才進行調(diào)換。

盡管變址運算所占運算量的比例很小，但對某些高要求的應(yīng)用（尤其在實時信號處理中），也可設(shè)法用適當?shù)碾娐方Y(jié)構(gòu)直接實現(xiàn)之。例如，單片數(shù)字信號處理器TMS320C25就有專用于FFT的二進制碼變址模式。

4.蝶形運算兩節(jié)點的距離

以圖5-7所示的8點DITFFT為例，其第一級每個蝶形運算的兩節(jié)點間的距離為1，第二級每個蝶形的兩節(jié)點間的距離為2，第三級每個蝶形的兩節(jié)點間的距離為4。由此類推，對于N=2L點的DITFFT，其第m級運算中的每個蝶形的兩節(jié)點間的距離為2m－1。因此，我們可以將蝶形運算表示為(5.5-14)

5.WrN的確定

在每個蝶形運算中都要乘以因子WrN，我們稱其為旋轉(zhuǎn)因子。由于N=2L為已知，因此只需確定r的值。通過觀察圖5-7不難發(fā)現(xiàn)，r的變化是有一定規(guī)律的，針對這些規(guī)律可以采用多種方法確定r的值。一種簡便的方法是：

(1)將蝶形運算兩節(jié)點中的第一個節(jié)點標號值k表示成L位(N=2L)二進制數(shù)：k=(nL－1…n1n0)2。

(2)將k=(nL－1…n1n0)2左移(L－m)位(m指m級的運算),右邊位置補零,就可得到(r)2的值，即(r)2=(k)22L－m

。例如,N=8=23,有

(1)k=2,m=3時的r值:

k=2=(010)2，左移L－m=3－3=0，則r=(010)2=2

(2)k=3，m=3時的r值：

k=3=(011)2,左移L－m=3－3=0，則r=(011)2=3

(3)k=5，m=2的r值:

k=5=(101)2，左移L－m=3－2=1，則r=(010)2=25.6基2頻率抽取FFT算法

同樣是基于將長序列分解為短序列的思想，如果把輸出序列X(k)（假設(shè)也是N點序列）按其順序的奇偶性分解為越來越短的子序列，就形成了另一種FFT算法，稱為按頻率抽?。―IF）的FFT算法。

5.6.1DIFFFT算法原理

1.N點DFT的另一種表達形式

仍設(shè)序列點數(shù)N=2L，L為整數(shù)。我們把輸入序列x(n)按n的順序分成前后兩部分（注意，這不是頻率抽取），可得到N點DFT的另一種表達形式由于，故因此X(k)可進一步表示為(5.6-1)

2.X(k)按奇偶分組當k為偶數(shù)時,(－1)k=1；當k為奇數(shù)時,(－1)k=－1。因此，按k的奇偶可將X(k)分為兩部分。令則(5.6-2)(5.6-3)

3.蝶形運算可以看出,式(5.6-2)為前一半輸入與后一半輸入之和的N/2點DFT，式(5.6-3)為前一半輸入與后一半輸入之差再與WnN乘積的N/2點DFT。如果令(5.6-4)則(5.6-5)式(5.6-4)所表示的運算關(guān)系可以用圖5-10所示的蝶形運算來表示。圖5-10按頻率抽取蝶形運算流圖符號這樣，就可以把一個N點DFT按k的奇偶分解為兩個N/2點DFT了。比如當N=8時，上述分解過程如圖5-11所示。圖5-11按頻率抽取將一個N點DFT分解為兩個N/2點DFT的組合（N=8）

4.繼續(xù)分解

同時間抽取法的推導(dǎo)過程一樣，由于N=2L，N/2仍是一個偶數(shù)，因而可以將每個N/2點DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點DFT進一步分解為兩個N/4點DFT。這兩個N/4點DFT的輸入也是先將N/2點DFT的輸入（即前一級蝶形的輸出）上下對半分開后通過蝶形運算之后形成的，這一步分解過程如圖5-12所示。圖5-12按頻率抽取將一個N點DFT分解為四個N/4點DFT的組合（N=8）這樣的分解可以一直進行到第L級（N=2L），第L級實際上就是作兩點DFT，它只有加減運算，但為了統(tǒng)一運算結(jié)構(gòu)，我們?nèi)匀徊捎孟禂?shù)為W0N的蝶形運算來表示，這N/2個兩點DFT的N個輸出即為x(n)的N點DFT的結(jié)果X(k)。圖5-13表示了一個N=8的完整的按頻率抽取的FFT運算流圖。圖5-13按頻率抽取的FFT流圖（N=8）5.6.2DIFFFT算法特點

1.原位運算

從圖5-13可以看出，這種運算和按時間抽取法一樣，是很有規(guī)律的。其每級(列)都是由N/2個蝶形運算構(gòu)成的,每一個蝶形結(jié)構(gòu)完成同樣的基本迭代運算:(5.6-6)式中,m表示第m級迭代，k、j為數(shù)據(jù)所在行數(shù)。通過進行蝶形運算的兩個節(jié)點變量k和j完全可以確定蝶形運算的結(jié)果，而與其他節(jié)點變量無關(guān)。因而蝶形運算的兩個輸出值仍可放回蝶形運算的兩個輸入所在的存儲器中，實現(xiàn)原位運算。

2.蝶形運算兩節(jié)點的距離

從圖5-13中可以看出，當計算第一級蝶形(m=1)時，參與同一蝶形運算的兩節(jié)點之間的距離為4；第二級每個蝶形的兩節(jié)點之間的距離為2，第三級每個蝶形的兩節(jié)點之間的距離為1。因此對于N=2L的一般情況，可推出其蝶形運算兩節(jié)點之間的距離為2L－m=N／２m，其中，m是指第m級蝶形，m=1,2,…,L。

3.WrN的計算

由于第m級DIF蝶形運算的兩節(jié)點間的距離為N／2m，因此該蝶形運算可表示為(5.6-7)現(xiàn)在的問題是在不同級（m）的情況下，如何求解r。一種簡便的方法是：

(1)將蝶形運算中第一個節(jié)點標號值k表示成L位二進制數(shù)：k=(nL－1…n1n0)2。

(2)將k=(nL－1…n1n0)2左移m－1位，右邊位置補零，就可得到(r)2的值，即(r)2=(nL－1…n1n0)22m－1。

例如，N=8時，有

(1)m=1，k=2時，k=(010)2，左移1－1=0位，則r=(010)2=2

(2)m=2，k=1時，k=(001)2，左移2－1=1位，則r=(010)2=2

(3)m=2，k=5時，k=(101)2，左移2－1=1位，則r=(010)2=25.6.3DIF法與DIT法的異同

通過對兩種算法的原理及特點進行比較，我們可以看出，DIT法與DIF法在以下兩個方面是相同的：

(1)兩種算法都可以進行原位運算。

(2)兩種算法運算量相同,即都有L級（N=2L時）運算，每級運算均需N/2個蝶形，每個蝶形均有一次復(fù)乘、兩次復(fù)加，故總的運算量均為次復(fù)乘和Nlog2N次復(fù)加。兩種算法的不同點在于:

(1)DIT輸入為倒位序,輸出為自然序，而DIF恰好相反。初看起來，這一點不同是顯而易見的。但對于任何流圖，只要保持各節(jié)點所連的支路以及傳輸系數(shù)不變，則不論節(jié)點位置怎么排列，所得流圖都是等效的，因而不論是哪種算法，都可以將輸入或輸出進行重排，使其變?yōu)樽匀恍蚧虻刮恍颍赃@并不是二者的本質(zhì)區(qū)別。

(2)基本蝶形不同。

DIT中的蝶形運算是先作復(fù)乘后再作加減法，而DIF的復(fù)數(shù)乘法則僅出現(xiàn)在減法之后，這一點才是二者本質(zhì)上的不同。如果將DITFFT的基本蝶形運算寫為矩陣形式，則有(5.6-8)同樣，將DIFFFT的基本蝶形運算寫為矩陣形式，則有(5.6-9)從式(5.6-8)和式(5.6-9)可以看出，兩個蝶形運算的傳輸矩陣互為轉(zhuǎn)置。另外，從圖5-4和圖5-10也可以看出，如果將DIT的基本蝶形的所有支路方向都反向，并且交換輸入和輸出，就得到了DIF的基本蝶形；反過來將DIF的基本蝶形的所有支路方向都反向，并且交換輸入和輸出，就得到了DIT的基本蝶形。因此，DIT與DIF的基本蝶形運算是互為轉(zhuǎn)置的。5.7IDFT的快速實現(xiàn)——IFFT算法

DFT的FFT算法同樣可以適用于離散傅里葉反變換的運算，即快速傅里葉反變換（IFFT）。IFFT可以通過以下兩種方法來快速實現(xiàn)。一種方法需要稍微改動FFT程序和參數(shù)來實現(xiàn)。由于比較兩式可知，只要把DFT運算中的每個系數(shù)WnkN換成

W－nkN，最后再乘以常數(shù)１／N，就可以得到IDFT的快速算法——IFFT。

此外,可以將常數(shù)１/N分配到每級運算中,由于

因此每級蝶形運算均乘以1/2即可。

另一種方法則完全不用改變FFT的程序而可以直接實現(xiàn)IFFT?？紤]到將上述的IDFT公式兩邊同時取共軛，可得因此(5.7-1)式(5.7-1)說明，只要先將X(k)取共軛，然后將X*(k)作為輸入直接調(diào)用FFT程序計算DFT，最后再取一次共軛，并乘以1/N，即可得到x(n)。所以，F(xiàn)FT和IFFT的運算完全可以調(diào)用同一個子程序，使用起來十分方便。

5.8MATLAB實現(xiàn)

5.8.1用MATLAB計算序列的DFT與IDFT

1.直接計算DFT與IDFT

根據(jù)DFT與IDFT的定義式可以編寫MATLAB函數(shù)來完成DFT與IDFT的計算?？紤]到每計算一個X(k)都需要一個for…end循環(huán)來計算N項的和式，為了計算所有的X(k)又需要另一個for…end循環(huán)，這就會得到一種兩重循環(huán)嵌套的實現(xiàn)方式。為了提高計算效率，在MATLAB中可以采用矩陣向量乘法來實現(xiàn)上述計算。令行向量X表示X(k)的各點的值，行向量x表示

x(n)的各點的值，則上面兩式可表示為

X=xXN（5.8-1）（5.8-2）式中矩陣WN為0≤n,k≤N－1（5.8-3）

矩陣WN是一個方陣，稱為DFT矩陣。因此，可以編寫下面的MATLAB函數(shù)來實現(xiàn)上述的計算過程。計算DFT的函數(shù)為：

function［Xk］=dft(xn,N)

%計算DFT

%［Xk］=dft(xn,N)

%Xk是頻域的DFT序列

%xn是時域的有限長序列

%N是DFT的長度

n=［0:1:N－1］;

k=［0:1:N－1］;