數(shù)字信號處理-課件 第5章 FFT快速傅氏變換

第5章FFT快速傅氏變換22十二月2024§5-6線性卷積的FFT算法§5-4DIF的FFT算法§5-5IFFT算法§5-2DFT的運算量及改進的途徑§5-1引言點擊進入目錄§5-3按時間抽取(DIT)的FFT算法22十二月20245-1引言

DFT在實際應用中很重要:可以計算信號的頻譜、功率譜和線性卷積等。直接按DFT變換進行計算，當序列長度N很大時，計算量非常大，所需時間會很長。FFT不是一種新的變換，而是DFT算法的一種改進,這種改進實現(xiàn)了快速計算的目的

22十二月2024§5-2DFT的運算量及改進途徑5.2.1DFT的計算量估計兩公式基本結(jié)構(gòu)類似，其差別僅在指數(shù)的符號不同、及逆變換的因子1/N.22十二月2024

通常x(n)和 都是復數(shù),所以計算一個

X(k)的值需要N次復數(shù)乘法運算,和 次復數(shù)加法運算.一個X(k)的運算量,如X(1)

計算全部X(k)就要N2次復數(shù)乘法運算,N(N-1)次復數(shù)加法運算.

當N很大時,運算量將是驚人的,如N=1024,則要完成1048576次(一百多萬次)運算.這樣,難以做到實時處理.22十二月2024運算量估計結(jié)論1.乘法運算的時間是加法的一個量級以上2.DFT運算量與成正比1)N降低運算量的措施:2)利用的有關特性運算量（有效途徑）22十二月20245.2.1降低運算量的途徑

1.利用的特性得:周期性:可約性:對稱性:利用上述特性,可以將有些項合并.22十二月20242.將DFT分解為短序列可以有效降低運算量,提高運算速度.1965年,cooley和Tukey首先提出FFT算法.對于N點DFT,僅需(N/2)log2N次復數(shù)乘法運算.

如:N=1024=210

，需要計算的次數(shù)是:(1024/2)log2210=512*10=5120次而5120/1048576=4.88%

速度提高20倍22十二月2024§5-3按時間抽取(DIT)FFT算法

—庫利-圖基算法算法原理按時間抽取基-2FFT算法與直接計算DFT運算量的比較按時間抽取的FFT算法的特點按時間抽取FFT算法的其它形式流程圖22十二月2024§5-3按時間抽取(DIT)的FFT算法

—庫利-圖基算法5.3.1算法原理(基2-FFT)因此，n為偶數(shù)時:n為奇數(shù)時:1.N點DFT分解為兩個N/2點DFT(1)先將按n的奇偶分為兩組作DFT,設N=2L,不足時,可補些零。這樣有:22十二月2024由于:(n為偶數(shù))

(n為奇數(shù))所以,上式可表示為:22十二月2024(2)兩點結(jié)論:①X1(k),X2(k)均為N/2點DFT。

其中:12kN②X(k)=X

(k)+W

X

(k)能確定出

X(k)的k=個；即前一半點的結(jié)果。22十二月2024(3)X(k)的后一半的確定由于（周期性）,所以:同理:22十二月2024

可見,X(k)的后一半，也完全由X1(k),X2

(k)所確定。

N點DFT可由兩個N/2點的DFT來計算.又由于

,所以22十二月2024實現(xiàn)上式運算的流圖稱作蝶形運算(4)蝶形運算（N/2個蝶形)

前一半

后一半由X1(k)、X2(k)表示X(k)的運算是一種特殊的運算-碟形運算什么是蝶形運算?22十二月2024例1(前一半)

(后一半)1111-1根據(jù)蝶形運算算法畫出蝶形運算圖解:22十二月2024例2以N=8為例,根據(jù)碟形圖,分析N點DFT經(jīng)過第一次分解,FFT計算全過程:解:1111-1先復習基本碟形運算:因此,共N/2個蝶形運算k=0,1,2…

均有一個碟形運算22十二月2024N=8,從第一次分解,看FFT計算過程:(1)由x1(n)求X1(k)(2)由x2(n)求X2(k)DFTDFT乘法次數(shù):4

2乘法次數(shù):4222十二月2024(3)由X1(k),X2(k)求X(k)k=0,可求出:k=1,可求出:k=2,可求出:k=3,可求出:每個碟運算1次乘法乘法次數(shù)N/2=422十二月2024第一次分解,稱為第一級碟形運算X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)NW2NW1WN0-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)NW322十二月2024(1)N/2點的DFT運算量:復乘次數(shù):(4)計算量分析復乘:總共運算量:分析N點序列經(jīng)過一次奇、偶分組后的乘法計算量：N點DFT的復乘為N2;僅經(jīng)過一次分解,計算量減少近一半(2)兩個N/2點的DFT運算量:復乘次數(shù):

(3)N/2個蝶形運算的運算量:復乘次數(shù):例4N點序列經(jīng)過一次奇、偶分組后成為了2個N/2點的序列解22十二月2024以N=8為例

DFT分解為兩個N/2=4點的DFT的計算過程如下.22十二月2024

由X1(k)和X2(k),計算X(k)的全過程如下:

x1(0)=x(0)

x1(1)=x(2)

x1(2)=x(4)

x1(3)=x(6)

x2(0)=x(1)

x2(1)=x(3)

x2(2)=x(5)

x2(3)=x(7)

第一次分解,稱為第一級碟形運算N/2點DFT

X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)NW2NW1WN0-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N/2點DFT

NW322十二月2024第一次分解之后小結(jié):一個N點的序列,分解成兩個N/2點的序列對每一個N/2點的序列的計算,依然采用了傳統(tǒng)的DFT算法經(jīng)一次分解之后,復數(shù)乘法次數(shù):N2/2+N/2算法量下降近一半,還需要繼續(xù)改進算法繼續(xù)對子序列再分解按第一次分解方法類比,繼續(xù)分解直至每一序列為2點止.22十二月2024概念:蝶形信號線(節(jié)點)之距離什么是蝶形信號線距離?4距離=4NW2NW1WN0NW3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)22十二月2024例5分析N點(8點)序列經(jīng)過一次奇偶分組后蝶形運算有哪些特點?

x1(0)

x1(1)

x1(2)

x1(3)

N/2點DFT

X1(0)X1(1)X1(2)X1(3)

x2(0)

x2(1)

x2(2)

x2(3)

N/2點DFT

X2(0)X2(1)X2(2)X2(3)1)N個信號線,組成N/2個蝶形.2)每一蝶形節(jié)點之間的距離為N/2.NW2NW1WN0NW3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)22十二月2024

由于N=2

L，因此，無論x1(n)還是x2(n),

每一個N/2點的序列可繼續(xù)分解為兩個N/4的子序列,以序列x1(n)為例,可以分解如下:5.3.2序列的第2次分解對N/4點的序列x3(n),x4(n),分別進行DFT運算,得到(偶中偶)(偶中奇)22十二月2024從而可得到X1(k)的前N/4點X1(k)的后N/4點為:22十二月2024第二次分解,每個N/2點的序列分解為2個N/4點的序列第2次分解后,時域序列的排列順序?第1次分解,時域序列排列順序先看序列x1(n)對應原序列x(n)設序列x1(n)分解為x3(n)和x4(n)兩個序列22十二月2024接下來,再看序列x2(n)上面的順序,對應原序列x(n)的哪些值呢?x2(n)按序號的奇偶排隊如下:設序列x2(n)分解為x5(n)和x6(n)兩個序列x5(n)x6(n)22十二月202422十二月2024

(0)=

(0)=(0)

(1)=

(2)=(4)

(0)=

(1)=(2)

(1)=

(3)=(6)

(0)=

(0)=(1)

(1)=

(2)=(5)

(0)=

(1)=(3)

(1)=

(3)=(7)3131414152526262因此x1(n),x2(n)兩個N/2點的序列按碟形圖進行計算,則有:N/2點DFTN/2點DFTWWWW0123NNNN-1-1-1-1X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1N/4DFTN/4DFTN/4DFTN/4DFTX

(0)X

(1)X

(0)X

(1)334402NWWNX

(0)X

(1)X

(0)X

(1)556602NWWN22十二月2024

結(jié)論：第2次分解后,得到4個N/4點DFT

對于N=8點的DFT,N/4點即為2點DFT,因此

22十二月2024

代入展開，可得：

X

(0)X

(1)X

(0)X

(1)3344WN0WN2-1-1X

(0)X

(1)X

(0)X

(1)5566WN0WN2-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)

(0)

(4)

(2)

(6)

(1)

(5)

(3)

(7)X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11121222WWWWN0N1N2N3-1-1-1-1因此,8點DFT的FFT的運算流圖如下：

第三次分解第二次分解第一次分解第一級運算第二級運算第三級運算-1WN0-1WN0-1WN0-1WN022十二月2024

這種FFT算法,是在時間上對輸入序列

的次序是偶數(shù)還是奇數(shù)進行分解,故稱為按時間抽取的算法(DIT)。

22十二月20245.3.2DIT的運算量例6FFT運算計算量估計N=8需三級蝶形運算

N=23=8,N=2L

共需L(L=3)級蝶形運算

每級都由N/2個蝶形運算組成,每個蝶形運算有一次復乘.從一個例題開始,分析FFT運算量22十二月2024

因此,N點的FFT的運算量為:復乘:mF

=（N/2）L=（N/2）log2N（復加:aF=N

L=Nlog2

N）DFT與FFT運算量之比較：N2/(N/2)log2N=2N/log2N

因此，N越大，運算量節(jié)省更明顯。如教材第5章表5-1所示。22十二月2024

1.倒位序現(xiàn)象

由圖可知,輸出X(k)按正常順序排列在存儲單元,而輸入是按順序:這種順序稱作倒位序,即二進制數(shù)倒位。5.3.3DIT算法的特點22十二月2024

因奇偶分組造成的,以N=8為例分析如下:第1次分組第2次分組第3次分組000011110100110011010101=0=4=2=6=1=5=3=7N=8時，序號需要3位二進制數(shù)表示22十二月202401234567自然順序n二進制

倒位序

倒位順序n^0

0

00

0

10

1

00

1

11

0

01

0

11

1

01

1

10

0

010

00

1

011

0

0

01

1

0

10

1

11

1

104261537輸入數(shù)據(jù)、中間運算結(jié)果和最后輸出均用同一存儲器。2.原位運算22十二月2024DIT基2-FFT算法與DFT直接計算運算量比較

DIT基-2FFT的信號流圖可知，當N=2L時，共有

級蝶形運算；每級都由

個蝶形運算組成，而每個蝶形有

次復乘、

次復加，因此每級運算都需

次復乘和

次復加。LN/2

N/2

12N22十二月2024這樣

級運算總共需要：L復數(shù)乘法：

復數(shù)加法：

直接DFT算法運算量復數(shù)乘法：

復數(shù)加法：

N2N(N－1)直接計算DFT與FFT算法的計算量之比為M22十二月2024FFT算法與直接DFT算法運算量的比較NN2計算量之比MNN2計算量之比M2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.422十二月20243.蝶形運算兩節(jié)點的距離:2m-1

其中,m表示第m列,且m

=1,…,L

例如N=8=23,

第一級(列)距離為21-1=1,

第二級(列)距離為22-1=2，

第三級(列)距離為23-1=4。

4.的確定

在DIT完整蝶形運算圖中，第m級蝶形運算兩節(jié)點的“距離”為2m-1，因而式（5-23）可寫成如下形式對于程序?qū)崿F(xiàn)，r值的遞推算法如下：（1）將上式蝶形運算兩節(jié)點的第1個節(jié)點標號k表示成L位二進制數(shù)；（2）將二進制數(shù)左移L-m位，右邊空位補零(即乘2L-m)（3）將所得二進制數(shù)轉(zhuǎn)換為十進制數(shù)，該數(shù)即為r值。5.3.4DIT其他形式的流圖1.DIT正常算法的流程圖對于FFT算法流圖，若各節(jié)點的連接支路以及支路系數(shù)不變，則無論各節(jié)點和支路如何變形（改變空間位置），其算法和運算量均不會改變。22十二月20242.DIT其它形式的流圖對于DIT輸出正常順序,輸入倒位序的蝶形運算流圖，按如下兩個步驟改變支路的物理位置（不改變節(jié)點的鏈接支路）。（1）將第2根水平線和第5根水平線平移互換位置，即x(4)水平相連的所有節(jié)點和x(1)水平相連的所有節(jié)點（包括輸入數(shù)據(jù)和輸出數(shù)據(jù)節(jié)點）互換位置，（2）將第4根水平線和第7根水平線平移互換位置，即x(6)水平相連的所有節(jié)點和x(3)水平相連的所有節(jié)點互換位置，該互換也包括輸入數(shù)據(jù)和輸出數(shù)據(jù)節(jié)點。

可得如下所示蝶形運算流圖。2.DIT其它形式的流圖DIT基-2FFT算法輸入自然順序、輸出倒位序的FFT流圖22十二月2024在不改變上圖各節(jié)點的支路連接數(shù)量和連接方式的原則下，繼續(xù)改變某些節(jié)點和支路的空間位置，則可以得到輸入和輸出均為正常順序的FFT蝶形運算圖,如下所示:2.DIT其它形式的流圖

用蝶形圖計算FFT,已知序列x(n)如下：

x(n)=[1，2，1，1]x(n)為4點長序列，根據(jù)DIT基-2算法，其完整蝶形圖如下:虛線左邊為第一級蝶形運算，從上往下4個節(jié)點的結(jié)果如下：1+1=2，1-1=0，2+1=3，2-1=1虛線右邊為第二級運算，第二級運算結(jié)果如下：例7解:22十二月2024§5-4DIF的FFT算法(桑德—圖基算法)5.4.1算法原理1.N點DFT的另一種表達形式22十二月2024

因此

X(k)可表為:

22十二月2024

2.N點DFT按k的奇偶分組可分為兩個N/2的DFT

k為偶數(shù)時：

當k為偶數(shù),即

k=2r時,(-1)k=1；

當k為奇數(shù),即k=2r+1時(-1)k=-1

。這時

X(k)

可分為兩部分：

22十二月2024

可見,上面兩式均為N/2的DFT。k為奇數(shù)時：22十二月20243.蝶形運算-1蝶形運算圖表示法之一22十二月2024蝶形運算圖形表示法之二22十二月20244.N=8時,按k的奇偶分解過程X1(0)X1(1)X1(2)X1(3)-1-1-1-1WWWWNNNN0123先蝶形運算，后N/2點DFT運算:22十二月2024

5.類比DIT算法分解過程如此進行下去,直至分解為2點DFT

將N/2點DFT繼續(xù)按k的奇偶分解為兩個N/4點的DFT22十二月2024

(0)

(1)

(2)

(3)

(4)

(5)

(6)

(7)-1WWWWNNNN0123WWWWNNNN0202N=8點的DIF的FFT流圖分析第一次分解第二次分解第三次分解第一級運算第二級運算第三級運算-1-1-1-1-1-1-1-1-1-1-1-1X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)例8解:22十二月2024由上述分析可知,N=8需三級蝶形運算N=23=8,由此可知,N=2L

共需L級蝶形運算而且每級都由N/2個蝶形運算

組成,每個蝶形運算有一次復乘。6.DIF算法的運算量22十二月2024

因此,N點的FFT的運算量為復乘:mF=（N/2）L=（N/2）log2N（復加:aF=NL=Nlog2N）DFT與FFT運算量之比較：N2/(N/2)log2N=2N/log2N

因此，N越大，運算量節(jié)省更明顯。22十二月2024

1.

原位運算

每級(列)都是由N/2個蝶形運算構(gòu)成,即:

-1WNr5.4.2DIF算法的特點22十二月20242.蝶形運算兩節(jié)點的距離

一般公式為2L-m=N/2m

例如N=23=8

：

(1)m=1時的距離為

8/2=4；

(2)m=2

時的距離為

8/4=2;

(3)m=3

時的距離為

8/8=1。22十二月2024r的求法：

k=(n2n1n0),左移m-1位,右邊空出補零,得(r)2,亦即(r)2=(k)2

2m-1.例如,N=8:(1)m=1,k=2,k=(010)2

左移0位,(r)2=(010)2=2;(2)m=2,k=1,k=(001)2

左移1位,(r)2=(010)2=2;(3)m=2,k=0,k=(001)2

左移1位,(r)2=(010)2=2.3.

的計算

由于DIF蝶形運算的兩節(jié)點的距離為

N/2m,

所以蝶形運算可表為：22十二月20241.相同點

(1)都要求序列長度滿足條件N=2L(2)均需要L次分解，均包含L級運算

(3)總運算量相同,均為（N/2)

Log2N次復乘

(4)編程時都可以進行原位運算；5.4.3DIF與DIT算法的比較比較如下:22十二月20242.不同點

(1)如無特別說明，DIT算法的輸入為倒位序,輸出為自然順序；

DIF算法正好與DIT算法相反。但經(jīng)過改進DIT算法也有輸入為自然順序,輸出為倒位序的情況。22十二月2024(2)蝶形運算不同用矩陣表示=11a.DIT先乘法運算，后求和運算22十二月2024b.DIF用矩陣表示=11先求和運算，后乘法運算22十二月2024(3)兩種蝶形運算的關系

互為轉(zhuǎn)置（矩陣）；

將流圖的所有支路方向都反向,交換輸入和輸出，即可得到另一種蝶形。

a.(DIT)11b.(DFT)1122十二月20245.4.4IFFT算法1.觀察DFT和IDFT運算的差異

22十二月2024

比較以上兩式可知，正變換和反變換差別為：

（1）正、反變換求和式指數(shù)符號不同，分別為：和

（2）反變換系數(shù)（常數(shù)）1/N，正變換系數(shù)為1。

結(jié)論：在DFT快速算法的基礎上，考慮以上兩點即可得到IDFT快速算法。

22十二月20241)可以將常數(shù)1/N分配到每級蝶型運算中,∵,也就是每級蝶形運算乘法運算均乘以1/2。2.IFFT快速算法之一（以DIF為例）2)將換為，即每級蝶型運算的乘法因子換為。正好等于IFFT快速算法中的因子1/N。22十二月2024

X(0)(0)

X(1)(4)

X(2)(2)

X(3)(6)

X(4)(1)

X(5)(5)

X(6)(3)

X(7)(7)-1-1-1-1WWWWNNNN0-1-2-3-1-1-1-1WWWWNNNN0-20-2-1-1-1-1WWWWNNNN0000N=8時IDFT流圖如下：22十二月20243.IFFT快速算法之二

22十二月20243.IFFT快速算法之二

22十二月2024

即：

1）先將X(k)取共軛,直接利用FFT程序計算DFT；

2）求得DFT后再取一次共軛；并乘以1/N,即得x(n)。結(jié)論：

1)在FFT程序的基礎上,在給定的已知數(shù)據(jù)處增加一組循環(huán)語句，求X(k)的共軛；

2)在得出結(jié)果處增加一組循環(huán)語句，對結(jié)果求共軛并乘以1/N;22十二月2024

§5-5

基4-FFT算法5.5.1基-4FFT算法原理

基-2FFT算法的原理是將N點的序列一分為二，一個N點DFT被分解為兩個N/2點DFT的組合，再將N/2點DFT又一分為二，分解為4個N/4點的DFT，直至全部分解為兩點DFT為止?；?4FFT的思路與基-2FFT的思路基本類似，不同點是將N點的序列一分為四，再對各子序列繼續(xù)一分為四，直至分解到全部子序列為4點為止。22十二月2024因此，類似于DIT基-2的分解過程，DIT基-4快速算法先將長度為N=4L的序列x(n)，按如下方式分為四個子序列：因此，DFT變換公式改變?yōu)槿缦滦问?.5.1基-4FFT算法原理

22十二月20245.5.1基-4FFT算法原理

根據(jù)WN的可約性，上式可以進一步化為

根據(jù)N/4點DFT公式，上式可以表示為22十二月2024其中：類似DIT基-2算法的第一次分解，上只能計算出X(k)前四分之一的值,其余值的計算需根據(jù)WN的周期性以及有限長序列隱含的周期性,類似DIT基2算法的方法，可得如下公式：22十二月2024由此可得基-4算法的基本碟形圖如下：22十二月2024DIT基-4快速算法基本蝶形運算圖。為了加深理解，可以根據(jù)DIT基-2算法原理進行類比。為了深入理解基-4FFT算法原理，以N=16為例分析基-4快速運算流圖的規(guī)律。由于N=16=42，即L=2，流圖如下所示：由于僅需2次分解，經(jīng)過第一次分解之后，對于4個N/4點的DFT，各子序列長度均為4點，正好是DIT基-4快速運算的基本單元。根據(jù)基-4算法的原則，四點長的子序列DFT采用基-2FFT運算，這是基-4FFT的最后一次分解。由此可得,當N=16=42時基-4算法的完整碟形運算圖如下根據(jù)原理可得第一列左上角4點基-4快速算法的蝶形運算如下圖。x(n)經(jīng)2次分解后，輸入為正常順序，輸出為二進制倒位序圖中虛線框內(nèi)為一個4點基-4FFT流圖的基本單元22十二月2024

§5-6

線性卷積的FFT算法5.6.1線性卷積傳統(tǒng)計算方法

設一離散線性移不變系統(tǒng)的沖激響應為

,其