《數(shù)字信號(hào)處理》課件-第4章

4.1引言

4.2提高DFT運(yùn)算效率的基本途徑4.3基2時(shí)分FFT算法

4.4基2頻分FFT算法

4.5IDFT的快速算法

4.6實(shí)序列DFT的有效計(jì)算方法

4.7線性調(diào)頻Z(Chirp-Z)變換算法習(xí)題與上機(jī)題

離散傅里葉變換(DFT)是信號(hào)分析與處理中的一種重要變換。因?yàn)橹苯佑?jì)算DFT的計(jì)算量與變換區(qū)間長(zhǎng)度N的平方成正比，當(dāng)N較大時(shí)，計(jì)算量太大，所以在快速傅里葉變換(FastFourierTransform，F(xiàn)FT)出現(xiàn)以前，直接用DFT進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。4.1引言自從1965年圖基(J.W.Tukey)和庫(kù)利(J.W.Cooley)在《計(jì)算數(shù)學(xué)》(MathematicsComputation)雜志上發(fā)表了著名的《機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法》論文后，桑德-圖基等快速算法相繼出現(xiàn)，很快形成了一套高效運(yùn)算方法，這種算法使DFT的運(yùn)算效率提高了幾個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了良好的條件，大大推動(dòng)了數(shù)字信號(hào)處理技術(shù)的發(fā)展。多年來(lái)，人們繼續(xù)尋求更快、更靈活的好算法，目前除了基2、基4算法外，還有分裂基、混合基等算法。對(duì)于N=1024，直接計(jì)算需要復(fù)數(shù)乘法1048576次，而幾種常用FFT算法使計(jì)算量大大降低，例如基2算法需要復(fù)數(shù)乘法5120次，基4算法需要復(fù)數(shù)乘法3840次，

分裂基算法需要復(fù)數(shù)乘法3413次。本章重點(diǎn)介紹基2快速傅里葉變換算法。設(shè)x(n)為N點(diǎn)有限長(zhǎng)序列，其DFT為

(4.2.1)

其反傅里葉變換(IDFT)為

(4.2.2)4.2提高DFT運(yùn)算效率的基本途徑正變換與反變換的差別只在于的指數(shù)符號(hào)不同，以及差一個(gè)乘數(shù)因子，因此我們以下只討論DFT的運(yùn)算量，IDFT的運(yùn)算量與DFT的基本相同。

一般來(lái)說(shuō)，X(k)為復(fù)數(shù)(只有x(n)為實(shí)數(shù)且條件偶對(duì)稱時(shí)，X(k)才為實(shí)數(shù))，x(n)多數(shù)情況下也為復(fù)數(shù)(例如：信號(hào)經(jīng)A/D采樣，數(shù)字下變頻芯片之后輸出為I、Q正交兩路，詳見(jiàn)第9章)。因此，計(jì)算一點(diǎn)X(k)需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法。由于有N點(diǎn)X(k)，因此完成N點(diǎn)序列的DFT共需要N2次復(fù)數(shù)乘法，即

CM=N2

(4.2.3)

以及N(N-1)次復(fù)數(shù)加法，即

CA=N(N-1)≈N2

(4.2.4)實(shí)際實(shí)現(xiàn)中復(fù)數(shù)乘法和加法都要依賴實(shí)數(shù)乘法和加法。由于一次復(fù)數(shù)乘法需要4次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法，一次復(fù)數(shù)加法需要2次實(shí)數(shù)加法，因此直接計(jì)算DFT的實(shí)數(shù)乘法次數(shù)為

RM=4N2

(4.2.5)

實(shí)數(shù)加法次數(shù)為

RA=2N(N-1)+2N2≈4N2

(4.2.6)所以，直接計(jì)算DFT時(shí)的運(yùn)算量與N2成正比。設(shè)N=1024，則直接計(jì)算DFT需要100多萬(wàn)次(1048576次)復(fù)數(shù)乘法。在實(shí)時(shí)計(jì)算較寬帶寬的頻譜時(shí)，即使使用目前運(yùn)算速度最快的DSP芯片也無(wú)法滿足計(jì)算要求。

觀察式(4.2.1)，要想提高DFT的運(yùn)算效率，只有利用DFT定義式中旋轉(zhuǎn)因子的特點(diǎn)。根據(jù)第3章所講內(nèi)容，我們可知有以下幾個(gè)特點(diǎn):

(1)共軛對(duì)稱性：。

(2)周期性：。

(3)可約性：。利用共軛對(duì)稱性，可以合并式(4.2.1)中的乘法項(xiàng)，從而減少了近一半的乘法次數(shù)。

利用旋轉(zhuǎn)因子的周期性和可約性，可以將長(zhǎng)序列的DFT分解成短序列的DFT。由于DFT的運(yùn)算量與N2成正比，N越小，計(jì)算量越小。因此將長(zhǎng)序列DFT變?yōu)槎绦蛄蠨FT是減少DFT運(yùn)算量的根本途徑?？焖俑道锶~變換算法正是基于此思路而發(fā)展起來(lái)的。

將長(zhǎng)序列的DFT劃分為短序列的DFT有兩種劃分方法：一種是將時(shí)域序列按奇偶劃分，稱之為時(shí)間抽取(DecimationinTime，DIT)算法或基2時(shí)分算法;一種是將頻域DFT按奇偶劃分，稱之為頻率抽取(DecimationinFrequency，DIF)算法或基2頻分算法。4.3.1基2時(shí)分蝶式運(yùn)算定理

設(shè)序列x(n)的長(zhǎng)度為N，且滿足N=2M，M為整數(shù)，其N點(diǎn)DFT為X(k)=DFT［x(n)］，0≤k，n≤N-1。按n的奇偶將x(n)分解為兩個(gè)點(diǎn)的子序列

x1(r)=x(2r)，r=0，1，…，(4.3.1)

x2(r)=x(2r+1)，r=0，1，…，(4.3.2)4.3基2時(shí)分FFT算法若X1(k)=DFT［x1(r)］，X2(k)=DFT［x2(r)］，0≤k≤

-1，則有

(4.3.3a)

(4.3.3b)

證明x(n)的N點(diǎn)DFT為

利用旋轉(zhuǎn)因子的可約性，即，

X(k)可以寫成

由于X1(k)和X2(k)都隱含周期性，周期為，因此上式可以寫為

當(dāng)0≤k≤

-1時(shí)

當(dāng)≤k≤N-1時(shí)

令，則有

由于，因此

最后

由證明過(guò)程可得，N點(diǎn)DFT可以分解為兩個(gè)點(diǎn)的DFT，它們按式(4.3.3)又組合成一個(gè)N點(diǎn)的DFT。式(4.3.3)也稱為蝶式運(yùn)算公式。由蝶式運(yùn)算定理可以看出，要完成一個(gè)蝶形運(yùn)算(即計(jì)算一次蝶式運(yùn)算定理)，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法，計(jì)算N點(diǎn)DFT共需計(jì)算兩個(gè)點(diǎn)的DFT和個(gè)蝶形運(yùn)算。計(jì)算點(diǎn)DFT需要次復(fù)數(shù)乘法和次復(fù)數(shù)加法。當(dāng)N1時(shí)，計(jì)算N點(diǎn)DFT共需由此可見(jiàn)，僅經(jīng)過(guò)一次分解，就使運(yùn)算量減少近一半。如果N=2M，則我們可以繼續(xù)分解，直至分解到1點(diǎn)DFT，運(yùn)算量即可大大減少。4.3.2基2時(shí)分的蝶形流圖與計(jì)算量分析

1.蝶形流圖

基2時(shí)分FFT蝶式運(yùn)算定理的運(yùn)算公式可以用圖4.3.1(a)所示的信號(hào)流圖表示，由于這個(gè)圖形呈蝶形，故稱為蝶形流圖，圖(b)是其簡(jiǎn)化形式。一個(gè)蝶形流圖是基2時(shí)分算法的一個(gè)基本單元。圖4.3.1DIT-FFT蝶式運(yùn)算信號(hào)流圖(a)蝶形流圖;(b)蝶形流圖簡(jiǎn)化形式圖中左面兩支為輸入，中間以一個(gè)點(diǎn)表示加、減運(yùn)算，右上支為相加輸出，右下支為相減輸出。如果在某一支路上信號(hào)需要進(jìn)行乘法運(yùn)算，則在該支路上標(biāo)以箭頭，并將

相乘的系數(shù)標(biāo)在箭頭邊。這樣，蝶式運(yùn)算定理的運(yùn)算公式(4.3.3)所表示的運(yùn)算，可用圖4.3.1(b)所表示的“蝶形結(jié)”來(lái)表示。采用這種表示法，可將基2時(shí)分的分解過(guò)程用計(jì)算流圖來(lái)表示。

【例4.3.1】將8點(diǎn)序列的DFT用基2時(shí)分FFT算法進(jìn)行分解。

解

(1)第一次分解。

將8點(diǎn)序列x(n)分解為兩個(gè)4點(diǎn)序列x1(n)和x2(n)，x1(n)為偶數(shù)序列，x2(n)為奇數(shù)序列，即

x1(n)={x(0)，x(2)，x(4)，x(6)}

x2(n)={x(1)，x(3)，x(5)，x(7)}

4點(diǎn)序列x1(n)和x2(n)分別做4點(diǎn)DFT得到X1(k)和X2(k)，由X1(k)和X2(k)通過(guò)蝶形構(gòu)造獲得8點(diǎn)DFTX(k)。第一次分解的旋轉(zhuǎn)因子為(k=0，1，2，3)，運(yùn)算流圖如圖4.3.2所示。

(2)第二次分解。將兩個(gè)4點(diǎn)序列x1(n)和x2(n)分解為四個(gè)2點(diǎn)序列x3(n)、x4(n)、和。

圖4.3.2

N點(diǎn)DFT基2時(shí)分第一次分解運(yùn)算流圖(N=8)

2點(diǎn)序列分別做2點(diǎn)DFT得到X3(k)、X4(k)、、

，由四個(gè)2點(diǎn)DFT通過(guò)蝶形構(gòu)造獲得兩個(gè)4點(diǎn)DFT，再通過(guò)蝶形構(gòu)造獲得8點(diǎn)DFTX(k)。第二次分解的旋轉(zhuǎn)因

子為，運(yùn)算流圖如圖4.3.3所示。圖4.3.3

N點(diǎn)DFT基2時(shí)分第二次分解運(yùn)算流圖(N=8)

(3)第三次分解。

將四個(gè)2點(diǎn)序列分解為8個(gè)1點(diǎn)序列，其中

由于1點(diǎn)序列的DFT值為其序列本身，因此在最后一次分解后，流圖中已經(jīng)沒(méi)有直接計(jì)算DFT的環(huán)節(jié)。第三次分解旋轉(zhuǎn)因子為，運(yùn)算流圖如圖4.3.4所示。

由以上例子我們可以看出，由于每一次分解都是按輸入序列在時(shí)域上的次序是偶數(shù)還是奇數(shù)來(lái)抽取的，最終分解成N個(gè)1點(diǎn)DFT，因此稱為基2時(shí)分FFT。圖4.3.4

N點(diǎn)DFT基2時(shí)分FFT運(yùn)算流圖(N=8)

2.計(jì)算量分析

對(duì)于任何一個(gè)2的整數(shù)冪N=2M，總是可以通過(guò)M次分解直到1點(diǎn)的DFT運(yùn)算。這樣的M次分解，就構(gòu)成了從x(n)到X(k)的M級(jí)運(yùn)算過(guò)程。從圖4.3.4可以看出，每一級(jí)運(yùn)算都由個(gè)蝶形運(yùn)算構(gòu)成。由于每一個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法，因此每一級(jí)分解所需的復(fù)數(shù)乘法和加法次數(shù)分別為

N點(diǎn)DFT(M級(jí)分解)所需總的復(fù)數(shù)乘法和加法次數(shù)分別為

(4.3.4)

(4.3.5)我們知道直接計(jì)算N點(diǎn)DFT需要的復(fù)數(shù)乘法為N2次，復(fù)數(shù)加法為N(N-1)次，當(dāng)N1時(shí)，基2時(shí)分FFT算法將比直接計(jì)算DFT的運(yùn)算量大大減少?；?時(shí)分算法與直接計(jì)算N點(diǎn)DFT的復(fù)數(shù)乘法次數(shù)比為

(4.3.6)復(fù)數(shù)加法次數(shù)比為

(4.3.7)若N=210，則直接計(jì)算需要的復(fù)數(shù)乘法和加法次數(shù)分別為CM=10242=1048576，CA=1024(1024-1)=1047552，基2時(shí)分需要的復(fù)數(shù)乘法和加法次數(shù)分別為CM=5120，CA=10240,復(fù)數(shù)乘法次數(shù)比為αM≈，即基2時(shí)分FFT的復(fù)數(shù)乘法運(yùn)算效率提高了約200倍。圖4.3.5顯示了直接計(jì)算DFT與基2時(shí)分FFT算法所需乘法次數(shù)的比較曲線，顯然，N越大，F(xiàn)FT算法的效率越高。圖4.3.5直接計(jì)算DFT與基2時(shí)分FFT算法所需乘法次數(shù)的比較曲線

4.2.4基2時(shí)分FFT算法的運(yùn)算規(guī)律及編程思想由基2時(shí)分FFT運(yùn)算流圖，可以看出這種算法的運(yùn)算規(guī)律。

1.原位計(jì)算

由圖4.3.4的基2時(shí)分FFT運(yùn)算流圖可以看出，同一級(jí)運(yùn)算中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一條水平線上，這就意味著計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元。這樣，經(jīng)過(guò)M級(jí)運(yùn)算后，原來(lái)存放輸入序列數(shù)據(jù)的N個(gè)存儲(chǔ)單元中便依次存放X(k)的N個(gè)值。

這種利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出數(shù)據(jù)的方法稱為原位運(yùn)算。

2.旋轉(zhuǎn)因子的變化規(guī)律

在基2時(shí)分FFT運(yùn)算流圖中，旋轉(zhuǎn)因子的變化和兩個(gè)節(jié)點(diǎn)之間的距離都呈現(xiàn)一定的規(guī)律，p稱為旋轉(zhuǎn)因子的指數(shù)。設(shè)L表示從左到右的運(yùn)算級(jí)數(shù)，即L=1，2，…，M。設(shè)N=23=8，L=1，2，3，第L級(jí)共有2L-1個(gè)不同的旋轉(zhuǎn)因子，即

L=1時(shí)，;

L=2時(shí)，;

L=3時(shí)，。

對(duì)N=2M的一般情況，L=1，2，…，M，第L級(jí)的旋轉(zhuǎn)因子為

(4.3.8)在實(shí)際編程實(shí)現(xiàn)中，旋轉(zhuǎn)因子有三種計(jì)算方法。

(1)直接計(jì)算。在用高級(jí)編程語(yǔ)言實(shí)現(xiàn)FFT，且對(duì)運(yùn)算時(shí)間沒(méi)有要求的理論分析場(chǎng)合下，

一般采用直接計(jì)算求旋轉(zhuǎn)因子。根據(jù)歐拉公式有

如果采用相同的旋轉(zhuǎn)因子計(jì)算完后存儲(chǔ)起來(lái)的辦法，則共需計(jì)算個(gè)，即N個(gè)正弦函數(shù)。

(2)遞推計(jì)算。根據(jù)旋轉(zhuǎn)因子的特點(diǎn)，即

可以利用遞推的辦法求解旋轉(zhuǎn)因子。根據(jù)上式，在每一級(jí)只需計(jì)算一個(gè)旋轉(zhuǎn)因子，其余的旋轉(zhuǎn)因子均可通過(guò)上式求出。因此N=2M點(diǎn)FFT共需計(jì)算2M個(gè)正弦函數(shù)。

(3)查表。在要求實(shí)時(shí)計(jì)算FFT的應(yīng)用場(chǎng)合，用DSP匯編或FPGA編程實(shí)現(xiàn)FFT算法時(shí)，一般用查表方法。由于N點(diǎn)基2時(shí)分FFT算法中共有個(gè)不同的旋轉(zhuǎn)因子，因此事先計(jì)算好個(gè)旋轉(zhuǎn)因子表以供查詢，可以省去計(jì)算正弦函數(shù)的時(shí)間。

3.輸入序列的逆序

基2時(shí)分FFT算法輸入序列的排序看起來(lái)似乎很亂，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種排序是

有規(guī)律的，我們稱之為比特逆序。

對(duì)于N=2M，N個(gè)順序數(shù)可以用M位二進(jìn)制數(shù)(nM-1nM-2

…n1n0)2來(lái)表示，即(n)10=(nM-1nM-2…n0)2，定義

ρM(n)=(n0n1…nM-1)2

(4.3.9)

為n的M位比特逆序數(shù)。

【例4.3.2】計(jì)算n=2，12的二進(jìn)制比特逆序數(shù)ρ4(n)。

解

造成基2時(shí)分FFT算法的輸入序列順序逆序的原因是將輸入序列x(n)按下標(biāo)n的奇偶不斷分解造成的。表4.3.1列出了N=8的自然順序數(shù)和比特逆序數(shù)。由表顯而易見(jiàn)，只要

將自然順序的二進(jìn)制數(shù)按位倒置，就能得到比特逆序數(shù)。

在實(shí)際應(yīng)用中，一般先按自然順序數(shù)將輸入序列存入存儲(chǔ)單元A(m)，m=0，1，…，N-1。

為了得到比特逆序的排列，可以通過(guò)變址運(yùn)算來(lái)完成，變址過(guò)程如圖4.3.6所示。表4.3.1N=8的自然順序數(shù)和比特逆序數(shù)圖4.3.6比特逆序的變址過(guò)程(N=8)由表4.3.1可以看出，自然順序的次序增加是在二進(jìn)制數(shù)低位加1，二進(jìn)制進(jìn)位由低向高;比特逆序的次序增加在二進(jìn)制數(shù)高位加1，進(jìn)位由高向低。因此，實(shí)際求數(shù)

n(n=0，1，2，…，N-1)的比特逆序ρM(n)步驟如下:

(1)0的比特逆序?yàn)?，因此ρM(0)=0。

(2)求n+1的逆序ρM(n+1)。如ρM(n)的二進(jìn)制數(shù)最高位為0，則將該位賦1，循環(huán)結(jié)束。

如ρM(n)的二進(jìn)制數(shù)從高位開(kāi)始數(shù)前幾位均是1，則把為1的最低位的右邊為0的位賦1，同時(shí)將為1的位賦0，循環(huán)結(jié)束。

綜合以上求比特逆序步驟和圖4.3.6，將自然順序的輸入序列通過(guò)比特逆序變址變?yōu)楸忍啬嫘蜉斎氪涡虻某绦蛄鲌D如圖4.3.7所示。圖4.3.7比特逆序程序流圖圖4.3.7所示的程序流圖是求j的逆序，同時(shí)將存儲(chǔ)單元內(nèi)自然順序排列的輸入序列變?yōu)槟嫘蚺判?，i存儲(chǔ)的是j-1的逆序數(shù)。由于j=0，N-1的逆序既是數(shù)據(jù)本身，因此程序循

環(huán)從j=1到j(luò)=N-2。s存放的是二進(jìn)制數(shù)每一位的權(quán)，每次j循環(huán)開(kāi)始，s為二進(jìn)制最高位的權(quán)。程序流圖中虛線框部分是將為1的位賦0的過(guò)程。

4.編程思路與程序流圖

觀察基2時(shí)分FFT蝶形流圖，可歸納出一些對(duì)編程有用的運(yùn)算規(guī)律：第L級(jí)運(yùn)算中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)相距2L-1個(gè)點(diǎn)，同一個(gè)旋轉(zhuǎn)因子對(duì)應(yīng)著間隔為2L點(diǎn)的2M-L個(gè)蝶形?？偨Y(jié)上述運(yùn)算規(guī)律，可以采用以下方法。首先從第一級(jí)(輸入端)開(kāi)始，逐級(jí)進(jìn)行，共進(jìn)行M級(jí)運(yùn)算。在進(jìn)行第L級(jí)運(yùn)算時(shí)，依次求出2L-1個(gè)不同的旋轉(zhuǎn)因子，每求出一個(gè)旋轉(zhuǎn)因子，就計(jì)算完它對(duì)應(yīng)的所有2M-L個(gè)運(yùn)算蝶。因此基2時(shí)分FFT程序由逆序和三重循環(huán)組成。三重循環(huán)與流圖的對(duì)應(yīng)關(guān)系為：最外層循環(huán)(循環(huán)變量為L(zhǎng))對(duì)應(yīng)蝶形流圖的級(jí)數(shù)M，中間循環(huán)(循環(huán)變量為k)對(duì)應(yīng)流圖中每一級(jí)不同旋轉(zhuǎn)因子對(duì)應(yīng)的運(yùn)算蝶數(shù)目2L-1，最內(nèi)層循環(huán)(循環(huán)變量為J)對(duì)應(yīng)每一級(jí)相同旋轉(zhuǎn)因子運(yùn)算蝶的順序，程序流圖如圖4.3.8所示，C語(yǔ)言程序見(jiàn)附錄。圖4.3.8基2時(shí)分FFT算法程序流圖

【例4.3.3】設(shè)x(n)為N點(diǎn)有限序列，N為偶數(shù)，其N點(diǎn)DFT為X(k)，試用X(k)表示如下序列的N點(diǎn)DFT。

解

(1)解法1。

(2)解法2。用基2時(shí)分蝶式運(yùn)算定理將x2(n)分解為兩個(gè)

點(diǎn)的序列x20(n)和x21(n)。

根據(jù)蝶式運(yùn)算定理有

因此有

同理，將x(n)分解為兩個(gè)點(diǎn)的序列x0(n)和x1(n)。

因?yàn)?/p>

所以

令，有

因?yàn)?/p>

所以

4.4.1基2頻分蝶式運(yùn)算定理

設(shè)序列x(n)的長(zhǎng)度為N=2M，其N點(diǎn)DFT為X(k)=DFT［x(n)］，0≤k≤N-1，按k的奇偶將X(k)分解為兩個(gè)點(diǎn)的子序列X1(k)和X2(k)。

4.4基2頻分FFT算法若x1(n)=IDFT［X1(r)］，x2(n)=IDFT［X2(r)］，0≤n≤

-1，則

(4.4.1)

(4.4.2)證明由證明過(guò)程可得，N點(diǎn)序列x(n)按式(4.4.1)和式(4.4.2)分解為兩個(gè)點(diǎn)的子序列，這兩個(gè)點(diǎn)子序列的DFT正好是N點(diǎn)DFTX(k)的偶數(shù)組和奇數(shù)組。由蝶式運(yùn)算定理可以看出，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法，計(jì)算N點(diǎn)DFT共需計(jì)算兩個(gè)點(diǎn)DFT和次蝶形運(yùn)算。計(jì)算點(diǎn)DFT需要次復(fù)數(shù)乘法和次復(fù)數(shù)加法。當(dāng)N>>1時(shí)，計(jì)算N點(diǎn)DFT共需

次復(fù)數(shù)加法。由此可見(jiàn)，僅經(jīng)過(guò)一次分解，就使運(yùn)算量減少近一半。如果N=2M，則我們可以繼續(xù)分解，直至分解

到1點(diǎn)DFT，運(yùn)算量即可大大減少。4.4.2基2頻分的蝶形流圖與計(jì)算量分析

1.蝶形流圖

基2頻分FFT蝶式運(yùn)算定理的運(yùn)算公式可以用圖4.4.1所示的信號(hào)流圖表示，一個(gè)蝶形流圖是基2頻分算法的一個(gè)基本單元。圖4.4.1DIF-FFT蝶式運(yùn)算信號(hào)流圖

【例4.4.1】將8點(diǎn)序列的DFT用基2頻分FFT算法進(jìn)行分解。

解

(1)第一次分解。

將8點(diǎn)序列x(n)通過(guò)蝶形構(gòu)造分解為兩個(gè)4點(diǎn)序列x1(n)和x2(n),分別做4點(diǎn)DFT得到X1(k)和X2(k)，即

X1(k)={X(0)，X(2)，X(4)，X(6)}

X2(k)={X(1)，X(3)，X(5)，X(7)}

由X1(k)和X2(k)獲得8點(diǎn)DFTX(k)，旋轉(zhuǎn)因子為(n=0，1，2，3)，運(yùn)算流圖如圖4.4.2所示。圖4.4.2

N點(diǎn)DFT基2頻分第一次分解運(yùn)算流圖(N=8)

(2)第二次分解。

將兩個(gè)4點(diǎn)序列分別通過(guò)蝶形構(gòu)造分解為四個(gè)2點(diǎn)序列，分別做2點(diǎn)DFT得到

由2點(diǎn)DFT即可獲得8點(diǎn)DFTX(k)，第二次分解的旋轉(zhuǎn)因子為(n=0，1)，運(yùn)算流圖如圖4.4.3所示。圖4.4.3

N點(diǎn)DFT基2頻分第二次分解運(yùn)算流圖(N=8)

(3)第三次分解。

將四個(gè)2點(diǎn)序列通過(guò)蝶形構(gòu)造分解為8個(gè)1點(diǎn)序列，其中

由于1點(diǎn)序列的DFT值為其序列本身，因此，在最后一次分解后，流圖中已經(jīng)沒(méi)有直接計(jì)算DFT的環(huán)節(jié)。第三次分解旋轉(zhuǎn)因子為，運(yùn)算流圖如圖4.4.4所示。圖4.4.4

N點(diǎn)DFT基2頻分FFT運(yùn)算流圖(N=8)由以上例子我們可以看出，由于每一次分解都是按輸入序列在頻域上的次序是偶數(shù)還是奇數(shù)來(lái)抽取的，最終分解成N個(gè)1點(diǎn)DFT，因此稱為基2頻分FFT。

2.計(jì)算量分析

對(duì)于任何一個(gè)長(zhǎng)度為2的整數(shù)冪(N=2M)序列，其DFT總是可以通過(guò)M次分解到1點(diǎn)的DFT運(yùn)算。這樣的M次分解，就構(gòu)成了從x(n)到X(k)的M級(jí)運(yùn)算過(guò)程。從圖4.4.4可以看出，每一級(jí)運(yùn)算都由個(gè)蝶形運(yùn)算構(gòu)成。由于每一個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法，因此N點(diǎn)DFT(M級(jí)分解)所需總的復(fù)數(shù)乘法和加法次數(shù)分別為

(4.4.3)

CA=NM=Nlog2N

(4.4.4)由于基2時(shí)分FFT算法和基2頻分FFT算法抽取的域不同，因此它們的蝶形構(gòu)造發(fā)生的地方、基本運(yùn)算和蝶形流圖都不相同?；?時(shí)分是時(shí)域抽取，頻域蝶形構(gòu)造，輸入逆序，輸出順序;基2頻分是頻域抽取，時(shí)域蝶形構(gòu)造，輸入順序，輸出逆序。但兩者的運(yùn)算量是相同的。具體的編程思想不再贅述。

在前面章節(jié)的學(xué)習(xí)中我們或者使用基2時(shí)分FFT算法，或者使用基2頻分FFT算法將某一個(gè)序列的DFT計(jì)算出來(lái)。下面我們舉個(gè)例子，在同一個(gè)序列中某些步驟用基2時(shí)分，某些步驟用基2頻分。

【例4.4.2】在N=8的DFT中，分兩步做快速算法，第一步用基2頻分將8點(diǎn)DFT化為兩個(gè)4點(diǎn)DFT，第二步用基2時(shí)分將這兩個(gè)4點(diǎn)DFT化為四個(gè)2點(diǎn)DFT，并畫(huà)出流圖。

解根據(jù)題目要求，第一步使用基2頻分，構(gòu)造4點(diǎn)序列x1(n)和x2(n)，其DFT分別是

X1(k)={X(0)，X(2)，X(4)，X(6)}，

X2(k)={X(1)，X(3)，X(5)，X(7)}

運(yùn)算流圖如圖4.4.5所示。圖4.4.5例4.4.2第一步基2頻分FFT第一次分解運(yùn)算流圖第二步使用基2時(shí)分，以x1(n)為例，將其按照n的奇偶分成2點(diǎn)序列x3(n)和x4(n),由2點(diǎn)DFTX3(k)和X4(k)通過(guò)蝶形運(yùn)算即可構(gòu)造出X1(k)，如圖4.4.6所示。同理可得X2(k)。

最后，將前兩步的結(jié)果合并起來(lái)，運(yùn)算流圖如圖4.4.7所示。圖4.4.6例4.4.2第二步基2時(shí)分FFT分解運(yùn)算流圖圖4.4.7例4.4.2運(yùn)算流圖長(zhǎng)度為N的有限長(zhǎng)序列x(n)的離散傅里葉變換為

(4.5.1)

其離散傅里葉逆變換為

(4.5.2)4.5IDFT的快速算法比較以上兩式，可見(jiàn)離散傅里葉變換對(duì)具有對(duì)稱性。因此可以利用DFT的快速算法(FFT)來(lái)實(shí)現(xiàn)IDFT。具體來(lái)說(shuō)，就是將FFT運(yùn)算流圖中的旋轉(zhuǎn)因子取共軛(虛部取反)，最后輸出乘以。此時(shí)，輸入為X(k)，輸出即為x(n)。前面討論的序列x(n)的DFT快速算法都是復(fù)數(shù)運(yùn)算，包括序列x(n)也認(rèn)為是復(fù)數(shù)。在實(shí)際應(yīng)用中，信號(hào)有可能是實(shí)序列，任何實(shí)數(shù)都可看成虛部為零的復(fù)數(shù)。例如，求某實(shí)信號(hào)x(n)的頻譜，可認(rèn)為是將實(shí)信號(hào)加上數(shù)值為零的虛部變成復(fù)信號(hào)(x(n)+j0)，再用FFT求其離散傅里葉變換。這種做法很不經(jīng)濟(jì)，因?yàn)榘褜?shí)序列變成復(fù)序列，存儲(chǔ)器要增加一倍，且計(jì)算機(jī)運(yùn)行時(shí)，即使虛部為零，也要進(jìn)行涉及虛部的運(yùn)算，浪費(fèi)了運(yùn)算量。

合理的解決方法是利用復(fù)數(shù)FFT對(duì)實(shí)數(shù)進(jìn)行有效計(jì)算。4.6實(shí)序列DFT的有效計(jì)算方法

1.一個(gè)N點(diǎn)FFT同時(shí)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的DFT

【例4.6.1】設(shè)x1(n)和x2(n)是彼此獨(dú)立的兩個(gè)N點(diǎn)實(shí)序列，且X1(k)=DFT［x1(n)］，X2(k)=DFT［x2(n)］。

試通過(guò)一次FFT運(yùn)算同時(shí)求得X1(k)和X2(k)。

解首先將x1(n)和x2(n)分別作為一個(gè)N點(diǎn)復(fù)序列x(n)的實(shí)部及虛部，即

x(n)=x1(n)+jx2(n)通過(guò)調(diào)用一個(gè)N點(diǎn)的FFT算法即可獲得x(n)的DFT序列X(k)。

利用離散傅里葉變換的共軛對(duì)稱性可獲得X1(k)和X2(k)，即

下面分析計(jì)算量。通過(guò)調(diào)用N點(diǎn)FFT算法求X(k)需要的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

根據(jù)X(k)求X1(k)和X2(k)需要的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

CM2=N-1，CA2=2(N-1)

因此，該方法總共需要的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

如果調(diào)用兩次N點(diǎn)FFT算法直接計(jì)算X1(k)和X2(k)，所需的運(yùn)算量為

CM=Nlog2N，CA=2Nlog2N

設(shè)N=1024，則直接調(diào)用兩次FFT計(jì)算需要的CM=10240，CA=20480。利用上述算法則有CM=6143，CA=12286，計(jì)算量減少近半。

2.一個(gè)N點(diǎn)FFT計(jì)算一個(gè)2N點(diǎn)實(shí)序列的DFT

【例4.6.2】設(shè)x(n)是2N點(diǎn)的實(shí)序列，試設(shè)計(jì)用一次N點(diǎn)的FFT算法完成計(jì)算X(k)的高效算法。

解將x(n)分解為偶數(shù)序列x1(n)和奇數(shù)序列x2(n)，即

x1(n)=x(2n)，n=0，1，…，N-1

x2(n)=x(2n+1)，n=0，1，…，N-1將x1(n)和x2(n)分別作為一個(gè)N點(diǎn)復(fù)序列y(n)的實(shí)部及虛部，即

y(n)=x1(n)+jx2(n)

通過(guò)N點(diǎn)FFT運(yùn)算可得到y(tǒng)(n)的N點(diǎn)DFTY(k)，根據(jù)前面的討論可得

根據(jù)基2時(shí)分蝶式運(yùn)算定理得

下面分析計(jì)算量。通過(guò)調(diào)用N點(diǎn)FFT算法求Y(k)需要的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

根據(jù)Y(k)求X1(k)和X2(k)需要的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

CM2=N-1，

CA2=2(N-1)

利用基2時(shí)分蝶式運(yùn)算定理求X(k)需要的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

CM3=N，

CA3=2N因此，該方法總共需要的復(fù)數(shù)乘法次數(shù)和復(fù)數(shù)加法次數(shù)分別為

直接計(jì)算2N點(diǎn)FFT計(jì)算量為

CM=Nlog22N，

CA=2Nlog22N

設(shè)N=1024，則直接計(jì)算CM=11264，CA=22528。

利用上述算法則有CM=7167，CA=14334。前面已經(jīng)介紹過(guò)，采用FFT算法可以很快計(jì)算出全部N點(diǎn)DFT值，即Z變換X(z)在z平面單位圓上的全部等間隔取樣值。而實(shí)際中也許不需要計(jì)算整個(gè)單位圓上Z變換的取樣值。例如對(duì)于窄帶信號(hào)，只需要對(duì)信號(hào)所在的一段頻帶進(jìn)行分析，這時(shí)希望頻譜的取樣集中在這一頻帶內(nèi)，以獲得較高的分辨率，而頻帶以外的部分可不考慮。另外，實(shí)際中有時(shí)也對(duì)非

單位圓上的取樣值感興趣。4.7線性調(diào)頻Z(Chirp-Z)變換算法例如需要知道Z變換的極點(diǎn)所在處的頻率，如極點(diǎn)位置離單位圓較遠(yuǎn)，則其單位圓上的頻譜就很平滑，這時(shí)很難從中識(shí)別出極點(diǎn)所在處的頻率，此時(shí)，如果取樣不是沿單位圓而是沿一條接近這些極點(diǎn)的弧線進(jìn)行，則極點(diǎn)所在頻率上的頻譜將出現(xiàn)明顯的尖峰，由此可較準(zhǔn)確地測(cè)定極點(diǎn)頻率。

Z變換采用螺旋線取樣是一種適合于以上需要的變換，且可以采用FFT來(lái)快速計(jì)算，這種變換也稱做線性調(diào)頻Z變換(也稱Chirp-Z變換或CZT)，它是適用于這種更為一般情況下由x(n)求X(zk)的快速算法。4.7.1Chirp-Z變換的基本原理

已知x(n)(0≤n≤N-1)為有限長(zhǎng)序列，其Z變換為

(4.7.1)

為適應(yīng)z可以沿z平面上的一段螺旋線做等分角的取樣，令z的取樣點(diǎn)為

zk=AW-k，k=0，1，…，M-1

(4.7.2)其中，M為所要分析的復(fù)頻譜的點(diǎn)數(shù)(不一定等于N);A和W是任意復(fù)數(shù)，可表示為

(4.7.3)

(4.7.4)圖4.7.1CZT在z平面的螺旋線取樣將式(4.7.3)和式(4.7.4)帶入式(4.7.2)中，可得

(4.7.5)

有

取樣點(diǎn)在z平面上所沿的周線如圖4.7.1所示。由以上討論及圖可見(jiàn):

(1)A0表示起始取樣點(diǎn)的矢量半徑長(zhǎng)度，通常A0≤1，否則z0將處于單位圓外。

(2)ω0表示起始取樣點(diǎn)z0的相角，可以是正值也可以是負(fù)值。

(3)φ0表示兩相鄰取樣點(diǎn)之間的等分角度，φ0為正，表示zk的路徑是逆時(shí)針旋轉(zhuǎn)的;φ0為負(fù)，表示zk的路徑是順時(shí)針旋轉(zhuǎn)的。

(4)W0的大小表示螺旋線的伸展率，當(dāng)W0<1時(shí)，隨著k的增加螺旋線外伸;當(dāng)W0>1時(shí),隨著k的增加螺旋線內(nèi)縮；W0=1表示半徑為A0的一段圓弧，若A0=1，這段圓弧則是單位圓的一部分。當(dāng)

時(shí)，各個(gè)zk均勻等間隔地分布在單位圓上，此時(shí)CZT即為DFT。

將式(4.7.2)中的zk代入Z變換表達(dá)式(4.7.1)中，可得

(4.7.6)

顯然，同直接計(jì)算DFT情況相仿，按照式(4.7.6)計(jì)算出全部M點(diǎn)取樣值需要NM次復(fù)數(shù)乘法和(N-1)M次復(fù)數(shù)加法，當(dāng)N及M較大時(shí)，計(jì)算量迅速增加。如果通過(guò)一定的變換，如采用布魯斯坦(Bluestein)等式，將以上運(yùn)算轉(zhuǎn)換為卷積形式，則可采用FFT進(jìn)行，這樣即可大大提高計(jì)算速度。布魯斯坦等式為

(4.7.7)將上式代入式(4.7.6)，可得

令

(4.7.8)

(4.7.9)

則有

(4.7.10)式(4.7.10)說(shuō)明，如對(duì)信號(hào)x(n)先進(jìn)行一次加權(quán)處理，加權(quán)系數(shù)為，然后通過(guò)一個(gè)單位脈沖響應(yīng)為h(n)的線性時(shí)不變系統(tǒng)，最后對(duì)該系統(tǒng)的前M點(diǎn)輸出再作一次的加權(quán)，就可得到全部M點(diǎn)螺旋線取樣值。運(yùn)算流程如圖4.7.2所示。圖4.7.2線性調(diào)頻Z變換運(yùn)算流程由于系統(tǒng)的單位脈沖響應(yīng)與頻率隨時(shí)間成線性增加的線性調(diào)頻信號(hào)(即ChirpSignal)相似，因此這種算法稱為Chirp-Z變換。

4.7.2Chirp-Z變換的實(shí)現(xiàn)步驟

由式(4.7.10)可以看出，由于輸入信號(hào)g(n)是長(zhǎng)度為N的有限長(zhǎng)序列，序列是無(wú)限長(zhǎng)的，而計(jì)算0~M-1點(diǎn)卷積g(k)*h(k)所需要的h(n)是取值在n=-(N-1)~(M-1)那一部分的值，如圖4.7.3(a)所示。因此，可認(rèn)為h(n)是一個(gè)有限長(zhǎng)序列，長(zhǎng)度為L(zhǎng)=N+M-1。所以，Chirp-Z變換為兩個(gè)有限長(zhǎng)序列的線性卷積

g(k)*h(k),可用循環(huán)卷積通過(guò)FFT來(lái)實(shí)現(xiàn)，即

g(k)*h(k)=IDFT［G(r)H(r)］根據(jù)第3章所學(xué)知識(shí)，g(k)*h(k)的長(zhǎng)度為2N+M-2，因而用循環(huán)卷積求線性卷積時(shí)，循環(huán)卷積的長(zhǎng)度最短為2N+M-2。由于我們只需要求0~M-1處的線性卷積結(jié)果，因此選循環(huán)卷積的長(zhǎng)度為兩個(gè)序列中最長(zhǎng)的長(zhǎng)度，即L=N+M-1點(diǎn)。另外，h(n)的主值序列(0≤n≤L-1)可由h(n)作周期延拓后取0≤n≤L-1部分值獲得，如圖4.7.3(b)所示。

將h(n)與g(n)作循環(huán)卷積后，其輸出的前M個(gè)值就是CZT的M個(gè)值。這個(gè)循環(huán)卷積的過(guò)程可在頻域上通過(guò)FFT實(shí)現(xiàn)。圖4.7.3

h(n)的主值序列求解過(guò)程總之，CZT運(yùn)算步驟如下：

(1)選擇一個(gè)最小整數(shù)L，使其滿足L≥N+M-1，同時(shí)滿足L=2m，以便采用基2FFT算法。

(2)對(duì)x(n)加權(quán)并補(bǔ)零得到g(n)：

(4.7.11)并利用FFT算法求此序列的L點(diǎn)DFTG(r)。

(4.7.12)

(3)求h(n)的主值序列:

(4.7.13)并利用FFT算法求此序列的L點(diǎn)DFTHm(r):

(4.7.14)

(4)將Hm(r)和G(r)相乘，得到Q(r)=G(r)Hm(r)。

(5)用FFT算法求L點(diǎn)Q(r)的IDFT，得到hm(n)與g(n)的循環(huán)卷積。

(4.7.15)其中，q(n)的前M-1點(diǎn)等于h(n)與g(n)的線性卷積結(jié)果(與第3章所講的線性卷積與循環(huán)卷積的關(guān)系不同，這里的hm(n)是h(n)以L為周期延拓后的主值序列)。

(6)求X(zk):

(4.7.16)4.7.3Chirp-Z變換運(yùn)算量的估算

采用上小節(jié)的算法后，CZT所需的運(yùn)算量如下:

(1)形成L點(diǎn)序列，由于補(bǔ)零關(guān)系，

g(n)只有N點(diǎn)有序列值，需要N次復(fù)數(shù)乘法。系數(shù)可以通過(guò)遞推求得。令

則

初始條件。

因此通過(guò)遞推求Cn需要2N次復(fù)數(shù)乘法。

(2)形成L點(diǎn)序列hm(n)，由于它是由在

-N+1≤n≤M-1段內(nèi)的序列值構(gòu)成的，是偶對(duì)稱序列，如果設(shè)N≥M，則只需求0≤n≤N-1段內(nèi)的N點(diǎn)序列值。求

也可以用遞推方式求解，因此需要復(fù)數(shù)乘法2N次。

(3)計(jì)算Hm(r)、G(r)和q(n)共需要3次L點(diǎn)FFT算法，因此需要復(fù)數(shù)乘法次數(shù)為。

(4)計(jì)算Q(r)=G(r)Hm(r)需要L次復(fù)數(shù)乘法。

(5)計(jì)算X(zk)=，0≤k≤M-1需要M次復(fù)數(shù)乘法。綜上所述，Chirp-Z變換總共需要的復(fù)數(shù)乘法次數(shù)為

(4.7.17)

前面討論過(guò)直接計(jì)算X(zk)需要復(fù)數(shù)乘法為NM次，當(dāng)N=925，M=100時(shí)，直接計(jì)算需要CM=92500次，采用快速算法后所需的復(fù)數(shù)乘法次數(shù)為CM=21109，計(jì)算量減少較多。總之，與DFT相比，CZT有以下特點(diǎn)：

(1)輸入序列的長(zhǎng)度N與輸出序列的長(zhǎng)度M不需要相等；(2)N及M不必是合成數(shù)，二者均可為素?cái)?shù)；

(3)zk點(diǎn)的角度間隔φ0是任意的，因此頻率分辨率也是任意的；

(4)周線不必是z平面上的圓；

(5)起始點(diǎn)z0可任意選定，因此可以從任意頻率上開(kāi)始對(duì)輸入數(shù)據(jù)進(jìn)行窄帶高分辨率分析；

(6)若A=1，M=N，即使N為素?cái)?shù)，也可用Chirp-Z變換計(jì)算DFT。4.7.4用Matlab計(jì)算Chirp-Z變換

Matlab信號(hào)處理工具箱提供了內(nèi)部函數(shù)czt用于實(shí)現(xiàn)Chirp-Z變換，調(diào)用格式如下：

y=czt(x，M，W，A);

y=czt(x);

y=czt(x，M，W，A)用于計(jì)算指定參數(shù)M、W、A下的Chirp-Z變換，而y=czt(x)則使用默認(rèn)參數(shù)進(jìn)行Chirp-Z變換，默認(rèn)參數(shù)為M=length(x)，W=exp(j*2*pi/m)，A=1，此時(shí)即計(jì)算DFT。

【例4.7.1】某一低通濾波器的零、極點(diǎn)分布如圖4.7.4所示，利用Chirp-Z變換觀察濾波器零點(diǎn)特性。

clear；fs=2000; ％采樣頻率為2000Hz

fp=150；

p1=0.9*exp(-j*2*pi*fp/fs);

p2=p1′;p=［p1，p2］′; ％極點(diǎn)在150Hz處

fz1=500;

fz2=300;

z1=1.2*exp(-j*2*pi*fz1/fs)；z2=z1′;

z3=1.2*exp(-j*2*pi*fz2/fs);z4=z3′;圖4.7.4濾波器零、極點(diǎn)分布圖

z=［z1，z2z3z4］′;

％零點(diǎn)在300Hz和500Hz處的單位圓外，半徑為1.2

［b，a］=zp2tf(z，p，1);

ww=0：0.005*pi：2*pi;

h1=freqz(b，a，ww);

hn1=ifft(h1);hn=real(hn1)；

N=length(ww)； ％濾波器單位脈沖響應(yīng)長(zhǎng)度(401點(diǎn))

f2=700;f1=50；M=201；

W=exp(-j*2*pi*(f2-f1)/(M*fs));

％在z平面ω=2πf1~2πf2之間取M點(diǎn)

A=1.19*exp(j*2*pi*f1/fs); ％取樣圓弧半徑為1.19

yzz=czt(hn，M，W，A); ％求CZT由于零點(diǎn)在單位圓外，半徑為1.2處，因此CZT的圓弧線半徑為1.19，起始點(diǎn)ω=2π×50,終止點(diǎn)為ω=2π×700，取樣點(diǎn)數(shù)為201點(diǎn)，如圖4.7.5所示。濾波器單位圓上的幅頻響應(yīng)如圖4.7.6所示，由于單位圓距離零點(diǎn)較遠(yuǎn)，兩個(gè)零點(diǎn)處的頻率在幅頻響應(yīng)里不明顯。由于CZT取樣曲線接近零點(diǎn)，因此在300Hz和500Hz處的頻率在CZT中非常明顯，CZT如圖4.7.7所示。由于CZT的取樣圓弧離極點(diǎn)位置較遠(yuǎn)，因此極點(diǎn)處的頻率在CZT曲線中已不明顯。圖4.7.5CZT取樣螺旋線圖圖4.7.6濾波器幅頻響應(yīng)圖圖4.7.7濾波器CZT圖用Matlab按快速算法的實(shí)現(xiàn)步驟編寫的CZT程序如下(參數(shù)設(shè)置與上相同):

L=M+N-1;

gn=zeros(1，L);

gn(1：N)=A.^(-(0：N-1)).*W.^((0：N-1).^2./2).*hn;

gf=fft(gn，L);

hhn(1：M)=W.^(-(0：M-1).^2./2);

hhn(M+1：L)=W.^(-(L-(M：L-1)).^2./2);

hhnf=fft(hhn);

Qr=hhnf.*gf;

qn=ifft(Qr);

yzz=qn(1：M).*W.^((0：M-1).^2./2)

【例4.7.2】設(shè)信號(hào)為x(n)，它由4個(gè)頻率分別為60Hz、64Hz、95Hz和100Hz的正弦序列組合而成。采樣頻率為600Hz，樣點(diǎn)數(shù)為200點(diǎn)。試用CZT觀察信號(hào)頻譜。

解為比較起見(jiàn)，分別用200點(diǎn)的DFT和CZT觀察信號(hào)頻譜。

圖4.7.8所示為x(n)的DFT，由于點(diǎn)數(shù)太少，60Hz與64Hz、95H