數(shù)字信號(hào)處理（第2版）課件 第4章-快速傅里葉變換（FFT）

1第4章快速傅里葉變換（FFT）4.5FFT算法的應(yīng)用4.3按頻率抽?。―IF）的基2-FFT算法4.2按時(shí)間抽?。―IT）的基2–FFT算法4.1DFT的運(yùn)算量分析4.4線性調(diào)頻z變換（Chirp-z）算法4.6FFT的MATLAB實(shí)現(xiàn)24.1DFT的運(yùn)算量分析一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列x[n]的DFT為由于x[n]可為復(fù)數(shù)，則直接計(jì)算DFT量需要復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X[k]N次N-1次N個(gè)X[k]N2次N(N-1)

次34.1DFT的運(yùn)算量分析若用實(shí)數(shù)運(yùn)算來(lái)完成DFT，則有

每個(gè)復(fù)數(shù)乘法需要4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法，并且每個(gè)復(fù)數(shù)加法需要2次實(shí)數(shù)加法。因此實(shí)數(shù)乘法實(shí)數(shù)加法一個(gè)X[k]4N次4N-2次N個(gè)X[k]4N2次N(4N-2)

次44.1DFT的運(yùn)算量分析N

復(fù)乘

復(fù)加1625624032102499264409640321281638416256

102410485761047552

如果每次復(fù)數(shù)乘法需要100us，每次復(fù)數(shù)加法需要20us，來(lái)計(jì)算N=1024點(diǎn)DFT，則需要54.1DFT的運(yùn)算量分析利用了系數(shù)WNkn的對(duì)稱性和周期性來(lái)改善DFT計(jì)算效率對(duì)稱性2.周期性合并n和（N-n）項(xiàng)

：64.1DFT的運(yùn)算量分析且

其他項(xiàng)可做類似的合并，這樣，乘法的次數(shù)大概可以減少1/2。但仍面臨著正比于N2的大量計(jì)算。

離散傅里葉變換的高效運(yùn)算方法都稱為快速傅里葉變換，即FFT。FFT算法的基本思想是將一個(gè)長(zhǎng)度為N的序列，依次分解為若干較短序列，充分利用DFT計(jì)算中的系數(shù)WNkn的周期性和對(duì)稱性，將這些短序列對(duì)應(yīng)的DFT進(jìn)行適當(dāng)?shù)慕M合，達(dá)到減少運(yùn)算量的目的。74.2按時(shí)間抽取（DIT）的基2–FFT算法4.2.1

算法原理

設(shè)x[n]點(diǎn)數(shù)為

，其中

為整數(shù)，即N為2的整數(shù)冪，若不滿足，可以補(bǔ)零來(lái)達(dá)到，這種FFT也稱基2–FFT。84.2按時(shí)間抽?。―IT）的基2–FFT算法由于94.2按時(shí)間抽取（DIT）的基2–FFT算法式中利用系數(shù)的周期性同理104.2按時(shí)間抽?。―IT）的基2–FFT算法由此(4.2-8)再考慮系數(shù),則,上式可以寫作(4.2-9)114.2按時(shí)間抽取（DIT）的基2–FFT算法圖4.2-1時(shí)間抽取蝶形運(yùn)算結(jié)構(gòu)

可見(jiàn)，每一個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法

及兩次復(fù)數(shù)加法運(yùn)算。12例圖4.2-2按時(shí)間抽取，將一個(gè)N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT計(jì)算的信號(hào)流圖134.2按時(shí)間抽?。―IT）的基2–FFT算法同理144.2按時(shí)間抽取（DIT）的基2–FFT算法將系數(shù)統(tǒng)一為,則可得圖4.2-4

將一個(gè)N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)DFT計(jì)算的信號(hào)流圖154.2按時(shí)間抽?。―IT）的基2–FFT算法2點(diǎn)序列的DFT164.2按時(shí)間抽?。―IT）的基2–FFT算法圖4.2-6按時(shí)間抽取，輸入倒位序、輸出自然順序的8點(diǎn)FFT流圖174.2按時(shí)間抽取（DIT）的基2–FFT算法4.2.2

DIT—FFT算法特點(diǎn)1.蝶形結(jié)構(gòu)運(yùn)算次分解，就構(gòu)成

級(jí)運(yùn)算過(guò)程。圖中，m表示第m級(jí)蝶形運(yùn)算，

。2.運(yùn)算量每一個(gè)蝶形需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法。184.2按時(shí)間抽取（DIT）的基2–FFT算法N點(diǎn)的DIT-FFT計(jì)算量為復(fù)數(shù)乘法：復(fù)數(shù)加法：例：

如果每次復(fù)數(shù)乘法需要100us，每次復(fù)數(shù)加法需要20us，來(lái)計(jì)算N=1024點(diǎn)DFT，則需要直接運(yùn)算則需要125.809s。194.2按時(shí)間抽?。―IT）的基2–FFT算法--------輸入信號(hào)上節(jié)點(diǎn);--------輸入信號(hào)下節(jié)點(diǎn);--------輸出信號(hào)上節(jié)點(diǎn);--------輸出信號(hào)下節(jié)點(diǎn);j=i+dm

dm--------第m級(jí)的蝶距;sm--------第m級(jí)的蝶形組數(shù);--------蝶形結(jié)構(gòu)的W因子。20m12…v-1v12……

N/2N/4…214.2按時(shí)間抽?。―IT）的基2–FFT算法214.2按時(shí)間抽取（DIT）的基2–FFT算法例：若N=64，問(wèn)第4級(jí)的中有幾組蝶形運(yùn)算流圖？每組有多少

基本蝶形？并確定該級(jí)的權(quán)系數(shù)的種類。(1)(2)(每組8個(gè)基本蝶形)(3)或解：224.2按時(shí)間抽取（DIT）的基2–FFT算法3.原位運(yùn)算

按時(shí)間抽取FFT算法流圖中，可以看出每一級(jí)的蝶形運(yùn)算的輸入數(shù)據(jù)與以后的運(yùn)算無(wú)關(guān)，因而不需要保留。在蝶形運(yùn)算中，每一個(gè)輸出數(shù)據(jù)Xm[l]可以直接存放在原來(lái)存儲(chǔ)輸入數(shù)據(jù)Xm-1[l]的單元中，即每一級(jí)蝶形運(yùn)算輸入和輸出都存儲(chǔ)在同一地址的存儲(chǔ)單元中，這就稱為原位（或同址）運(yùn)算。原位運(yùn)算只需要N個(gè)復(fù)數(shù)的存儲(chǔ)單元，節(jié)省了大量的存儲(chǔ)單元。234.2按時(shí)間抽?。―IT）的基2–FFT算法4.序數(shù)重排FFT的輸出是按先后自然順序排列的，而輸入數(shù)據(jù)不是按照自然順序，而是按倒位序排列的。

倒位序，首先將序號(hào)n用二進(jìn)制碼表示（如n2n1n0），然后將該二進(jìn)制倒位，形成倒位序二進(jìn)制數(shù)（n0n1n2），最后再將倒位序二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)。例：N=8，采用三位二進(jìn)制碼表示，n=6=(110)

2倒位序的二進(jìn)制為

：(011)

2=6244.2按時(shí)間抽取（DIT）的基2–FFT算法十進(jìn)制數(shù)二進(jìn)制數(shù)倒位序二進(jìn)制數(shù)倒位序順序0000000010011004201001023011110641000011510110156110011371111117表4.1自然順序和二進(jìn)制倒位序254.2按時(shí)間抽?。―IT）的基2–FFT算法5.系數(shù)WNr的確定

對(duì)

點(diǎn)的DIT-FFT運(yùn)算來(lái)講，第

級(jí)運(yùn)算，用N/2點(diǎn)的DFT合成N點(diǎn)DFT，系數(shù)因子用

；第

級(jí)運(yùn)算，用N/4合成N/2點(diǎn)DFT，系數(shù)因子用

；第

級(jí)運(yùn)算，用N/8合成N/4點(diǎn)DFT，系數(shù)因子用

；依此類推，可得所有m級(jí)運(yùn)算的系數(shù)因子。-1-1-1-1-1-1-1-1X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]X[8]X[9]X[10]X[11]X[12]X[13]X[14]X[15]-1-1-1-1-1-1-1-1WN3WN0WN1WN2WN4WN5WN6WN7-1-1-1-1-1-1-1-1WN0WN2WN4WN6WN0WN2WN4WN6-1-1-1-1-1-1-1-1WN0WN4WN0WN4WN0WN4WN0WN4x[0]x[8]x[4]x[12]x[2]x[10]x[6]x[14]x[1]x[9]x[5]x[13]x[3]x[11]x[7]x[15]WN0WN0WN0WN0WN0WN0WN0WN026274.2按時(shí)間抽取（DIT）的基2–FFT算法4.2.3按時(shí)間抽取FFT算法的其他形式流圖圖4.2-8按時(shí)間抽取，輸入自然順序、輸出倒位序的8點(diǎn)FFT流圖284.3按頻率抽?。―IF）的基2–FFT算法4.3.1

算法原理28

仍設(shè)x[n]點(diǎn)數(shù)為

，

為整數(shù)，N為2的整數(shù)冪，首先將時(shí)間序列x[n]按n的順序分為前后兩部分，得。因分別計(jì)算偶序號(hào)頻率樣本X[2r]和奇序號(hào)頻率樣本X[2r+1]294.3按頻率抽?。―IF）的基2–FFT算法由于304.3按頻率抽?。―IF）的基2–FFT算法類似由于則314.3按頻率抽?。―IF）的基2–FFT算法令有圖4.3-1頻率抽取蝶形運(yùn)算結(jié)構(gòu)324.3按頻率抽取（DIF）的基2–FFT算法圖4.3-2按頻率抽取，將一個(gè)N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT計(jì)算的信號(hào)流圖334.3按頻率抽?。―IF）的基2–FFT算法圖4.3-3

將一個(gè)N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)DFT計(jì)算的信號(hào)流圖344.3按頻率抽?。―IF）的基2–FFT算法圖4.3-4按頻率抽取，輸入自然順序、輸出倒位序的8點(diǎn)FFT流圖354.3按頻率抽?。―IF）的基2–FFT算法4.3.2

DIF—FFT算法特點(diǎn)1.蝶形結(jié)構(gòu)運(yùn)算2.運(yùn)算量每一個(gè)蝶形需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法。次分解，就構(gòu)成

級(jí)運(yùn)算過(guò)程。364.3按頻率抽?。―IF）的基2–FFT算法N點(diǎn)的DIF-FFT計(jì)算量為復(fù)數(shù)乘法：復(fù)數(shù)加法：3.原位運(yùn)算

按頻率抽取FFT算法流圖仍是原位運(yùn)算，每一級(jí)蝶形的輸入和輸出在運(yùn)算前后可以存儲(chǔ)在同一地址的存儲(chǔ)單元中。4.序數(shù)重排

按頻率抽取FFT算法的輸入是自然順序，而輸出是按位反轉(zhuǎn)的倒位序?？梢?jiàn)，按頻率抽取的FFT算法和按時(shí)間抽取的FFT算法是兩種等價(jià)的FFT運(yùn)算。374.3按頻率抽取（DIF）的基2–FFT算法5.系數(shù)WNr的確定

對(duì)

點(diǎn)的DIF-FFT運(yùn)算來(lái)講，第1級(jí)運(yùn)算，將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)的DFT，系數(shù)因子

；第2級(jí)運(yùn)算，將N/2點(diǎn)DFT分解為兩個(gè)N/4點(diǎn)的DFT進(jìn)行計(jì)算，系數(shù)因子

；第3級(jí)運(yùn)算，將N/4點(diǎn)DFT分解為兩個(gè)N/8點(diǎn)的DFT，系數(shù)因子

；依此類推，可得所有m級(jí)運(yùn)算的系數(shù)因子。38m12…v-1v12……N/2N/4…214.3按頻率抽?。―IF）的基2–FFT算法394.3按頻率抽?。―IF）的基2–FFT算法4.3.3按頻率抽取FFT算法的其他形式流圖圖4.3-6按頻率抽取，輸入倒位序、輸出自然順序的8點(diǎn)FFT流圖404.4線性調(diào)頻z變換（Chirp-z）算法4.4.1算法原理設(shè)N點(diǎn)序列x[n]，其z變換為對(duì)z變換在單位圓上采樣，即DFT沿著z平面上的一條螺線作等分角取樣，各取樣點(diǎn)zk

為這里M為任意整數(shù)，A為起始點(diǎn)位置，表示為

。414.3線性調(diào)頻z變換（Chirp-z）算法參數(shù)螺線內(nèi)縮螺線外伸一段圓弧表示螺旋線上相鄰兩抽樣點(diǎn)之間的等分角。——序列x[n]的線性調(diào)頻z變換424.3線性調(diào)頻z變換（Chirp-z）算法4.4.2線性調(diào)頻z變換的快速算法利用布魯斯坦等式令則434.3線性調(diào)頻z變換（Chirp-z）算法交換變量k和n，相當(dāng)于序列g(shù)[n]與h[n]卷積，然后再乘以,得，角頻率

隨時(shí)間n線性增長(zhǎng)，稱為Chirp信號(hào)444.5FFT算法的應(yīng)用4.5.1

用FFT計(jì)算IDFT直接利用FFT的算法再次取共軛，有454.5FFT算法的應(yīng)用IFFT實(shí)現(xiàn)步驟是：1.對(duì)X[k]取共軛，即虛部乘以-1，得到

；2.利用FFT程序計(jì)算；3.再對(duì)運(yùn)算結(jié)果取一次共軛變換，并乘以常數(shù)

，

即可得到x[n]。464.5FFT算法的應(yīng)用4.5.2

實(shí)序列的DFT計(jì)算（1）用一次N點(diǎn)FFT計(jì)算兩個(gè)長(zhǎng)度為N的實(shí)序列的N點(diǎn)DFT

序列x[n]和y[n]是長(zhǎng)度為N的實(shí)序列，要求一次N點(diǎn)FFT求兩個(gè)實(shí)序列的DFTX[k]和Y[k]。1.構(gòu)成復(fù)序列2.對(duì)g[n]進(jìn)行一次N點(diǎn)FFT運(yùn)算3.利用DFT的圓周共軛對(duì)稱性474.5FFT算法的應(yīng)用（2）用一次N點(diǎn)FFT計(jì)算一個(gè)長(zhǎng)度為2N的實(shí)序列的2N點(diǎn)DFT

令v[n]是長(zhǎng)度為2N的實(shí)序列，將其偶數(shù)序號(hào)和奇數(shù)序號(hào)的樣本值分別組成兩個(gè)N點(diǎn)的實(shí)序列，即

根據(jù)上例，由x[r]和y[r]構(gòu)成復(fù)序列g(shù)[n]，再對(duì)g[n]進(jìn)行一次N點(diǎn)FFT運(yùn)算，由圓周共軛對(duì)稱性求出x[r]和y[r]的N點(diǎn)DFTX[k]和Y[k]。則v[n]的2N點(diǎn)DFTV[k]為：484.5FFT算法的應(yīng)用即類似于按時(shí)間抽取的FFT算法494.5FFT算法的應(yīng)用4.5.3

用FFT實(shí)現(xiàn)線性卷積（1）線性卷積的FFT實(shí)現(xiàn)流程圖

若某FIR數(shù)字濾波器的單位樣值響應(yīng)為h[n]，，輸入信號(hào)為x

[n]，，系統(tǒng)的輸出

當(dāng)圓周卷積和的點(diǎn)數(shù)N滿足圖4.5-1兩個(gè)有限長(zhǎng)序列線性卷積的FFT實(shí)現(xiàn)框圖504.5FFT算法的應(yīng)用（2）有限長(zhǎng)序列和無(wú)限長(zhǎng)序列的線性卷積當(dāng)輸入信號(hào)x

[n]是無(wú)限長(zhǎng)的，或者比單位樣值響應(yīng)h[n]長(zhǎng)得多，可采用分段卷積的方法，將x

[n]分割成與h[n]長(zhǎng)度相當(dāng)?shù)亩?，再?duì)信號(hào)進(jìn)行分段卷積處理，有兩種分段卷積的處理方法：重疊相加法和重疊保留法。重疊相加法設(shè)h[n]長(zhǎng)度為N2，將x[n]分解成長(zhǎng)度為N1的段，兩者數(shù)量級(jí)相當(dāng)xi[n]表示x[n]的第i段514.5FFT算法的應(yīng)用圖4.5-2輸入信號(hào)及其分段524.5FFT算法的應(yīng)用x[n]和h[n]的線性卷積為其中53圖4.5-3重疊相加法示意圖544.5FFT算法的應(yīng)用重疊相加法用FFT實(shí)現(xiàn)的步驟，1.h[n]補(bǔ)零，至N點(diǎn)，即：2.將x[n]分段，第i段xi[n]補(bǔ)零，至N點(diǎn)，3.分別求出xi[n]和h[n]的N點(diǎn)DFT，由FFT算法實(shí)現(xiàn)

5.N點(diǎn)IDFT，由IFFT算法實(shí)現(xiàn)，6.重疊部分相加：4.554.5FFT算法的應(yīng)用重疊保留法仍將x[n]分為長(zhǎng)N1的段xi[n]，不同點(diǎn)在于，不在末端補(bǔ)零，而是在每一段序列前端補(bǔ)上前一段序列的(N2-1)點(diǎn)，組成(N1

+N2-1)點(diǎn)的序列。第一段的數(shù)據(jù)前應(yīng)該補(bǔ)上(N2-1)個(gè)零值點(diǎn)。

一個(gè)(N1+N2-1

)點(diǎn)的序列與一個(gè)N2點(diǎn)的序列做(N=

N1+N2-1)點(diǎn)的圓周卷積時(shí)，其結(jié)果中的前(N2-1)個(gè)點(diǎn)是混疊部分，而其余點(diǎn)與線性卷積相同。由此重疊保留法即將輸入段xi[n]和h[n]的圓周卷積舍掉前(N2-1)個(gè)點(diǎn)，將各相鄰段留下來(lái)的樣本銜接起來(lái)，就構(gòu)成了最終的輸出。56圖4.5-5重疊保留法示意圖574.6FFT的MATLAB實(shí)現(xiàn)Matlab為計(jì)算離散快速傅里葉變換，提供了一系列豐富的數(shù)學(xué)函數(shù)，主要有fft，ifft，fft2，ifft2，fftn，ifftn和fftshift，ifftshift等。例4.6-1已知：

和。試用Matalb實(shí)現(xiàn)由DFT計(jì)算兩個(gè)序列的循環(huán)卷積，并討論什么情況下，可以得到線性卷積結(jié)果。解：線性卷積584.6FFT的MATLAB實(shí)現(xiàn)x1=[2,